如何理解汉诺塔的递归?

学C++ 递归篇 看懂了斐波那契序列的递归 但是却死也看不懂移动汉诺塔 主要问题有两个 怎么把一个大的移动问题分解成三部分?而这三部分恰好是要递归的三步递归的三步如何完美的控制(明明三步中嵌套两步 思维乱死了)
关注者
376
被浏览
77517

45 个回答

拿以前写的一篇文作为回答吧。

-


懒汉式递归——瞬间明白汉诺塔问题


Q. 为什么会有递归?
A. 因为我们是人,不是电脑!我们的working memory有限!

游戏规则:

有A,B,C三根针,将A针上N个从小到大叠放的盘子移动到C针,一次只能移动一个,不重复移动,小盘子必须在大盘子上面。


问题:

总的移动次数是多少?


分析:

首先明确,我们的目标是将A针上所有N个盘子移动至C针。而对于B针,我们可以将之看成一个中转站。

这个问题,顺向思维或者逆向思维道理是相同的,都太麻烦。我们不妨从中间开始思考。

||: 规则要求小盘子必须在大盘子之上。试想这个过程中,必然会经历那么一个步骤,即有一大坨N-1个盘子在B针这个中转站,而我们正将最大那个盘子(即第N个盘子)从A针移动至C针。


【图例】


只有经历“移动最大盘子”这个步骤,余下的事情才有可能实现。而在此之前,我们所要做的事情,就是让“移动最大盘子”这个步骤得以实现。

现在,游戏整个过程以“移动最大盘子”为中央,被分为了两部分。即(前)“将那坨N-1个盘子从A针移动到B针”,(中)“移动最大盘子”,(后)“将坨N-1个盘子从B针移动到C针”。

这是我们意识到,(前)与(后)操作道理是相似的。不去管那个最大盘子,(前)是以C针为中转站,(后)是以A针为中转站。因此两者所需的移动次数应当是相等的。这意味着我们只要计算出其中一者的移动次数,然而乘以2,在加上“移动最大盘子”的那1次,就是这场游戏的总移动次数了。

用数学语言表达,假设(前)“将N-1个盘子从A针移动到B针”所需次数为Hn-1,总移动次数为Hn,那么可以得出的关系就是:Hn=Hn-1 x 2 + 1.

其实当我们得出这个算式的时候,稍微聪明一点的人已经明白,这就是一个递推公式,可以直接用此公式得出Hn的通解。

但是LZ比较笨,就是不明白,为什么这个公式就可以套用呢?

那么就干脆继续思考吧。

让我们再想象一个情景:最大那个盘子在刚刚从A针被移动到C针,而那坨N-1个盘子还在B针蠢蠢欲动地等待着,即处于(中)->(后)的这个状态。

怎么移动这N-1个盘子呢?

其实这时候,问题已经回到了笔者标示“||:”符号的地方。“||:”是乐谱中的反复记号,而我们要做的,就是重复上面的步骤,但是要将N替换为N-1,因为现在只剩下N-1个盘子需要移动。而中转站则从B变成了A(鉴于这时盘子都在B针)。目标仍然是C针。下一次重复的时候,只剩下N-2个盘子需要移动,中转站又回到A,目标不变仍然是C针。……整个过程中,变化的只是中转站(在A与B之间轮换),以及剩下那些所需要移动的盘子的总数(越来越少)而已。

那么那个大盘子怎么办?不去管它吗??

正解!!

因为你已经把它移到C针,已经完成了这个移动步骤,它不会影响之后的操作。提醒自己牢记游戏规则,大盘子永远在小盘子下面,而你也不需要再重复移动它——“不重复移动”,正是游戏规则的要求!

于是 Hn=Hn-1 x 2 + 1 这个公式,就可以套用、套用、套用……直到H3=7,H2=3,H1=1。

最后,用最懒的数学归纳法证明通项公式 Hn = 2^n - 1 吧!没办法,LZ就是比较懒嘛~


Fin.

我觉得这样理解最高分的答案会比较简单(粗暴)~

一个环:
Step1.将最大的环从A移动到C
A -> C

两个环:
Step1.把除了最大的环之外的环,从A移动到B
A -> B
Step2.将最大的环从A移动到C
A -> C
Step3.把除了最大的环之外的环,从B移动到C
B -> C

三个环:
Step1.把除了最大的环之外的环,从A移动到B
A -> C
A -> B
C -> B
Step2.将最大的环从A移动到C
A -> C
Step3.把除了最大的环之外的环,从B移动到C
B -> A
B -> C
A -> C

所以其实是这样抽象成三个步骤的~
这个时候,可以放张图了
(a)是初始状态,也就是递归的起点,我们假设n=4, move(4,A,B,C)还是请参考现在最高的分的代码哈~写这个是帮助大家更清楚那个让人压力大的(“抽象”)两个字,哈哈
<这个函数要实现的功能是把n个环从A按照一定的规则,借助B,移动到C>
(b)是step1完成的时候的状态,已经将所有的n-1,这里也就是3个环从A挪到了B
<第一处递归,move(n-1,A,C,B) 这个函数要实现将n-1个环从A,借助C,移动到B>
(c)是step2,此时需要将第n个,也就是第四个最大的环从A挪到C
<move(1,A,B,C),或者干脆直接print("A -> C")>
(d)是step3,此时需要将B上面的n-1个环从B挪到C<第二处递归>
<第二处递归,move(n-1,B,A,C) 这个函数要实现将n-1个环从B,借助A,移动到C>
Over~