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