文档中给出输入塔的数目以及每步操作;
数学归纳法:
一个盘子的话,一次就OK,记A1=1
两个盘子,分三步:
1.将B最上面的一个盘子移到C上,就个就是上面一个盘子的情况,即A1次
2.将B最下面的盘子移到A上,一次就好。
3.将C的所有盘子(1个),移到A上面,即A1次。
也就是A2=2A1+1=3 =2^2-1
三个盘子,分三步:
1.将B最上面的两个盘子移到C上,即A2次
2.将B最下面的盘子移到A上,一次就好。
3.将C上面的两个盘子,移到A上,即A2次。
也就是A3=2A2+1=7=2^3-1
同理,n个盘子的情况:
1.将B上面的n-1个盘子移到C上,即An-1次
2.将B最下面的盘子,移到A上,一次就好
3.将C上面的两个盘子,移到A上,即An-1次
也就是An=2An-1 +1=2^n-1