话不多说,上代码

1 def hanoi_move(n, source, dest, intermediate):
2 if n >= 1: # 递归出口,只剩一个盘子
3 hanoi_move(n-1, source, intermediate, dest)
4 print("Move %s -> %s" % (source, dest))
5 hanoi_move(n-1, intermediate, dest, source)

首先我们这里有三根杆子依次排放,分别是 源杆、媒介杆、目标杆 对应 代码的 source、dest、intermediate,源杆上有n块大饼

我们定义一个函数 def hanoi(n,源杆,目标杆,媒介杆):# 意思是源杆 借助 媒介杆 到 目标杆

  我们假设除了底下最后一层上面的n-1层都已经摆放好了,即源杆上目前只有两块大饼,我们要执行的操作是:

  源杆上的n-1层 借助 目标杆 到 媒介杆 等同于 hanoi(n-1,源杆,媒介杆,目标杆)相当于n-1层在媒介杆上了

  打印 源杆 到 目标杆 显示路径

  再把媒介杆的n-1层 借助 源杆 到 目标杆 等同于 hanoi(n-1,媒介杆,目标杆,源杆)

再来说说为什么假设n-1层的,因为我们在假设n-1层的时候使用了递归,在hanoi(n-1…)的时候我们就是假设n-2层已经摆放好了,然后就是在hanoi(n-2…)的时候我们假设n-3层已经摆放好了,不断回溯,就到了最上面一层已经摆放好了,这个假设是合理的,既可以使用该方法。使用了递归的回溯思想,如果使用递归思想不断地推出他的步骤那基本是不可能的,然而通过前提不断地假设反而更容易拿到结果。

04-28 22:15