数系、算法与递归

前几章分别讨论了集合包含哪些对象、函数怎样对应元素，以及序列怎样按指标取值。本章把这些概念用到算术与计算中：先比较常见数系，再研究算法需要的整数运算，最后证明迭代与递归过程确实能完成指定任务。

阅读前应掌握朴素集合论、函数与映射和数列与级数。全文统一采用 $\mathbb N=\{0,1,2,\ldots\}$，正整数写作 $\mathbb Z_{>0}$。关于无限集、递归数据与循环不变量，可以继续阅读 Mathematics for Computer Science 中的相关章节[1][1] E. Lehman, F. T. Leighton, and A. R. Meyer, Mathematics for Computer Science. MIT OpenCourseWare, 2015. Revised May 18, 2015; infinite sets, recursive data, and invariants. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf。

数系扩展了允许进行的运算

常见数系具有包含关系：

$$\mathbb N\subsetneq\mathbb Z\subsetneq\mathbb Q \subsetneq\mathbb R\subsetneq\mathbb C.$$

在通常的嵌入方式下，向右扩展时保留已有的数，同时允许新的方程解或极限。

数系	包含什么	扩展带来什么
$\mathbb N$	$0,1,2,\ldots$	计数与归纳
$\mathbb Z$	正整数、负整数与零	做减法不会离开这个数系
$\mathbb Q$	整数之比 $p/q$，其中 $q\ne0$	可以除以任意非零元素
$\mathbb R$	有理数与无理数	构成完备有序域
$\mathbb C$	$a+bi$，其中 $a,b\in\mathbb R$、$i^2=-1$	为 $x^2=-1$ 提供解，并扩展代数讨论的范围

前几步可以从方程理解：$x+3=1$ 在 $\mathbb N$ 中无解，$2x=1$ 在 $\mathbb Z$ 中无解。从 $\mathbb Q$ 到 $\mathbb R$，还要解决极限过程中的缺口，不能仅理解为补上某一个平方根。复数的性质在复数章继续展开。

同一个有理数可以有不同的分数表示。分母非零时，

$$\frac pq=\frac rs\quad\Longleftrightarrow\quad ps=rq.$$

因此，$1/2$ 与 $2/4$ 表示同一个数，不是 $\mathbb Q$ 的两个元素。严格构造有理数时，可以把满足这种等价关系的整数对归为同一个对象，这就是等价类的一个应用。

无理数集写作 $\mathbb R\setminus\mathbb Q$。它不是包含链上的另一个域：$\sqrt2$ 与 $-\sqrt2$ 都是无理数，但它们相加得到有理数。素数也只是 $\mathbb N$ 的一个特殊子集，并非新的数系层级。素数是大于 $1$、正因子只有 $1$ 和自身的整数；特别地，$1$ 不是素数。

小数表示与数本身要分开

有理数的小数展开要么终止，要么从某一位开始循环。对正分母 $q$ 做长除法时，余数只有 $q$ 种可能；余数为零，展开终止，否则迟早重复某个余数，后面的数字便跟着重复。反过来，最终循环的小数尾部可以写成等比级数，因此表示有理数。

例如，$1/3=0.\overline3$。同一个数还可能有两种小数展开，如 $0.999\ldots=1$。无限且不循环的小数表示无理数，但只观察很长的一段有限前缀，不能证明后面永远不循环。实数可以用截断的小数逐步作有理近似；这是实数系统的性质，并不是在尚未定义极限时就已经给出的实数构造。

集合大小：康托尔对角线论证

有理数很稠密：任意两个不同的有理数之间，总能再找到一个有理数。但这并不妨碍把它们逐个列出。要证明实数不可数，需要指出另一种障碍：不管怎样安排列表，总会漏掉一个实数。

定理区间 (0,1) 不可数

不存在一个序列 $x_1,x_2,\ldots$，能够包含 $(0,1)$ 中的全部实数。

