您小时候玩过汉诺塔吗？有没有手忙脚乱，晕头转向的赶脚？
汉诺塔（Tower of Hanoi）源于印度的古老传说：大梵天创造世界的时候做了三根金刚石柱子，其中一根柱子自下而上按大小顺序摞着64个黄金圆盘。大梵天命令婆罗门把圆盘按大小顺序重新摆放到另一根柱子上，并且规定，大圆盘不能放小圆盘上，三根柱子之间一次只能移动一个圆盘。
如此这般，得移动多少次呢？
和汉诺塔故事相似的，还有另外一个印度传说 ：舍罕王打算奖赏国际象棋的发明人──宰相西萨·班·达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。
如果数字限制了我们的想象力，那让我们化繁为简，先从简单的做起，由此发现其中的规律。
1个圆盘的时候移动1次；
2个圆盘的时候移动3次；
3个圆盘的时候……
让我们看一下动图：
结果为7次，也即3个圆盘重新摞在一起需要的次数为7；
4个圆盘时，其上面3个圆盘如此这般摞在一起仍旧要用7次，再如此这般挪动到之前挪动到空白柱子的第四个圆盘上还要7次，因此其需要的总次数就是：
“3个圆盘重新摞在一起的次数”+1次+“3个圆盘重新摞在一起需要的次数”
=2x“3个圆盘重新摞在一起的次数”+1次
=15次。
……
可见，n个圆盘时搬动的次数是2x“（n-1）个圆盘重新摞在一起的次数”+1次。由于1 个圆盘的时候是1次，n个圆盘的时候则为（2^n-1）次。
汉诺塔是典型的递归问题，其可演示移动过程的代码如下：
#汉诺塔（假设圆盘由小到大编号为1->N）
n=eval(input('请输入圆盘数：'))
count=0
def hanoi(n,sp,ep,bu): #sp:start point; ep:end point; bu:buffer
global count
if n==1:
print('{}号：{}->{}'.format(1,sp,ep))
count+=1
else:
hanoi(n-1,sp,bu,ep)
print('{}号：{}->{}'.format(n,sp,ep))
hanoi(n-1,bu,ep,sp)
count+=1
hanoi(n, 'A', 'C', 'B') #相应柱子标记为A，C，B
print('需要移动{}次'.format(count))
以3个圆盘为例，移动过程为：
以递归函数呈现的 python 代码则为：
n=eval(input('请输入圆盘的数目：'))
def f(n):
if n==1:
return 1
else:
return 2*f(n-1)+1
print('需要移动',f(n),'次')
回到题头，当圆盘数为64时，需要移动的次数为：18,446,744,073,709,551,615！如果移动一次需要1秒，那需要的时间简直不可想象！！！
如果您一定要问我是多久，⊙▂⊙，大约是天荒地老吧……
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/106991.html
