对汉诺塔问题的一点理解
Topic source首先,我们考虑n为1的情况,也即仅有A柱有一个圆盘的情况: 此时我们只需要做到将A柱上的圆盘移动到C柱上即可,我们用下面这条语句来表示这个过程,这就是我们的递归基础;
# n == 1
print(a, '-->', c)
其次,我们来考虑n为2的情况,这个时候A柱上从上到下有一小一大两个圆盘,我们需要做的是先借助C柱,将小盘移动到B柱,然后就回到了n为1的情况了,这时我们只需要和之前一样,将A柱上的
圆盘移动到C柱上即可,移动的过程如下:
# n == 2
a -> b
a -> c
b -> c
下面,我们来思考n为3的情况,这个时候A柱上从上到下有小中大三个圆盘,从这个时候开始我们要引入抽象的概念,将小盘和中盘视作一个整体,我们现在所需要的是将这个整体借助C柱,移动到B柱上,然后我们就有一次回到了n为1的情况了,本次移动过程如下:
# n == 3
a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c
大家可以发现,当n为3时,步骤以及比较多了,但还是可以用大脑(或手和笔)去跟踪函数运行每一步的执行的,但当n更大时呢(比如5):
# n == 5
a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c
a --> b
c --> b
c --> a
b --> a
c --> b
a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c
b --> a
c --> b
c --> a
b --> a
b --> c
a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c
如果我们继续用大脑(或手和笔)去跟踪函数运行每一步的执行,我们很难保证一步不错地跟下来。
汉诺塔(递归问题)的关键就在于放弃我们让大脑(或用手和笔)去跟踪函数运行每一步的执行的习惯,利用用抽象和自动化的思想解决问题。
事实上,我们总能将A柱最底层的圆盘上面的n-1个圆盘抽象为一个整体,然后借助C柱将其转移到B柱上,然后我们就回归到了n为1的情况了,这时我们只需要和之前一样,将A柱上的一个圆盘移动到C柱上即可;然后,对于此时在B柱上的n-1个圆盘,我们又可以将最底层的圆盘上面的n-2个圆盘抽象为一个整体,借助C柱将其移动到A柱,然后将最底层的圆盘从B柱移动的C柱上,这个时候,那n-2个圆盘又可以继续如上操作;综上所述,我们顺着这个思路,可以发现,我们总有办法将初始柱上的n-1个圆盘,借助目的柱而移动到中间柱上,进而我们就回到了最简单的n为1的情况。
最后,我们来看一下完整的程序
# -*- coding: utf-8 -*-
def hanoi(n, a, b, c):
# 当n为1时 (递归基础)
if n == 1:
print(a, '-->', c) # 将A柱最底层的圆盘移动到C柱
# 当n大于1时
else:
hanoi(n-1, a, c, b) # 借助C柱,将n-1个圆盘从A柱移动到B柱
print(a, '-->', c) # 将A柱最底层的圆盘移动到C柱
hanoi(n-1, b, a, c) # 借助A柱,将n-1个圆盘从B柱移动到C柱
#调用hanoi函数,这里设置了n为5的情况
hanoi(5, 'a', 'b', 'c')
大功告成!
Congratulations !
YANGZY1202
# 汉诺塔(递归问题)的关键就在于放弃我们让大脑(或用手和笔)去跟踪函数运行每一步的执行的习惯,利用用抽象和自动化的思想解决问题。
# 汉诺塔是一个非常好的帮助我们从传统的数学思维转变到计算思维的小问题,汉诺塔问题让我第一次认识到计算机/算法的神奇和魅力所在!