这里从 $1$ 开始编号，是为了让行号与小数位数对应；改从 $0$ 开始不会影响可数性。列表也允许重复，即使允许一个数出现多次，仍然不可能列尽整个区间。

第一步：假设已经列出了全部实数

证明

反设 $(0,1)$ 中的所有实数都出现在一个序列里。每个数都选用末尾不全是九的小数表示。例如，使用 $0.5000\ldots$，不用 $0.4999\ldots$。

把第 $k$ 个数写成

$$x_k=0.d_{k1}d_{k2}d_{k3}\ldots.$$

第一个下标表示行号，第二个下标表示小数位数。因此，$d_{kn}$ 是第 $k$ 个数的小数点后第 $n$ 位。有限表格只能画出有限行、有限列，但假设中的列表与每一行的小数都无限延伸。

图中前五个对角线数字是 $1,3,1,5,1$，改写后得到 $2,1,2,1,2$。这里只展示前五位，后面的每一位也都按同一规则确定。

第二步：沿对角线，每行挑一位改掉

依次读取 $d_{11},d_{22},d_{33},\ldots$：第一个数的第一位、第二个数的第二位，以此类推。定义

$$e_n= \begin{cases} 1,&d_{nn}\ne1,\\ 2,&d_{nn}=1. \end{cases}$$

无论原数字是什么，都有 $e_n\ne d_{nn}$。对角线的作用就在于把“第 $n$ 行”与“第 $n$ 位”配对：给每一行预留一个保证不同的位置。

第三步：确认新数字确实组成一个实数

令 $y=0.e_1e_2e_3\ldots$。更明确地说，

$$y=\sum_{n=1}^{\infty}\frac{e_n}{10^n}.$$

每一位都只取 $1$ 或 $2$，所以部分和递增且有上界，确定了一个实数。用每位全为 $1$ 和每位全为 $2$ 的等比级数夹住它，得到

$$\frac19\le y\le\frac29.$$

因此 $y\in(0,1)$。这一步保证我们构造出的对象仍在原本声称要列尽的集合中。

第四步：证明新数不等于任何一行

任取行号 $k$。在小数点后第 $k$ 位，列表中的 $x_k$ 使用数字 $d_{kk}$，而新数 $y$ 使用数字 $e_k$。根据构造，

$$e_k\ne d_{kk}\quad\Longrightarrow\quad y\ne x_k.$$

这里用到了前面的小数约定：列表中的表示都排除了末尾全九，$y$ 又只含数字一和二，不会遇到终止小数的双重表示。下文会把这个细节单独说明。

由于 $k$ 可以是任意行号，$y$ 与列表中的每一个数都不同。但 $y$ 明明属于 $(0,1)$，完整列表就应该包含它，矛盾。因此，这样的完整列表不存在。

为什么必须处理小数表示不唯一

两个数字串不同，不一定表示两个不同的数。例如，

$$0.5000\ldots=0.4999\ldots.$$

如果随意把对角线上的数字改成 $0$ 或 $9$，却不处理这种情况，证明就可能留下漏洞。我们只用 $1$ 和 $2$ 构造新数，因此它既不可能末尾全零，也不可能末尾全九；列表中的数也统一选用了末尾不全九的表示。

为什么只有这种小数表示会重复

设两个小数串第一次在第 $N$ 位不同，且 $a_N<b_N$。较大的数字至少带来 $10^{-N}$ 的差距，而后面所有位最多只能抵消

$$\sum_{n>N}\frac9{10^n}=10^{-N}.$$

所以，两个串若仍表示同一个数，就必须满足：$b_N=a_N+1$，较小数字所在的串从下一位起全是九，较大数字所在的串从下一位起全是零。只要后缀没有抵消到这个极限，两个数就严格不同。

这既解释了 $0.4999\ldots=0.5000\ldots$，也说明排除末尾全九后，表示就唯一了。只含数字一和二的小数串更不可能参与这种重复。

这个论证究竟否定了什么

