第一章 递归问题 学习笔记

河内塔问题

有 \(3\) 根柱子和 \(n\) 个圆盘，我们可以把最顶上的圆盘移到另外的柱子上，但不可以把大的圆盘放在小的圆盘上面

问，最少需要多少步才能把所有圆盘从一根柱子移到另外一跟柱子上

我们先命名一个状态 \(T_n\) 表示圆盘从一根柱子移动到另外一根柱子的最少次数

那么我们思考一种移动方案，假设我们要把圆盘从 \(A\) 柱移动到 \(B\) 柱上

那么我们可以将 \(n-1\) 个圆盘移动 \(C\) 柱上 然后把最下面的圆盘移动到 \(B\) 柱上，最后把 \(n-1\) 个圆盘从 \(C\) 柱移到 \(B\) 柱，所以，我们能得到方程

\[\begin{align*} &T=1 \\ &T_n= 2T_{n-1}+1 (n >0) \end{align*}\]

我们想要得到通项公式，可以盲猜结论 \(T_n = 2^n -1,n \ge 0\)

可以用数学归纳法证明

• \(n=1\) 时等式成立
• \(n\ge 1\)时，假设 \(T_{n-1} = 2^{n-1}-1\) 成立，可得

\[T_n=2T_{n-1}+1=2 \times (2^{n-1}-1)+1=2^n-1 \]

证毕

平面上的直线

平面上 \(n\) 条直线所界定的区域最大个数 \(L_n\) 是多少

我们考虑假设已经有\(n-1\) 条直线，我们需要画一条直线，这条直线最多和 \(n-1\) 条直线相交产生 \(n\) 个新的区域

所以我们得到了

\[\begin{align*} &L_0=1 \\ &L_n=L_{n-1}+n (n >0) \end{align*}\]

很容易我们可以得出 \(L_n=\frac{n(n+1)}{2}+1,n \ge0\)

考虑一个变形，平面上由 \(n\) 条这样的折线所界定区域的最大的个数 \(Z_n\) 是多少

考虑一个折线可以看作两条直线擦掉一半，对于每个折线，我们都失去了 \(2\) 块区域

所以

\[\begin{aligned} Z_n & = L_{2n}-2n \\& = \frac{2n(2n+1)}{2}+1-2n\\ & = 2n^2-n+1,n \ge 0 \end{aligned}\]

约瑟夫问题

从围成标有记号的 \(1\) 到 \(n\) 的 \(n\) 个人开始，每隔一个删去一个人，直到有一个人幸存下来

\(n=10\) 时，消去的人时 \(2,4,6,8,10,7,1,9\) 最后 \(5\) 幸存

我们由此能得到几个规律：

• 每一轮杀人，杀一半，向下取整，偶数编号的人会被杀
• 幸存的人，重新编号

递归表达式

每轮杀人，编号减半，那么最后肯定剩下一个人，我们能不能从第 \(k\) 轮活下来的那个人的编号反推出第 \(k-1\) 轮活下来的那个人的编号呢？

设 \(n\) 个人时的幸存的号码为 \(J(n)\)

• 先考虑偶数的情况，第一圈把偶数的去掉，奇数留下来，假设一开始有 \(2n\) 个人，第一轮后就是
  
  所以我们得到了一个子问题，用递归的思想，假设子问题以及求解完成了，我们可以得到表达式 \(J(2n)=2J(n)-1,n\ge1\),也就是说，存活的那个人的编号是子问题的答案的编号的两倍减一

• 然后考虑奇数，对于 \(2n+1\) 个人
  
  我们得到 \(J(2n+1)=2J(n)+1\)

所以我们得到了表达式

\[\begin{align*} J(1)&=1 \\ J(2n)&=2J(n)-1,n\ge 1\\J(2n+1)&=2J(n)+1,n\ge 1 \end{align*}\]

我们通过这个式子就可以快速得到答案了

接下来尝试把递归式子转化为非递归的形式

二进制形式性质

有了递归式，我们能做出一张表：

显然可以看出，\(J(n)\) 按照 \(2^m\) 为分段，段内为一个等差数列，于是我们能写出 \(J(n)\) 的封闭形式，设 \(n=2^m+l\)，则：

\[J(2^m+l)=2l+1,\ m\ge 0,\ 0\le l<2 \]

我们把 \(n\) 转化成二进制会发现更多规律，不妨设 \(n=(b_mb_{m-1}\cdots b_1b_0)\)

由于首位字母 \(b_m\) 必为 \(1\)，所以 \(n=(1b_{m-1}\cdots b_1b_0)\)，那么 \(l=(b_{m-1}\cdots b_1b_0)\)

所以 \(J(n)=2l+1=(b_{m-1}b_{m-2}\cdots b_01)=(b_{m-1}b_{m-2}\cdots b_0b_m)\)

用计算机程序设计的行话说就是，\(n\) 向左循环移动一位就得到 \(J(n)\)

成套方法

我们尝试把 \(J\) 函数进行拓展，有一个类似于 \(J\) 的递归式，引入常数 \(\alpha\)

\[\begin{align*} f(1)&=\alpha \\ f(2n)&=2f(n)+ \beta ,n\ge 1\\ f(2n+1)&=2f(n)+\gamma ,n\ge 1\\ \end{align*}\]

