[具体数学]第一章·递归问题

第一章·递归问题分 3 节，主要包括 $$ 塔问题、平面上直线分割问题、约瑟夫问题。其中，个人认为约瑟夫问题的讨论相当具有启发性。

Hanoi 塔问题

Notes

这是个超级经典的递归问题了，不多做解释。设 $$ 是 $$ 个圆盘的移动次数，那么有递归式： $$ 两边同时加一转化成等比数列，或者用数学归纳法，最后解得： $$

习题

书上的习题有一些 $$ 塔问题的变式，在此挑一些记录一下：

• 不允许在最左边的 $$ 柱和最右边的 $$ 柱之间直接移动： $$ 证明：这种移动规则下，$$ 根柱子上都会出现 $$ 个圆盘的每一种正确叠放。

  证：宏观来看，一共就 $$ 种可能，而 $$，一定遍历了所有可能的叠放方式。$$

  批注：这问题问得很玄学，转换角度思考就变简单了。

• 是否存在某种初始情形和结束情形，使得需要多于 $$ 的移动？

  不存在，归纳：如果最大盘不动，最多 $$ 次；否则，最多 $$ 次。$$

  批注：不知道咋整就归纳，哈哈

• 要求移动必须是顺时针方向（只能 $$），设 $$ 是 $$ 的最少移动次数，$$ 是 $$ 的最少移动次数，求证： $$ 证：意思就是 $$ 是跨一步，$$ 是跨两步。

  跨一步这样完成：$$ 个盘 $$，$$ 个盘 $$，$$ 个盘 $$，故 $$；

  跨两步这样完成：$$ 个盘 $$，$$ 个盘 $$，$$ 个盘 $$，$$ 个盘 $$，$$ 个盘 $$，故 $$. $$

  注：遗留问题：为什么跨两步不能这样：$$ 个盘 $$，$$ 个盘 $$，$$ 个盘 $$，$$ 个盘 $$。这样是 $$. 可以验证答案更差，但是怎样才能避免这样想？

• $$ 种尺寸，第 $$ 种有 $$ 个圆盘，求最少移动次数 $$. $$

平面上的直线

Notes

也是一个经典问题了，一条新的直线和原来的 $$ 条直线最多有 $$ 个交点，就最多增加 $$ 个面。

为什么？注意这条直线被划分成了 $$ 段，每一段两侧是两个现在不同、但是之前相同的面，所以净增加了 $$ 个面。

由此，我们有递归式： $$ 累和，或者数学归纳法，解得： $$

变式

• 把直线改成折线：

  

  注意到，一条折线相当于两条直线相交后抹掉一半，抹掉一半后平面数减 $$，所以 $$.

  可能还是不好理解（至少我理解了很久），这么考虑：新加一条折线进来，从它的顶点向被抹掉的那个方向看去，抹掉的直线本应该把这个区域分成 $$ 部分，但现在它是 $$ 部分，所以少了 $$。

  基于此我们也可以得到递归式：加入新折线的一条边，有 $$ 个新交点，增加 $$ 个面，再加入另一条边，有 $$ 个新交点（包括新折线的顶点），增加 $$ 个面，但是顶点那个交点不争气要减 $$，所以总共新增 $$ 个面，即 $$.

• $$ 字型（两平行半直线加一条直线段）划分平面：沿用上面的思路可得递归式：$$，解得：$$.

• 厚奶酪上划直切痕，得到的三维区域最大个数：新增一个面，前 $$ 个面在这个新平面上最多得到 $$ 个区域，考虑每个区域两侧可以知道新增了 $$ 个块，所以 $$.

  这波降维打击实在有趣！

约瑟夫问题

重点来了！

基础问题

$$ 个人围圈，隔一个死一个，问最后剩下的人的编号 $$.

• 偶数情况：$$ 个人，死了一圈之后，剩下 $$ 个人编号是：$$，这就是个把原编号 $$ 改成 $$ 之后的 $$ 人约瑟夫问题，所以 $$；
• 奇数情况：$$ 个人，死了一圈之后，剩下 $$ 个人编号是：$$，这就是个把原编号 $$ 改成 $$ 之后的 $$ 人约瑟夫问题，所以 $$.

