第1章 递归问题
-
河内塔
设
表示移动n个盘的步数，则：
可以这么解释：先移动顶上的n-1个盘子，再移动最大的那个。接下来把顶上n-1个盘子移动到最大的上面。
- 约瑟夫问题
在看这部分之前，我只会模拟。没想到它的推算还是蛮易懂的。
可以设n个人的情况下，J(n)可以存活。则如果将n扩大一倍至2n的话，那么经过一轮将偶数全部解决掉以后，剩下的情况与n个人的情况是一样的，只是序号不一样。由此可以获得递推关系：
奇数情况下，剩下n个人的时候，序号分别是3,5,7...2n+1，设原序号为x'，现在的序号为x，则x'=2x+1，这样可以获得递推关系：
偶数的情况同理，结果是
可以获得递推关系：
再去对前几项找找规律，可以发现：
就是将n拆成二进制，两部分：最高位10..0以及剩余的部分。结果是剩余的部分左移＋１，和循环左移位结果相同，是个巧合。
书中的例子并没有严格求解，可以如下求解：
{10}\=(1100100){2}\=(1000000){2}+(100100){2}\=(100100){2} << 1 + 1\=(1001001){2}\=(73)_{10})
