汉诺塔是经典的递归问题，也有非递归解法，此处只讨论递归解法
1、游戏描述如下：
A、B、C 三个桌子，其中A桌子上放了几个大小不同的盘子，盘子的排列顺序为： 从上到下，依次从小到大递增；现要求把这些盘子从 A 桌子上移动到 C 桌子上，盘子移动时有一点要求：每次移动必须保证三张桌子上大盘子在下、小盘子在上；
2、游戏步骤：
1）当
A上有1个盘子时，只需要将A上的盘子移至C
2）当A上有2个盘子时，将A的1号盘子移动至B，再将A的2号盘子移至C，最后将B上的1号盘子移至C
3）当A上有3个盘子时，先借助C将1、2号盘子从A移至B，然后将3号盘子移动到C，最后借助A将B上的1、2号盘移至C
4）综上可知：当A上有N（N>1）个盘子时，先借助C将A上1至n-1号盘子（共n-1个）移至B，再将A上的n号盘子移至C，最后借助A将B上的n-1个盘子移至C盘。
3、算法描述
美国一位学者发现了一种简单的算法，只需要轮流两步操作就能实现：
首先把三个桌子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在桌子A上，根据圆盘的数量确定桌子的排放顺序：
（1）若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。
（2）按顺时针方向把圆盘1从现在的桌子移动到下一个桌子，即当n为偶数时，若圆盘1在桌子A，则把它移动到B；若圆盘1在桌子B，则把它移动到C；若圆盘1在桌子C，则把它移动到A。
（3）接着，把另外两个桌子上可以移动的圆盘移动到新的桌子上。即把非空桌子上的圆盘移动到空桌子上，当两根桌子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，但是可实施的行动是唯一的。
（4）反复进行（2）（3）操作，最后就能按规定完成汉诺塔的移动。
4、Python代码实现
#!/usr/bin/env python # _*_ coding:utf-8 _*_ def input_n(): while True: n = raw_input(‘请输入A上的盘子个数:‘) try: n = int(n) if n < 1: print ‘请输入大于0的整数!‘ else: break except Exception, e: print ‘请不要随意输入字符!‘ return n def move_info(n, from_table, to_table): step_info = ‘将%s号盘:%s ----> %s‘ % (n, from_table, to_table) return step_info def recursion_hano(n, A, B, C, step_info_list = []): if n == 1: # 当n=1时，直接将盘子移动至目的桌，递归终止条件 step_info_list.append(move_info(1, A, C)) else: recursion_hano(n-1, A, C, B) # 先借助C将A上n-1个盘子移至B step_info_list.append(move_info(n, A, C)) # 将A最后一个盘子移动到C recursion_hano(n-1, B, A, C) # 借助A将B上的n-1个盘子移至C return step_info_list def main(): n = input_n() step_info_list = recursion_hano(n,‘A‘, ‘B‘, ‘C‘) for i,k in enumerate(step_info_list): print ‘第%s步:%s‘ % (i+1, k) if __name__ == ‘__main__‘: main()
5、其他
当盘子为N时，移动次数为 2^N - 1
本文出自 “王潇苒” 博客，请务必保留此出处http://wangxiaoran85.blog.51cto.com/8199070/1717992
原文：http://wangxiaoran85.blog.51cto.com/8199070/1717992