Python ---- 算法入门(3)分治算法解决【汉诺塔】问题

1. 汉诺塔问题起源

汉诺塔问题源自印度一个古老的传说，印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱，其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：

1. 每次只能移动柱子最顶端的一个圆盘；
2. 每个柱子上，小圆盘永远要位于大圆盘之上；

2. 规律分析

为了方便讲解，我们将 3 个柱子分别命名为起始柱、目标柱和辅助柱。实际上，解决汉诺塔问题是有规律可循的：

1. 当起始柱上只有 1 个圆盘时，我们可以很轻易地将它移动到目标柱上；
2. 当起始柱上有 2 个圆盘时： 移动过程是：
   1. 先将起始柱上的 1 个圆盘移动到辅助柱上；
   2. 然后将起始柱上遗留的圆盘移动到目标柱上；
   3. 最后将辅助柱上的圆盘移动到目标柱上。
3. 当起始柱上有 3 个圆盘时，移动过程和 2 个圆盘的情况类似： 移动过程是：
   1. 先将起始柱上的 2 个圆盘移动到辅助柱上；
   2. 然后将起始柱上遗留的圆盘移动到目标柱上；
   3. 最后将辅助柱上的圆盘移动到目标柱上。

3. 规律总结

1. 将起始柱上的 n-1 个圆盘移动到辅助柱上；
2. 将起始柱上遗留的 1 个圆盘移动到目标柱上；
3. 将辅助柱上的所有圆盘移动到目标柱上。

由此，n 个圆盘的汉诺塔问题就简化成了 n-1 个圆盘的汉诺塔问题。按照同样的思路， n-1 个圆盘的汉诺塔问题还可以继续简化，直至简化为移动 3 个甚至更少圆盘的汉诺塔问题。

4. 代码实现

1. count 作为操作第几步得计步器；
2. 通过规律总结，我们知道，当【起始柱】只有一个圆盘得时候，直接将圆盘移动到【目标柱】；
3. 在【起始柱】不知有一个圆盘时，我们就将【N-1】一个圆盘从【起始柱】移动到【辅助柱】上；
4. 记录当前移动步骤；
5. 最后将【辅助柱上】得所有圆盘移动到【目标柱】上。

count = 1
def hanoi(num, sou, tar, aux):
  global count
  # 将【起始柱】 只剩一个圆盘移动到【目标柱】
  if num == 1:
    print("第%d次:从 %c 移动至 %c\n"%(count, sou, tar))
    count = count + 1
  else:
    # 将【起始柱】 n-1 个圆盘移动到【辅助柱】
    hanoi(num - 1, sou, aux, tar)
    print("第%d次:从 %c 移动至 %c\n"%(count, sou, tar))
    count = count + 1
    # 将【辅助柱】 n-1 个圆盘移动到【目标柱】
    hanoi(num - 1, aux, tar, sou)
    

if __name__ == '__main__':
  #以移动 3 个圆盘为例，起始柱、目标柱、辅助柱分别用 甲、乙、丙 表示
  hanoi(3, '甲', '乙', '丙')

5. 以3个圆盘对代码运行流程分析

1. hanoi(3, ‘甲’, ‘乙’, ‘丙’)运行，甲起始柱三个圆盘，由于num = 3；

1. 执行hanoi(num - 1 = 2, sou, aux, tar)【hanoi( 2, 甲, 丙, 乙)】，将第一个圆盘移动到辅助；也就是甲到丙；num=2；

1. 执行hanoi(num - 1 = 1, sou, aux, tar)【hanoi(1, 甲, 乙, 丙)】，注意此时递归到最底层，num == 1的条件满足，执行：print(“第%d次:从 %c 移动至 %c\n”%(count, sou, tar))

此时count=1第一步，sou是甲起始柱，tar是乙目标柱，完成第一次移动！count = count + 1；记录当前步！

6. 移动运行结果