综上，再加上初始条件，有递归式： $$ 至于怎么解这个递归式……我们可以打表（OIer & ACMer 狂喜）：

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
J(n)​	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

观察得到： $$ 或者按书上的写法，是 $$. 证明数学归纳法即可。

二进制视角

这一部分是我觉得最 Amazing 的地方了。

把上表写成二进制：

n​	1	10	11	100	101	110	111	1000	1001	1010	1011	1100	1101	1110	1111	10000
J(n)​	1	1	11	001	011	101	111	0001	0011	0101	0111	1001	1011	1101	1111	00001

发现一个神奇的现象：把 $$ 的二进制向左循环滚动一位，就得到了 $$！

其实看看通项公式，$$ 就是删掉最高位的剩下的部分，乘 $$ 就是左移一位，加一就是把最高位加到最低位去——所以一通操作下来，就是向左循环一位。

如果我们进行套娃式迭代——不停地向左循环，但是注意前导 $$ 会消失掉，所以足够多次迭代下去后得到的数就是由所有 $$ 组成的二进制数，即 $$，其中 $$ 是 $$ 在二进制下 $$ 的个数。

成套方法求解递归式 Repertoire Method

我们把 $$ 的递归式给推广一下： $$ （$$ 是 $$ 的特殊情况）。我们仍然可以打表找规律，但是可以用成套方法（这名字好奇怪）解它。

注意到决定上式结果的是 $$ 个参数 $$，所以我们可以设 $$ 是它的解（充分利用已知条件嘛）。下面我们找 $$ 个特解：

• 令 $$，解得：$$，得到：$$；
• 令 $$，解得：$$，得到：$$；
• 令 $$，有 $$，得到：$$，解得：$$.

联立上述 $$ 式，解得：$$. 所以我们得到了递归式的解： $$ 或者用书上的写法（ $$ ），就是：$$.

有木有感觉很玄学！这三个特解咋冒出来的～特别是第三个特解，好生奇怪！

如果我们把函数 $$ 看作一个向量，那它就是 $$ 的线性组合，我们找到了三个特解，得到线性方程组： $$ 理论上，给定三个线性无关的向量 $$ 和分别对应的的 $$，那么就可以解出 $$。但是问题的关键就在于，任给一个 $$，解 $$ 不一定简单。反过来，给定 $$ 解 $$ 倒是简单，但是给定的 $$ 可能不合法，即根本就不是原递归式的解。所以我感觉这个“成套方法”有很多凑的成分……

推广递归式的进制视角

对于推广的递归式，改写为： $$ 我们用二进制展开： $$ 当然，这里不要求二进制的每一位必须是 $$，而是任意数字都行。

怎么理解？把 $$ 写作二进制，其中 $$ 改成 $$，$$ 改成 $$，最高位改成 $$，就得到了 $$.

我们还可以推广，如果递归式长这样： $$ 那么用 $$ 进制展开： $$ 发现得到一个 $$ 进制结果！实在是妙呀！

习题

• 用成套方法解四参数递归式： $$ 解：设 $$ 是它的解。这是四参数递归式，我们需要找到四个特解。

  • 令 $$，问题转化成了之前解决的问题，有解：$$. 随便取 $$ 个线性无关的 $$，就能确定下 $$；
  • 令 $$，解得：$$，得到：$$.

  于是我们解决了这个问题（虽然没有写出显式的表达式）。

• 用成套方法解五参数递归式： $$ 解：设 $$ 是它的解。这是五参数递归式，我们需要找到五个特解。

  • 令 $$，问题转化成了之前解决的问题，可以确定 $$；
  • 令 $$，解得：$$，得到：$$；
  • 令 $$（注意观察，平方项正好抵消，所以这么设又解），解得：$$，得到：$$.

  联立，问题解决。