Python趣味编程（二）汉诺塔问题（原创）

pengjunling

　　上高中的时候借同学的文曲星玩，对hanoi（汉诺塔）游戏爱不释手。
　　但是没有找到规律，总是蒙出来的。后来大学学递归的时候，觉得是听得最认真的一课。连那个胖胖的小C老师，也那么滴可爱和鲜活起来……
　　最近在教递归函数，也拿过来做例子。
　　先废话一下，不知道什么汉诺塔的同学，请参考以下故事：
　　汉诺塔（又称河内塔）问题是印度的一个古老的传说．传说中，开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆形的金片，最大的
一个在底下，其余一个比一个小，依次叠上去，寺院的僧侣依照一个古老的预言，不知疲倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作
为帮助，但每次只能搬一个，而且大的不能放在小的上面，预言说，当这些金片移动完毕后，世界就会灭亡。
　　Python代码：




1 count = 1
2
3  def test(num, src, dst, rest):
4         global count
5
6         if num < 1:
7                 print False
8         elif num == 1:
9                 print "%d:\t%s -> %s" % (count, src, dst)
10                 count += 1
11         elif num > 1:
12                 test(num - 1, src, rest, dst)
13                 test(1, src, dst, rest)
14                 test(num - 1, rest, dst, src)
15
16
17 test(3, 'A', 'C', 'B')
　　运行结果如下：




1:      A -> C
2:      A -> B
3:      C -> B
4:      A -> C
5:      B -> A
6:      B -> C
7:      A -> C
　　顺便说一句，上面的神话传说是真的。
　　N阶汉诺塔的移动次数公式是：2的N次方减1。
　　所以64阶的汉诺塔，需要移动的次数是18446744073709551615次。
　　假设那庙里的僧侣每秒移一次，不眠不休，得移4000多亿年。地球才46亿年啊大哥……恐龙都灭绝好久了……