新数依赖于给定的列表。结论是“对于每一个列表，都能找到它漏掉的数”，并不是“存在一个固定的数，所有列表都漏掉它”。如果重新安排列表，把刚才漏掉的数也列进去，再对新列表做一次对角线构造，就会得到另一个遗漏。无限列表本来也没有一个最后的位置，可以简单地把新数补在后面。

这个构造也没有证明新数一定是无理数。对角线不同，得到的数字可能重复，也可能不重复；证明只需要它是一个不在列表中的实数。对有理数列表使用类似的改位规则，并不会否定有理数可数，因为构造出的实数不一定仍是有理数。

由于 $(0,1)\subseteq\mathbb R$，实数集也不可数。无理数集同样不可数：如果无理数可数，把它们的列表与有理数列表交错合并，就能让全部实数可数，与刚才的结论矛盾。

同样的“让第 $n$ 位与第 $n$ 行不同”也出现在数列与级数的无限二进制序列中，以及朴素集合论的自然数幂集论证中。对象虽然不同，对角线构造承担的作用相同。

集合的势、数值的顺序、允许的运算，需要分别判断。补入负数或有理分数，没有改变自然数集的可数无限大小；扩展到全部实数时，势才发生变化。

域、序与完备性

域让适当的算术运算可逆

定义域

域 $F$ 配有加法与乘法，两种运算都把 $F\times F$ 映到 $F$，并具有不同的元素 $0,1$。加法满足结合律与交换律，以 $0$ 为单位元，每个元素都有加法逆元。乘法满足结合律与交换律，以 $1$ 为单位元，每个非零元素都有乘法逆元。乘法对加法满足分配律。

减法就是加上加法逆元；除以非零元素，就是乘以它的乘法逆元。$\mathbb Q$、$\mathbb R$、$\mathbb C$ 都满足这些公理。$\mathbb Z$ 不是域，因为 $2$ 在其中没有乘法逆元；$\mathbb N$ 也不是域，因为 $1$ 在其中没有加法逆元。

证明零为什么没有逆元，消去为什么需要条件

由分配律，

$$x\cdot0=x(0+0)=x\cdot0+x\cdot0.$$

两边减去 $x\cdot0$，得到 $x\cdot0=0$。因此不可能有 $0u=1$。

若 $xz=yz$ 且 $z\ne0$，两边乘以 $z^{-1}$ 得到 $x=y$。但 $z=0$ 时，不论 $x,y$ 是什么，原等式都成立，不能推出二者相等。同理，若 $xy=0$ 且 $x\ne0$，乘以 $x^{-1}$ 就得到 $y=0$：域中不存在非零零因子。

顺序必须与算术相容

定义有序域

有序域是在域上配备全序 $\le$：这个序自反、反对称、传递，且任意两个元素都能比较。它与运算满足

$$x\le y\quad\Longrightarrow\quad x+z\le y+z,$$

并且乘以正数保持严格不等式：

$$x<y,\quad z>0\quad\Longrightarrow\quad xz<yz.$$

反对称性指的是：由 $x\le y$ 和 $y\le x$ 推出 $x=y$。对严格次序，$x<y$、$x=y$、$y<x$ 三种情形恰好有一种成立。若漏掉相等情形，取 $x=y$ 就会出问题。

乘以负数会反转不等号。平方总非负：$x\ge0$ 时是非负因子的乘积；$x<0$ 时，用 $x^2=(-x)^2$，其中 $-x>0$。特别地，$1>0$。若 $0<x<y$，在 $x<y$ 两边乘以正数 $1/(xy)$，便得到 $0<1/y<1/x$。

通常的大小关系使 $\mathbb Q$ 和 $\mathbb R$ 成为有序域。$\mathbb C$ 则不能成为有序域，因为 $i^2=-1$ 将是一个非负的平方，这与 $1>0$ 矛盾。这里说的是无法与域运算相容，不是否认可以用其他规则给复数排序。

完备性补上序结构中的缺口

