汉诺塔移动次数
发布网友
发布时间：2023-05-04 05:39
共1个回答
热心网友
时间：2023-10-25 10:55
汉诺塔：
三个柱子：A,B,C，A有n个环，讲n个环全部移动到C上，要求：
1> 移动次数最少；
2> 大环不能放在小环上。
如果有n个盘的话，那么移动次数为 2n-1
具体证明如下
对于一个单独的塔，可以进行以下操作：
1：将最下方的塔的上方的所有塔移动到过渡柱子
2：将底塔移动到目标柱子
3：将过渡柱子上的其他塔移动到目标柱子
可以归纳出第一步与第三步的步数是一样的，设为a
则总步数为2a+1
详细说明：
假如说有n个盘子要挪A(n)步,那么有n+1个盘子可以先通过A(n)步把上面的n个盘子挪到第三个柱子上,再挪最大的盘子,最后把n个盘子挪到大的上面,共2A(n)+1步,所以A(n+1)=2An+1
A(n)=2A(n-1)+1
最后可算得A(n)是2n-1
