如何理解汉诺塔的递归?

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

66 个回答

2017.11.13 校对说明:

才发现题主想问的是编程……这是笔者以前写的一篇文章,纯粹解释汉诺塔的数学问题,没有直接给出编程方案,获得最高赞数也是很醉……总之能够帮到大家理解就好,具体的编程可以参考其他答主的答案。

-


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

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个盘子需要移动,中转站又回到B,目标不变仍然是C针。……整个过程中,变化的只是中转站(在A与B之间轮换),以及剩下那些所需要移动的盘子的总数(越来越少)而已。

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

正解!!

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

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

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

Fin.

汉诺塔的话Concrete Mathematics第一章就讲了,我觉得讲得挺好。汉诺塔的话代码不难写,正确性也不难证明,稍微麻烦一点的是证明这是最小步数。第一章还讲了recurrance。记得把题也做了。不理解递归可以好好刷刷数学归纳法。

当然写到代码用到递归就得刷调用栈,栈帧,了解下calling convention。这个随便研究下就行了,弄gdb单步调试调试,打出backtrace看看。

数学归纳法和调用栈都了解之后递归就不是玄学了。

别人已经讲了 F(n) = 2 F(n-1) + 1,F(1) = 1 的各种来历和打印方式,我也不赘述了。

----------------- 为什么 F(n) = 2 F(n-1) + 1,F(1) = 1 是最优的 -----------------

其实用数学归纳法就行了。

最基本的情况,即n为1,就不用说了。

现在F(n-1)确实是把n-1个盘子集体挪动的最小步数,我们要证明F(n)是把n个盘子集体挪动的最小步数。

1)在把n个盘子从A移动到C的过程中,必然存在一步,是把最大的盘子从A拿出来。要想把最大的盘子从A移动到别的某个柱子上(B或C),就必须保证剩下的n-1个盘子不能碍事,得好好堆在剩下那个柱子(C或B)上。要保证n-1个盘子都在剩下那个柱子上,至少得付出F(n-1)次移动。

2)在把n个盘子从A移动到C的过程中,必然存在一步,是最大的盘子被放到了C上,而且此后再也没动过。在这步实行之前,最大的盘子要么在A要么在B上,而相应地别的n-1个盘子要么在B要么在A上。在这步实施之后,我们只要花至少F(n-1)的步数把n-1个盘子从要么B要么A挪动到C上就行了。这些步数必然和1)中的步数不重叠,因为这时候最大盘子在C上,而1)中最大盘子在A上。

3)最大的盘子至少被挪动了一次。而且这一次肯定没被算在1)或2)的“至少F(n-1)步”中,因为后者只挪动较小的那n-1个盘子。

把1),2),3)加起来,就是至少F(n-1) + F(n-1) + 1步。不能再少了。