集合 $S$ 的上界 $u$ 满足：对所有 $s\in S$，都有 $s\le u$。上确界是最小的上界，即它不大于任何其他上界。最大值必须属于 $S$，上确界不一定属于 $S$。例如，$(0,1)$ 的上确界为 $1$，但没有最大值。

定义有序域的完备性

若每个非空且有上界的子集，都在该域中有上确界，就称这个有序域完备。实数构成完备有序域。

“在该域中”不能省略。例如有理数集合

$$S=\{q\in\mathbb Q:q\ge0,\ q^2<2\}$$

在 $\mathbb R$ 中的上确界为 $\sqrt2$，却在 $\mathbb Q$ 中没有上确界。有理数能从下方任意接近 $\sqrt2$；任何有理上界又都能稍微减小，仍保持在 $\sqrt2$ 上方。$\sqrt2$ 的无理性已在间接证明中证明，而这些近似依赖有理数在实数轴上的稠密性，本章练习会给出证明。“任意两点之间还有点”比“所需的上确界都存在”弱得多。完备有序域的进一步讨论可见 Lebl 的 Basic Analysis[2][2] J. Lebl, Basic Analysis I: Introduction to Real Analysis, Volume I. . Online edition; Sections 1.1--1.2 on ordered fields and completeness; accessed September 6, 2026. https://www.jirka.org/ra/html/。

完备性还推出自然数在实数中无上界。否则，若 $s=\sup\mathbb N$，则更小的 $s-1$ 不是上界，于是存在 $n\in\mathbb N$ 满足 $n>s-1$。但这样 $n+1>s$，又与 $s$ 为上界矛盾。这就是这里需要的阿基米德性质：整数可以超过任意给定的实数阈值。下取整和上取整的存在会用到它。

下取整、上取整与欧几里得余数

定义下取整与上取整

对实数 $x$，下取整 $\lfloor x\rfloor$ 是不超过 $x$ 的最大整数，上取整 $\lceil x\rceil$ 是不小于 $x$ 的最小整数。定义对应的范围是

$$\lfloor x\rfloor\le x<\lfloor x\rfloor+1,$$$$\lceil x\rceil-1<x\le\lceil x\rceil.$$

阿基米德性质与非负整数的良序性保证这样的整数存在。下取整是向下取，不是向零截断：$\lfloor-2.3\rfloor=-3$，而 $\lceil-2.3\rceil=-2$。当输入是整数 $k$ 时，两者都等于 $k$。

对每个整数 $k$，下取整在 $[k,k+1)$ 上恒为 $k$，上取整在 $(k-1,k]$ 上恒为 $k$。用半开区间描述，可以准确区分跳跃点处的取值。

证明取负会交换下取整与上取整

设 $m=\lceil x\rceil$，由定义得 $m-1<x\le m$。取负并反转不等号，得到

$$-m\le-x<-m+1.$$

因此 $\lfloor-x\rfloor=-m=-\lceil x\rceil$。再把 $x$ 换成 $-x$，也得到 $\lceil-x\rceil=-\lfloor x\rceil$。

用正除数固定余数约定

设 $a\in\mathbb Z$、$m\in\mathbb Z_{>0}$，取

$$q=\left\lfloor\frac am\right\rfloor, \qquad r=a-mq.$$

由下取整的范围得到 $mq\le a<m(q+1)$，从而

$$a=mq+r,\qquad 0\le r<m.$$

