1. 汉诺塔问题起源
汉诺塔问题源自印度一个古老的传说，印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱，其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：
- 每次只能移动柱子最顶端的一个圆盘；
- 每个柱子上，小圆盘永远要位于大圆盘之上；
2. 规律分析
为了方便讲解，我们将 3 个柱子分别命名为起始柱、目标柱和辅助柱。实际上，解决汉诺塔问题是有规律可循的：
- 当起始柱上只有 1 个圆盘时，我们可以很轻易地将它移动到目标柱上；
- 当起始柱上有 2 个圆盘时：
移动过程是：
- 先将起始柱上的 1 个圆盘移动到辅助柱上；
- 然后将起始柱上遗留的圆盘移动到目标柱上；
- 最后将辅助柱上的圆盘移动到目标柱上。
- 当起始柱上有 3 个圆盘时，移动过程和 2 个圆盘的情况类似：
移动过程是：
- 先将起始柱上的 2 个圆盘移动到辅助柱上；
- 然后将起始柱上遗留的圆盘移动到目标柱上；
- 最后将辅助柱上的圆盘移动到目标柱上。
3. 规律总结
- 将起始柱上的 n-1 个圆盘移动到辅助柱上；
- 将起始柱上遗留的 1 个圆盘移动到目标柱上；
- 将辅助柱上的所有圆盘移动到目标柱上。
由此，n 个圆盘的汉诺塔问题就简化成了 n-1 个圆盘的汉诺塔问题。按照同样的思路， n-1 个圆盘的汉诺塔问题还可以继续简化，直至简化为移动 3 个甚至更少圆盘的汉诺塔问题。
4. 代码实现
- count 作为操作第几步得计步器；
- 通过规律总结，我们知道，当【起始柱】只有一个圆盘得时候，直接将圆盘移动到【目标柱】；
- 在【起始柱】不知有一个圆盘时，我们就将【N-1】一个圆盘从【起始柱】移动到【辅助柱】上；
- 记录当前移动步骤；
- 最后将【辅助柱上】得所有圆盘移动到【目标柱】上。
count = 1
def hanoi(num, sou, tar, aux):
global count
# 将【起始柱】 只剩一个圆盘移动到【目标柱】
if num == 1:
print("第%d次:从 %c 移动至 %cn"%(count, sou, tar))
count = count 1
else:
# 将【起始柱】 n-1 个圆盘移动到【辅助柱】
hanoi(num - 1, sou, aux, tar)
print("第%d次:从 %c 移动至 %cn"%(count, sou, tar))
count = count 1
# 将【辅助柱】 n-1 个圆盘移动到【目标柱】
hanoi(num - 1, aux, tar, sou)
if __name__ == '__main__':
#以移动 3 个圆盘为例，起始柱、目标柱、辅助柱分别用 甲、乙、丙 表示
hanoi(3, '甲', '乙', '丙')5. 以3个圆盘对代码运行流程分析
- hanoi(3, ‘甲’, ‘乙’, ‘丙’)运行，甲起始柱三个圆盘，由于num = 3；
- 执行hanoi(num - 1 = 2, sou, aux, tar)【hanoi( 2, 甲, 丙, 乙)】，将第一个圆盘移动到辅助；也就是甲到丙；num=2；
- 执行hanoi(num - 1 = 1, sou, aux, tar)【hanoi(1, 甲, 乙, 丙)】，注意此时递归到最底层，num == 1的条件满足，执行：print(“第%d次:从 %c 移动至 %cn”%(count, sou, tar))
此时count=1第一步，sou是甲起始柱，tar是乙目标柱，完成第一次移动！count = count 1；记录当前步！
6. 移动运行结果
