mooc学习：迭代法求递推方程

迭代法就是不断用方程的右部替换方程的左部，每次替换，随着n的降低在和式中多出一项，直到出现初值为止，然后代入初值求解。

我们以经典的汉诺塔问题为例：

汉诺塔问题描述

假设有n个盘子在a上，最优的移动方法就是先把上面的n-1个盘子先移到b上，然后将a中剩余的第n个盘子移到c上，然后剩下的n-1个盘子重复上面的步骤。

我们的伪码是：

算法Hanoi(A,C,n)//n个盘子从a到c

1、if(n==1) then move(A,C)

2、else hanoi(A,B,n-1)

 3、move(A,C)

4、hanoi(B,C,n-1)

我们设n个盘子的移动次数为T(n)，则

T(n)=2T(n-1)+1

T(1)=1

现在我们用迭代法。

T(n)=2T(n-1)+1

      =2[2T(n-2)+1]+1

      =2^2T(n-2)+2+1

不断替换至n=1时，便可求出递推公式

2^n-1