第一章:递归问题

热身题

[1.2] 汉诺塔问题,将圆盘从A移动到C,但是必须经过B,求最短的移动序列。

  1. 假设将圆盘从A移动到C需要T(n)次移动
  2. 当只有一个圆盘的时候,明显有T(1)=2 (先移动到B再移动到C,故这里需要2步)。
  3. 可以手工计算出当有2个圆盘的时候需要进行8次移动,好吧,我承认当有3个圆盘的时候我手工算起来已经很累的,无法想象有4个圆盘的时候计算量会有多少。
  4. 由于手工计算量实在太大,我们需要考虑的是是不是有其他的方法可以让我们把问题简化,或者说抽象话。通过归纳法我们知道可以通过研究T(n)和T(n-1)之间的关系来找到规律。为了更好的理解,我们画个图先。图片1
  5. 当需要移动第n个圆盘的时候那么n-1一个圆盘是必须在C柱上的图1(因为第n个圆盘必须先移动到B柱),那么很容易就看出来在移动第n个圆盘之前已经移动了T(n-1)步。
  6. 从图上我们可以看出来T(n) = T(n-1) + 1 + T(n-1) + 1 + T(n-1) = 3T(n-1)+2
  7. 等式2边加1我们可以得到 T(n) = 3(T(n-1) + 1) - 1,到这里我们已经离答案很近了,让我们继续带入T(n-2)看一下会有什么变化
  8. T(n) = 3(3(T(n-2) + 1 ) -1 + 1) - 1整理一下我们可以得到 $$T(n) = {3}^{2}(T(n-2)+1)-1$$,那么继续我们就可以得到$$T(n) = {3}^{n-1}(T(1)+1)-1$$ 由于T(1)=2代入上以后为$$T(n)={3}^{n-1}(2+1)-1 = {3}^{n}-1$$
  9. 所以本题的解为$$T(n)={3}^{n}-1$$