我们可以构造出如下表：

可以观察出 \(\alpha\) 的系数是不超过 \(n\) 的 \(2\) 的最大幂，\(\beta\) 的系数递减 \(1\) ，\(\gamma\) 的系数递增 \(1\)

我们可以得到 \(f(n)\) 的封闭形式：

\[f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma \]

且我们观察出

\[\begin{align*} A(n) &= 2^m \\ B(n) &=2^m-1-l \\ C(n) &=l \\ \end{align*}\]

这里可以使用数学归纳法证明，但是也可以采用特殊值法来证明，书上把这种方法称为成套方法

由于 \(A(n),B(n),C(n)\) 的关系在任何情况下都是固定的，所以理论上来说 \(\alpha,\beta,\gamma\) 可以取任意值

不妨取 \((\alpha,\beta,\gamma)=(1,0,0)\)，\(f(n)=A(n)\)，由：

\[\begin{align*} f(1)&=1 \\ f(2n)&=2f(n),n\ge 1 \\ f(2n+1)&=2f(n),n\ge 1 \\ \end{align*}\]

很显然可以得到 \(A(n)=f(n)=2^m\)

我们还可以设 \(f(n)=1\)，有：

\[\begin{align*} 1&=\alpha \\ 1&=2\times 1+\beta \\ 1&=2\times1 + \gamma \end{align*}\]

解出来得到 \((\alpha,\beta,\gamma)=(1,-1,-1)\)，于是得到了一个关系式 \(1=A(n)-B(n)-C(n)\)

然后设 \(f(n)=n\)，有：

\[\begin{align*} 1&=\alpha \\ 2n&=2n+\beta \\ 2n+1&=2n+\gamma \end{align*}\]

解出来得到 \((\alpha,\beta,\gamma)=(1,0,1)\)，于是得到了一个关系式 \(n=A(n)+C(n)\)

联立三个式子：

\[\begin{align*} 1&=A(n)-B(n)-C(n) \\ n&=A(n)+C(n) \\ A(n)&=2^m \end{align*}\]

于是 \(B(n)=2^m-1-l,C(n)=l\) 就可以被解出来了，这就是成套方法

有多少个独立的参数，我们就需要多少个特殊的值，本题中有三个 \((\alpha,\beta,\gamma)\)

推广的约瑟夫递归式

前面我们得到了一个二进制下循环移位的性质，那么推广的约瑟夫表达式是否也有类似的性质呢？

推广的递归式的形式如下：

\[\begin{aligned} f(1)&=\alpha \\ f(2n+j)&=2f(n)+\beta_j\ ,\ j=0,1\ ,n\ge 1 \\ \end{aligned} \]

展开就是

\[\begin{align*} f((b_m b_{m-1} \dots b_0)_2) =& 2f((b_m b_{m-1} \dots b_2)_2) + \beta_{b_0} \\ =& 4f((b_m b_{m-1} \dots b_2)_2) + 2\beta_{b_1} + \beta_{b_0} \\ \vdots \\ =& 2^m f((b_m)_2) + 2^{m-1} \beta_{b_{m-1}} + \cdots + 2\beta_{b_1} + \beta_{b_0} \\ = &2^m \alpha + 2^{m-1} \beta_{b_{m-1}} + \cdots + 2\beta_{b_1} + \beta_{b_0}. \end{align*} \]

所以我们可以解除二进制的限制，这里的 \(b_i\) 一点是 \(0,1\) ，但 \(\beta_j\) 可以不为 \(0,1\)

\[f\left((b_m b_{m-1} \cdots b_1 b_0)_2\right) = (\alpha \beta_{b_m-1} \beta_{b_{m-2}} \cdots \beta_{b_1} \beta_{b_0})_2. \]

我们把上面的表格换一种形式就可以看出

完全符合上面的形式，这里的 \(\beta = \beta_0, \alpha = \gamma\)

于是，我们可以考虑推广基数，这里我们设基数为 \(d\)

\[\begin{aligned} f(j) &= \alpha_j, \quad 1 \leq j < d; \\ f(dn + j) &= c f(n) + \beta_j, \quad 0 \leq j < d, \quad n \geq 1 \end{aligned} \]

这个的解是：

\[f\left((b_m b_{m-1} \cdots b_1 b_0)_d\right) = (\alpha_{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} \cdots \beta_{b_1} \beta_{b_0})_c \]

例如，我们有递归式：

\[\begin{aligned} f(1) &= 34; \\ f(2) &= 5; \\ f(3n) &= 10f(n) + 76, \quad n \geq 1; \\ f(3n + 1) &= 10f(n) - 2, \quad n \geq 1; \\ f(3n + 2) &= 10f(n) + 8, \quad n \geq 1; \end{aligned} \]

假设我们这里要计算 \(f(19)\)，有 \(d=3\) ，\(c=10\) ，我们可以把 \(19\) 转化成三进制 \((201)_3\) ，这里的 \(\alpha_1=2,\beta_0=76,beta_1=-2\)，所以 \(f(19)=f((201)_3)=(5\ 76\ -2)_{10}=500 + 760 - 2 = 1258\)