汉诺塔的传说
相传在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
算法分析
该问题实际上是一个非常典型的迭代问题，所谓迭代问题就是原问题拆分的子问题实质上仍然是原问题，此外，每个迭代问题都应该有一个base case，即在此情况下停止迭代。
用迭代的角度来看汉诺塔问题：
- 把n个金片从第一个银针上全部转移到第三个银针上的操作定义为函数Transfer(n,start=1,end=3)。
- 把n-1个金片从第一个银针上全部转移到第三个银针上为函数Transfer(n-1,start=1,end=3)。
- Transfer(n-1,start=1,end=3)与Transfer(n,start=1,end=3)属于一类问题。
- Transfer(n,start=1,end=2)与Transfer(n-1,start=1,end=3)有联系，即在n-1个金片全部从第一根到第三根后，只需将第n个金片从第一根转移到第二根，然后再把其他的n-1个金片放到它上面，即发生了Transfer(n-1,start=3,end=2)，最后得到Transfer(n,start=1,end=2)。
- Base case就是n=1时，直接将n=1的金片从1移到3.
Python代码实现
def Transfer(n,start=1,end=3):
if n:
Transfer(n-1,start,6-start-end) # 将n-1个金片从start转移到6-start-end
print('Move disk %d from rod %d to rod %d '%(n, start,end))
Transfer(n-1,6-start-end,end)# 将n-1个金片从6-start-end转移到end
output:
Transfer(3)
Move disk 1 from rod 1 to rod 3
Move disk 2 from rod 1 to rod 2
Move disk 1 from rod 3 to rod 3
Move disk 3 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 1
Move disk 2 from rod 2 to rod 3
Move disk 1 from rod 1 to rod 3
Transfer(4)
Move disk 1 from rod 1 to rod 2
Move disk 2 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 3
Move disk 3 from rod 1 to rod 2
Move disk 1 from rod 3 to rod 0
Move disk 2 from rod 3 to rod 3
Move disk 1 from rod 0 to rod 3
Move disk 4 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 3
Move disk 2 from rod 2 to rod 1
Move disk 1 from rod 3 to rod 3
Move disk 3 from rod 2 to rod 3
Move disk 1 from rod 1 to rod 2
Move disk 2 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 3
需要注意几点：
- 将n-1个金片从start转移到6-start-end，这里start不能用1代替，因为在迭代中start是动态变动的，而end=6-start-end则是动态的表示是除了start和end外的宝石针，6=1+2+3。
- 在将n-1个金片全部转移到6-start-end后，将第n个金片转移到end，因此可以用print输出此时是将哪个金片从哪里移动到哪里，也可以理解为此时将第n个金片移动到了end。
- print输出后（将第n个金片移动到了end后）,将n-1个金片从6-start-end转移到既定的end。