第一章 递归问题

热身题

1. 推理有误，当 \(n = 2\) 时不存在标号为 \(2 \sim n - 1\) 的马。
2. 令 \(A_{i}\) 表示将 \(i\) 个圆盘从 \(A\) 柱移至 \(B\) 所需的最少步数。显然有 \(A_{1} = 1\)。对于任意的 \(i(i \geqslant 2)\)，若想要使最大的圆盘从 \(A\) 柱移至 \(B\) 柱，需先将其余的 \(i - 1\) 个圆盘移动至 \(B\) 柱，然后将第 \(i\) 个圆盘移动至中间柱子，再将其余 \(i - 1\) 个圆盘移回 \(A\) 柱，将第 \(i\) 个圆盘移动至 \(B\) 柱，最后再将剩下的 \(i - 1\) 个圆盘移动至 \(B\) 柱，所以 \(A_{i} = 3A_{i - 1} + 2\)。
3. 类似 (2.) 的思路，先将最底层圆盘移动至目标位置，同时保持剩下的圆盘的相对顺序，再移动次大的圆盘。
4. 不存在。因为确定每一个圆盘的位置时都移动了最多的步数 \(2T_{i - 1} + 1\)（已是最坏情况），若目标位置不同只可能步数更少而不可能增多。
5. 不可能。考虑再当前的维恩图上再添加一个圆，此圆必须与八个部分都有交集并且不为互不包含关系，而 \(A \cap B, b \cap C, c \cap A\) 的部分将 \(A \cap B \cap C\) 的部分完全「围住」，若新圆与这些部分有交集则必定包含 \(A \cap B \cap C\)。
6. 令 \(B_{i}\) 表示由 \(i\) 条直线围成的「有界」区域的最大数量，显然 \(B_{1} = 0, B_{2} = 0, B_{3} = 1\)，对于 \(i(i \geqslant 4)\)，新加入的直线最多同时与原来的所有直线相交，这 \(i\) 条直线最多划分出 \(i + 1\) 个「无界」区域，而两端的「无界」区域无法划分出有界区域，所以最多能多出来 \(i - 2\) 个「有界」区域，所以 \(B_{i} = B_{i - 1} + i - 2\)。
7. 此推理过程只证明了 \(H(2n + 1) = 2H(n) - 2(n \geqslant 1)\)，而没有关于 \(H(1)\) 的证明，故对于 \(H(3), H(7), H(15), \cdots\) 都没有证明，错误。

习题