这证明了欧几里得商与余数的存在性。若还有另一组满足同样条件的 $q',r'$，则 $m(q-q')=r'-r$。右边严格位于 $-m$ 与 $m$ 之间，而这个范围内唯一的 $m$ 的整数倍是零。因此 $q=q'$、$r=r'$，唯一性得证。

记 $a\bmod m=r$。例如，$-17=5(-4)+3$，所以 $-17\bmod5=3$。整除 $m\mid a$ 的意思是存在整数 $k$ 使 $a=mk$；当 $m$ 为正时，这等价于余数为零。编程语言的运算符及负除数约定需要另外核对，下面所有取余运算都使用正除数。

算法需要输入输出约定，也需要正确性论证

一个计算过程由明确、可执行的步骤组成。若要声称它解决了某个问题，就要说明哪些输入合法、输出应满足什么条件，再分别证明每个合法输入都会终止，以及返回结果满足要求。算术问题本身有解，并不能证明某段程序能够正确求解。

伪代码用来描述这些步骤，不依赖具体编程语言。符号 $\gets$ 表示赋值；证明中的等号则表示数学关系。这里使用精确算术，机器溢出不属于当前模型。

折半与倍增乘法

给定 $M\in\mathbb Z$、$N\in\mathbb N$，下面的算法返回 $MN$。只有第二个输入要求非负，并且允许为零。

算法 1 折半与倍增乘法

Require: $M \in \mathbb{Z}$，$N \in \mathbb{N}$

Ensure: 乘积 $MN$

1:$A \gets M$，$B \gets N$，$p \gets 0$

2:while $B > 0$ do

3:if $B \bmod 2 = 1$ then

4:$p \gets p+A$

5:end if

6:$A \gets 2A$

7:$B \gets \lfloor B/2 \rfloor$

8:end while

9:return $p$

取 $M=73,N=41$，循环更新前的各行如下：

$A$	$B$	加入 $p$ 的值
$73$	$41$	$73$
$146$	$20$	$0$
$292$	$10$	$0$
$584$	$5$	$584$
$1168$	$2$	$0$
$2336$	$1$	$2336$

相加得到 $73+584+2336=2993=73\cdot41$。

证明循环不变量与终止性

每次迭代开始时，不变量为 $p+AB=MN$，初始化显然满足。将当前的 $B$ 写成 $2q+r$，其中 $r\in\{0,1\}$。完整的一轮更新得到 $p'=p+rA$、$A'=2A$、$B'=q$，因此

$$\begin{aligned} p'+A'B'&=p+rA+2Aq\\ &=p+A(2q+r)\\ &=p+AB. \end{aligned}$$

无论奇偶，不变量都保持。只要 $B>0$，新值 $\lfloor B/2\rfloor$ 就是严格更小的非负整数，因此循环必定终止。终止时 $B=0$，由不变量得到 $p=MN$。若 $N=0$，直接跳过循环，初始结果零已经正确。

复杂度依赖输入规模与计费模型

当 $N>0$ 时，完成 $k$ 次迭代后的状态只要仍在执行过程中，就满足

$$B_k=\left\lfloor\frac{N}{2^k}\right\rfloor.$$

连续整数折半给出这个表达式；把 $N$ 写成 $2^k$ 的整数倍加余数，就能核对它。若 $2^{L-1}\le N<2^L$，则 $B_{L-1}=1$、$B_L=0$，所以确切迭代次数是

$$L=\lfloor\log_2N\rfloor+1.$$

这里包含从 $B=1$ 开始的最后一轮。$N=0$ 时迭代零次，不使用对数。正整数 $N$ 的二进制长度也恰好为 $L$：相对于数值大小是对数关系，相对于这个输入的位数则是线性关系。

定义Big-O 与紧界

对最终非负、定义在自然数上的函数 $T,f$，若存在常数 $c>0$ 与 $n_0$，使得

$$0\le T(n)\le c f(n)\qquad(n\ge n_0),$$

就记 $T(n)=O(f(n))$。若最终同时有 $f(n)$ 的正常数倍作为上界和下界，则记 $T(n)=\Theta(f(n))$。

Big-O 是函数的渐近上界，不表示已经做过运行时间测量，也不是“最坏情况”的同义词。最坏、平均或其他约定下的成本函数，都可以讨论渐近界。常见增长率包括 $1$、$\log n$、$n$、$n\log n$、$n^2$、$2^n$。

若每次精确整数操作都记一个单位成本，上面的乘法在 $N>0$ 时需要 $\Theta(L)$ 的循环工作量，并使用固定数量的整数寄存器。这不等于占用固定数量的比特：输入变大时，寄存器要存的整数也变长。使用普通二进制表示和朴素运算时，可以给出 $O(L(M_b+L))$ 的位操作上界，以及 $O(M_b+L)$ 的工作位数，其中 $M_b$ 是 $|M|$ 的二进制长度，零也至少按一位计。这个上界把每轮成本估为 $O(M_b+L)$。更精细的实现分析可能改进它，但不能省略成本模型。

递归通过更小的对象定义对象

递归定义需要起始情形、构造规则，以及依赖链不会无限下降的理由。例如，

$$0!=1,\qquad (n+1)!=(n+1)n!$$

为每个 $n\in\mathbb N$ 唯一确定了一个值：下一项只使用已经定义的值。递归计算 $n!$ 时，非负参数逐次减小，最终到达零。公式里出现自身，并不自动保证定义存在、唯一，也不保证计算终止。

有限严格二叉树

用且仅用下面两条规则定义树：$\operatorname{Leaf}$ 是树；若 $L,R$ 是树，则 $\operatorname{Node}(L,R)$ 是树。除此以外没有别的树。两个构造器彼此不同，左右参数有顺序，因此每个非叶节点都有唯一的左右子树。这里说的是经过有限次构造得到的有限严格二叉树，每个内部节点恰有两个孩子；这种树也称 full/proper binary tree，不要求所有叶子深度相同。

递归定义叶子数 $\ell$ 与内部节点数 $i$：

$$\ell(\operatorname{Leaf})=1,\qquad i(\operatorname{Leaf})=0,$$ $$\ell(\operatorname{Node}(L,R))=\ell(L)+\ell(R),$$ $$i(\operatorname{Node}(L,R))=1+i(L)+i(R).$$

由此得到统计叶子的递归算法：

算法 2 统计叶子数

Require: 有限严格二叉树 $T$

Ensure: $T$ 的叶子数

1:if $T=\operatorname{Leaf}$ then

2:return $1$

3:else

4:设 $T=\operatorname{Node}(L,R)$

5:$a \gets$ CountLeaves($L$)

6:$b \gets$ CountLeaves($R$)

7:return $a+b$

8:end if

每次递归调用都进入节点更少的真子树，因此对指定的有限输入必定终止。这个理由不能自动推广到无限树。

结构归纳沿着构造规则证明

要证明性质对所有这样的树成立，先证明它对 $\operatorname{Leaf}$ 成立；再假设性质对任意 $L,R$ 成立，并证明它对 $\operatorname{Node}(L,R)$ 成立。两种情形覆盖每一种允许的有限构造。这就是结构归纳法；自然数归纳对应的构造规则则是零和后继。

证明叶子数比内部节点数多一

对一片叶子，$\ell=1=i+1$。假设 $\ell(L)=i(L)+1$、$\ell(R)=i(R)+1$，并记 $T=\operatorname{Node}(L,R)$，则

$$\begin{aligned} \ell(T)&=\ell(L)+\ell(R)\\ &=i(L)+i(R)+2\\ &=i(T)+1. \end{aligned}$$

所以每棵有限严格二叉树的叶子数，都比内部节点数多一。这里的归纳假设分别针对两个直接子树，而不是含糊地假设“前一棵树”已经满足结论。

练习

练习可数大小、上确界与最大值

设 $S=\{1-1/n:n\in\mathbb Z_{>0}\}$，判断它的势、上确界，以及是否有最大值。

展开解答

解

这些值严格递增，所以正整数与 $S$ 一一对应，$S$ 可数无限。每一项都小于 $1$。若 $u<1$，由阿基米德性质选整数 $n>1/(1-u)$，就有 $1-1/n>u$。因此任何小于 $1$ 的数都不是上界，故 $\sup S=1$。由于 $1\notin S$，它不是最大值；也可以注意到每项之后都有更大的一项。

练习在两个实数之间找有理数

设实数 $a<b$。用阿基米德性质和下取整，找整数 $p$ 与正整数 $n$，使 $a<p/n<b$。

展开解答

解

先选正整数 $n$ 使 $n(b-a)>1$，再取 $p=\lfloor na\rfloor+1$。由下取整的范围，

$$na<p\le na+1<nb.$$

除以正数 $n$，就得到所需结论。这证明了有理数在实数轴上稠密，却不意味着有理数不可数。

练习把取整比较改写成实数不等式

对整数 $m$，分别改写条件 $\lfloor x\rfloor<m$、$m\le\lfloor x\rfloor$、$\lfloor x\rfloor\le m$、$m<\lfloor x\rfloor$、$\lfloor x\rfloor=m$ 与 $\lceil x\rceil=m$。

展开解答

解

按相同顺序，等价条件为

$$\begin{gathered} x<m,\qquad m\le x,\\ x<m+1,\qquad m+1\le x,\\ m\le x<m+1,\\ m-1<x\le m. \end{gathered}$$

最后两个就是定义区间。第二个条件说明整数 $m$ 是一个不超过 $x$ 的候选整数，因而不大于其中最大的整数；第一个是它的否定。对第三、第四个条件，将这些结论用于整数 $m+1$，并利用 $m$ 与 $m+1$ 之间没有别的整数即可。

练习奇偶分类也覆盖负整数

证明对每个整数 $k$，都有

$$\left\lceil\frac{k-1}{2}\right\rceil=\left\lfloor\frac k2\right\rfloor,$$$$\left\lfloor\frac{k-1}{2}\right\rfloor=\left\lceil\frac k2\right\rceil-1.$$

展开解答

解

若 $k=2t$，第一个等式两边都为 $t$，第二个两边都为 $t-1$。若 $k=2t+1$，两个等式的两边都为 $t$。所有整数都属于这两种情形，包括负整数。例如 $k=-3$ 时，两个等式的两边均为 $-2$。

练习负整数的余数

求 $-23$ 除以 $7$ 的欧几里得商与余数。为什么把 $-23/7$ 向零截断，不会得到这里要求的商？

展开解答

解

商为 $-4$，余数为 $5$，因为 $-23=7(-4)+5$，且 $0\le5<7$。向零截断得到 $-3$，对应的余数为 $-2$，不在规定范围中。符号约定属于定义，不能当成可以忽略的实现细节。

练习只有三个元素的域

设域 $F=\{0,1,u\}$ 中三个元素互不相同。证明 $u+u=1$、$u^2=1$，并写出运算表。

展开解答

解

由消去律，$1+1\ne1$。若 $1+1=0$，则 $u+1$ 既不能为 $u$，也不能为 $1$，否则消去后分别得到 $1=0$ 或 $u=0$；它也不能为 $0$，否则 $u+1=1+1$ 推出 $u=1$。这样 $F$ 中没有可用的结果，矛盾。因此 $1+1=u$。接着，$1+u$ 既不是 $1$ 也不是 $u$，只能为零。由结合律，

$$\begin{aligned} u+u&=(1+1)+u\\ &=1+(1+u)=1. \end{aligned}$$

域没有非零零因子，所以 $u^2\ne0$；若 $u^2=u$，乘以 $u^{-1}$ 会得到 $u=1$，也不成立。因此 $u^2=1$。运算表为

$$\begin{array}{c|ccc} +&0&1&u\\\hline 0&0&1&u\\ 1&1&u&0\\ u&u&0&1 \end{array}$$$$\begin{array}{c|ccc} \cdot&0&1&u\\\hline 0&0&0&0\\ 1&0&1&u\\ u&0&u&1 \end{array}$$

这就是模 $3$ 算术，其中 $u$ 表示 $2$。$1$ 的加法逆元为 $u$，$u$ 的加法逆元也正是 $1$；互为逆元的关系是双向的。

练习探索：四元域与六元域

是否存在恰好四个元素、恰好六个元素的域？注意区分四元域与模 $4$ 算术。

展开讨论

解

四元域存在，其元素为 $0,1,\alpha,\alpha+1$。多项式系数按模 $2$ 计算，并用 $\alpha^2=\alpha+1$ 化简。严格地说，这是在二元域上对多项式 $t^2+t+1$ 取商得到的结构。继承的运算满足环的公理，且每个非零元素都有逆元：$1^{-1}=1$，$\alpha(\alpha+1)=1$。但模 $4$ 算术中，非零元素 $2$ 的平方为零，所以不是域。

有限域的特征是素数 $p$：把若干个 $1$ 相加首次得到零时，所需的最小正整数不可能是合数，否则分解会产生非零零因子。域中于是包含一个有 $p$ 个元素的子域。把原域视为这个子域上的向量空间，设有限维数为 $d$，按每个坐标的 $p$ 种取值计数，元素总数就是 $p^d$。六不是素数幂，所以六元域不存在。这里预用了多项式商与向量空间的构造，详细理论留到抽象代数。

练习用不变量证明平方乘法

设乘法满足结合律，且具有单位元 $1$，$n\in\mathbb N$。证明下面的算法返回 $b^n$。零次幂表示单位元。

算法 3 平方乘法

Require: $n \in \mathbb{N}$ 与元素 $b$

Ensure: $b^n$

1:$p \gets 1$，$s \gets b$，$a \gets n$

2:while $a > 0$ do

3:if $a \bmod 2 = 1$ then

4:$p \gets p s$

5:end if

6:$s \gets s^2$

7:$a \gets \lfloor a/2 \rfloor$

8:end while

9:return $p$

展开解答

解

取 $ps^a=b^n$ 为不变量。初始化满足它。将当前的 $a$ 写成 $2q+r$，其中 $r\in\{0,1\}$。更新后的值为 $p'=ps^r$、$s'=s^2$、$a'=q$，于是

$$\begin{aligned} p'(s')^{a'}&=(ps^r)(s^2)^q\\ &=ps^{r+2q}\\ &=ps^a. \end{aligned}$$

这里仅需结合律和同一个元素的幂运算规则，不要求任意两个元素可交换。正的 $a$ 严格减小，所以循环终止。终止时 $a=0$，不变量给出 $p=b^n$。$n=0$ 时不进入循环，直接返回单位元。对正的 $n$，迭代次数与乘法算法一样，为 $\lfloor\log_2n\rfloor+1$。任何断言 $a_k>0$ 的下界都只能用于终止之前，不能声称对所有非负整数 $k$ 成立。

练习用树高进行结构归纳

约定叶子的高度为零，节点的高度为左右子树高度的最大值加一。证明高度为 $h$ 的有限严格二叉树至多有 $2^h$ 片叶子。

展开解答

解

叶子情形有 $1=2^0$ 片叶子。在高度为 $h$ 的节点处，两个子树的高度都至多为 $h-1$。由两个归纳假设，各自至多有 $2^{h-1}$ 片叶子，相加至多为 $2^h$。这就覆盖了所有有限构造得到的树，不需要假设左右子树等高。

练习说清楚究竟在计算什么资源

某实现使用三个整数变量，循环执行 $L$ 次。仅凭这些信息，能否证明它使用 $O(1)$ 比特空间和 $O(L)$ 位操作时间？

展开解答

解

不能。变量个数固定，只能说明寄存器个数固定，里面的数仍可能需要越来越多的比特。同样，只有在所选模型下每轮成本有统一常数界时，$L$ 轮才能推出 $O(L)$ 时间。对不断变长的整数做精确运算，必须计入操作数长度。报告复杂度前，应先说明输入编码与操作成本。

参考文献

1. [1] E. Lehman, F. T. Leighton, and A. R. Meyer, Mathematics for Computer Science. MIT OpenCourseWare, 2015. Revised May 18, 2015; infinite sets, recursive data, and invariants. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf ↩
2. [2] J. Lebl, Basic Analysis I: Introduction to Real Analysis, Volume I. . Online edition; Sections 1.1--1.2 on ordered fields and completeness; accessed September 6, 2026. https://www.jirka.org/ra/html/ ↩