加载中...
坨——理解递归实现“汉诺塔”代码的关键
第1节:代码改善:一个“坑爹”的文字类冒险游戏
第2节:在禁止多重继承的情况下,如何设计“直立智慧猩猩”类?
第3节:C++多线程代码中的“乱序”执行现象
第4节:C++中函数指针有什么作用呢?
第5节:为什么我用c++写的游戏那么简陋?
第6节:多线程读写socket导致的数据混乱的原因是什么?
第7节:WebSocket 是什么原理?为什么可以实现持久连接?
第8节:怎样在c++中实现instanceof?
第9节:一个函数多处 return 是好风格吗?
第10节:C++中虚函数相比非虚函数的优势
第11节:为什么 C::C::C::C::foo() 能编译成功?
第12节:如何静态反射C++枚举的名字
第13节:看C++大叔如何拥 java 妹子入怀……
第14节:坨——理解递归实现“汉诺塔”代码的关键
第15节:C++编译器如何实现 const(常量)?
第16节:C++如何为断言加上消息
第17节:初学C++到什么水平,算是合格的初级开发工程师?
第18节:C++编程要避免使用单例模式吗?
第19节:学习C++要学boost库吗?
第20节:C++的继承就是复制吗?
第21节:C++构造函数失败,如何中止创建对象?
第22节:C++学完多线程后,学什么呢?
第23节:string_view 适合用做函数的返回值类型吗?
第24节:为指针取别名,为何影响const属性?
第25节:std::enable_shared_from_this 的存在意义?
第26节:C++模板可变参数如何一次性解包?
第27节:Linux下的c++开发,平时是怎么调试代码的呢?
课文封面

“汉诺塔”问题是计算机编程遇到递归时,最经典的练习题;然而不管是在校时,还是毕业后,许多同学遇到这个问题时,仍然哀嚎一片。本质是对“递归”的不理解。
如果你正在学习递归,快来上这堂课。这又是一篇作者在知乎的倍好好评的回复(甚至有知乎用户读完后主动联系作者要付费打赏)

汉诺塔玩具

递归为难了多少人?

我记得,大学学C语言时,在函数递归调用那一节有个作业,就是写汉诺塔。不少同学遭遇到困难。在知乎上遇见的就有: 如何理解诺塔的递归?

该知乎用户发出“悲鸣”:“……学C++递归篇 看懂了斐波那契序列的递归 但是却死也看不懂移动汉诺塔……”

还有:如果看不懂汉诺塔的递归逻辑,是不是可以放弃学习编程了?

这位朋友似乎更“惨烈”,因为他仿佛被为难到怀疑起人生:“……是不是可以放弃学习编程了…?!”。虽然他学的是Python,但语言在这里与问题无关,问题还是出在对递归的理解上,还是卡在汉诺塔这个实例上。

再如:无法理解汉诺塔问题的递归,是不是与编程无缘了?

呀,可不要轻易说和编程无缘,有时你只时差一说得相对清楚的文章而已。

来看看知乎网友的反馈:

知乎评论

第一招:粗暴代入最简数据——从两层塔的找规律

类似提问还有不少,而且每个问题下都有许多回答,很多图文并茂,讲得认真仔细。不过,我会觉得,如果无法把这问题极大的“本质简单化”,怕是回答越长,读起来越是“好像懂了点……自己再要想,又糊了”。

参加过信奥之类比赛的同学,肯定都知道暂无思路时的一个"土"、或称为“粗暴”但有效方法:先用简单的数据走一遍。我们也来从两层的塔看起:

代入2层的数据

想把A柱上套着的两层“盘”按“汉诺塔”要求挪到C柱。大的思路就是:

第一步:把2号盘挪到C柱;第二步:再把1号套上去,一切OK。

可是,2号盘头上顶着1号盘,2号盘取不出来呀?那我们再增一个过渡步骤吧:把2号盘头上的1号盘取出来套到中间的B柱上,不就得了?所以,现在的思路是三步解决:

  • 第一步:把 2号盘 头上的 1号盘,挪到 中间柱子 上;
  • 第二步:把 2号盘 挪到 目标柱 上;
  • 第三步:把(现在)位于 中间柱子 上的 1号盘,挪到 目标柱 上。

大功告成!现在,无论是理论层面,还是实践层面,我们都非常擅长玩2层的汉诺塔了。

不过,如何把这2层玩法的经验推广到更多层呢?对一个老程序员来,这太简单了;对于一个新程序员来,这也很简单,只要听老程序员一说,就一准学会:

我们要把前面(简化数据后观察到的)具体经验中的所有实际对象,抽象一下,就可以了。

第二招:基于最简单规律抽象

上面经验中,有这么些个实际对象:“2号盘”、“1号盘” 和 “中间柱子”、“目标柱” 等等。如果你没注意到,请现在抬头再往上看看。

1. 先来抽象 “2号盘”

试想,如果是套三层,它就该是3号盘了,如果是四层,它就是4号盘了,怎么办?好办呀,它其实是指“最底下的盘”呀,简称"底盘"——这就是幼儿园小朋友的抽象(这是真的,我家就读大班的小朋友,在我问他的思路时,他就是这么描述这个对象的)。

抽象到这层面已经非常够用了,唯一不足就是无法体现我们是大学生在数学知识上的优势,为此,我们可以这样抽象(并没有更好用):设有N层,则称最底下(也是最大的)那个盘,为N号盘。

2. 再来抽象 “1号盘”

有2号盘作基础,这回我们长话短说:“1号盘”可以抽象为:最底下的盘之上的所有盘。而由于这个术语有些长,所以我决定把它也称为“底盘上的那一坨”,有时也会进一步简化为:“那一坨”,特别是当底盘已经挪走后。

为什么是“所有盘”?以初始局面为例:当有三层时,那么在最大的盘(3号)的头上,难道不是2号和1号两(多)张盘吗?

这里我的五岁儿子说的“最底下盘之上的所有盘”,也可说为:N号盘上面的所有编号必然小于N的盘。同样以初始化局面为例,则为 N-1到1号盘(不一定连续)。

3. 最后抽象 “中间柱子”

这里很容易误解为:中间柱子就是A,B,C中间的 B柱。其实在后续步骤中,那可不一定。应该说,如果你在某一步骤时,想把某根柱子上“最底下的盘”挪到另一根柱子上,则称“最底下的盘”所在的柱子,为当前步骤的“源柱”,“最底下的盘”想挪至的那根柱子,称为“目标柱”,则自然有:余下的那根柱子称为“中间柱”(或者叫 过渡柱)。

第三招:把术语代入实际步骤

抽象完成,将抽象后的术语代入前面的三个步骤,得到:

  • 第一步:把当前 源柱上 的 底盘上那一坨 ,挪到 中间柱子;
  • 第二步:把当前 源柱上的底盘挪到目标柱;
  • 第三步:把当前 中间柱子上的那一坨,挪到目标柱。

现在,我们已经掌握挪N层塔(盘)的抽象理论了,“学霸们”都知道,此时应该用这个理论,倒过来套一个具体事物,加以验证,以保正确:那我们来套一个3层的:

三层汉诺塔

具体实践:

  • 第一步:先把那一坨(1号与2号盘)挪到中间柱;
  • 第二步:再把底盘(3号盘)挪到目标柱;
  • 第三步:最后,把已经在中间柱上的那一坨(1号与2号盘)挪到目标柱。

非常简单!以至于我夹起人造革的包差点就想走出教室了。然后有学生叫住我,指出疑问:

第一步是违规的:不允许将多张盘(也就是老师您说的“坨”)一次性挪到另一根柱子;同理第三步也是违规的。

好,那我们就来谈谈,如何把那一坨盘(1号和2号)从源柱移到中间柱。

好,那我们就来谈谈,如何把那一坨盘(1号和2号)从源柱移到中间柱。

等等!

两张盘!从一个柱挪到另一个柱子,并且一样拥有另一根柱做中间柱子——这不就是我们一开始就搞定的事吗?

在本文开始不久,你就已经(从理论和实践上)完全掌握:

把A柱上的1号和2号盘,以B柱为中间柱,挪到C柱;

现在,你哪有可能,竟然不会下面这道题:

把A柱上的1号和2号盘,以C柱为中间柱,挪到B柱?

注意两个问题的不同,就是目标柱和中间柱做了对调而已。再看第三步。请设想1号和2盘已经叠在B柱上,所以第三步的目标就是:

把B柱上的1号盘和2号盘,以A柱为中间柱,挪到C柱。

显然,这次是 源柱和中间柱做了对调 而已。

所以,无论是第一步,还是第三步,你都可以完成的,至于第二步,它已经是最简化的一步了——别说用手,就是用嘴叼,我也能轻松将某个底盘,从一根柱子上叨出来,再套放到另一根上面去。(画面好像有些H)

第四招:归纳、拔高,找出解题本质

真正的重点,我家小朋友无法理解,只有正在学编程的你才能听懂的道理马上要来了……

让我们先理一理:

  1. 为了把3张盘从A挪到C……
  2. 我们得先将上面的2张盘从A挪到B……
  3. 而为了将2张盘从A挪到B……
  4. 我们得先将上面的1张盘,从A挪到C……
  5. 而为了将1张盘从A挪到C……
  6. 我们必须学会直立行走,从而将上肢演化发育为手;实在没手的话,嘴巴灵活一些也不是不可以……

忽略上面的第6点。看前面1到5,你发现没有:先是3张盘,发现一步解决不了,于是处理最底下的第3张盘上面的2张盘;但还是无法一步处理,于是处理2张盘上面的1张盘……于是,竟然解决了。

这就是递归——为了解决 第N个问题,需要先解决第N-1的问题,而为了解决N-1的问题,需要先解决第N-2个问题,直到解决第1个问题。而且在这其中,前面第N、第N-1、直至倒数第2个问题的解决算法,都是一致的。

什么代码都没有,你说个球?!

核心代码思路

1. 关键函数说明

1.1 top 函数

假设我有一个函数叫“top()”,当调用 top(Src) 时,它可以取到源柱(入参Src)最顶上那个盘的编号,但并不代表真的将这个盘从柱子上取出来。(原谅我中STL毒太深,显然直接取出来也能解决问题)

1.2 pop 函数

假设我有一个函数叫“pop()”,当调用 pop(Src) 时,它可以把柱子最上面的那个盘,取出来。

1.3 push 函数

假设我有一个函数叫 “push()”,当调用 push(Dst, number) 时,它可以将编号为 number 的盘子,套到目标柱上(入参Dst)。

上面以源柱和目标柱为例,实际上也有可能往中间柱上套盘子。假设以“Tmp”代表中间柱,那么当你看到 push (Tmp, 4) 时,你应该能懂,这是在把 4 号盘套到 中间柱子上。

1.4 核心操作:用 move 函数实现移动一坨

最后,假设我用 “pile” 这个单词来表达 “坨”;那么,万事具备,只欠这么一个用以表达及实现“移动”的函数了:

// 示意算法,类C的伪代码: move (pile, Src, Tmp, Dst) { ……在这里,把 pile 层的一坨盘子,从 Src柱,经由 Tmp柱,移到 Dst柱上…… }

这个move 怎么实现呢?当然是先实现用嘴叼都可以做的事——也就是pile为1时的情况:

// 关键的移盘函数,暂时只能挪一层的情况: move (pile, Src, Tmp, Dst) { if (pile == 1) // 只有一层,用不到 Tmp { number = top(Src); //读到源柱上(唯一1层)盘的号码 pop(Src); //从源柱上取出 push(Dst, number); //把number号盘,套到目标柱上去。 return; } .... }

正如注释所说,仅有一层的情况下,直接从源柱取出来,再套进目标柱就可以了,Tmp在这种情况下没有用处。

那 pile 多于1,比如2层、3 层、4层呢?前面说了半天的结论呀,不怕麻烦,别骂我啰嗦(我的白话C++那么厚的原因,因为就是面对新人),再来看一次步骤的当下的演化:

  • 第一步:先把底盘上 的 pile - 1 层那一“”,从当前源柱经由目标柱,移动到中间柱

这里“经由目标柱,移到中间柱”,有些绕? 这是因为,我们此时是在 “pile”层的操作之下,要实现将其上的 pile-1 层的挪走。针对 当前的 pile时,可能C柱是目标,B柱是中间柱。但是,在移动 pile-1层,C柱成了中间柱,B柱才是目标柱。

所以,这一步,用 move 表达,就是:

/* step1: 把底盘上那一坨,挪到中间柱 */ move ( pile -1, /* 底盘上的那一坨 */, Src, /* 源柱还是源柱 */ Dst, /* 处理pile层时的目标柱却成了处理pipe-1层的中间柱Tmp */ Tmp, /* 而处理pile层时的中间柱,成了 pipe-1 层时目标柱 */ );
  • 第二步:把底盘,挪到目标柱

因为只有一层,所以此时pile为1 进入move后,会走中间柱没有用的那个 if 分支。

/* step2: 把 底盘,挪到目标柱 */ move ( 1, // 只剩底盘,所以pile为1,进入函数会走前面已实现的那个if分支 Src, Tmp, Dst );
  • 第三步:把现在位于中间柱那一坨 (pile - 1),经由源柱移动到目标柱
/* step3: 把中间柱上的 那一坨, 经由源柱,移动 目标柱上 */ move (pile - 1, // 那一坨 Tmp, // 位于中间柱上 Src, // 经由源柱... Dst // 挪到目标柱上去 );

只要是大于一层,就走上面那三步,所以现在move的实现是:

// 关键的移盘函数,可以移任意盘数了: move (pile, Src, Tmp, Dst) { if (pile == 1) // 只有一层,用不到 Tmp { number = top(Src); //读到源柱上(唯一1层)盘的号码 pop(Src); //从源柱上取出来 push(Dst); //套到目标柱上去。 return; } // 2层,或2层以上,全部是三步解决: move(pile - 1, Src, Dst, Tmp); // 先把一坨, 经由Dst,移到 Tmp move(1, Src, Tmp, Dst); // 再把余下的一层(底盘),经由Tmp,移到Dst move(pile - 1, Tmp, Src, Dst); // 最后,把位于中间柱子上的一坨,经由Src,移到Dst }

核心功能完事!

更多实现细节

这种题目,通常会给出一个最大层数限制。此处假设是10层。因为是纯C风格(通用C和C++的作业),所以给一个宏来表达这10层:

#define MAX_LEVEL 10

这种题目搞无限层是没有意义的——因为它根本无关算法的核心,要实现也不难,就是改为动态分配内存而已。

我们用:

int numbers[MAX_LEVEL];

来存储某一根柱子的可能套着的盘(存的是盘的编号:最小的盘叫1号,次小的是2号……)。不过,我们有三根柱子,所以同样以纯C代码来定义一个柱子的结构体:

typedef struct { int index; int numbers[MAX_LEVEL]; int count; } Column; /* 柱子 */

三个成员,解释如下:

  • index: 前面我们称A柱、B柱、C柱……听起来像是在谈汽车,所以实际我们用的是:柱1,柱2、柱3——事实上,不需要这个号也可以解决问题,只是我们为了方便在输出信息时,带上柱子的编号。这样显然会直观很多;
  • numbers[MAX_LEVEL]:核心数据,前面解释过了,请参看下一条关于 count 的解释;
  • count: 表示本柱子当前实际套了几层盘子。

注意一个纯粹是实现上的细节:假设一个柱子套满10个盘,那么 numbers[0]是10,numbers[1] 是9,numbers[2] 是8 ……numbers[9] 是1。也就是说我把较大盘子的编号,存储在 numbers中索引较小的位置上。

在移动的过程,同一根柱子上套着的盘子的编号,很可能不是连续的。比如,有一根柱子上面可能在某一时刻,套着 1号、5号和7号三张盘,那么,它的numbers存储的情况是:numbers[0]为7,numbers[1]为5,numbers[2]为1,即:[7, 5, 1, 0, 0, 0, 0, 0, 0, 0]。

为了直观,我还给出一个 “draw(Column* 柱子)”的函数,它可以画出指定柱子上的所有盘。draw()会调用draw_cell(),后者用于实际画一个盘子,这里我很合情合理地偷懒了:我只输出盘子的编号(“仿真”的画法,应该是画出盘子的大小)。

但仍然是一个讲究的人,所以我给所有编号加了一对小翅膀 (大雾)。

以三层汉诺塔的前两步为例,画出来的样子如下:

三层塔前两步模拟输出

图中表达的,就是把柱1顶部的01号盘子,移动柱3。

如果,你认真研究前面的三步,你可以计算出对于 pile 层的塔,完成移动需要 2的pile次方减1步。比如,3层,就是 8-1,计7步。但这是我们人脑计算的,程序里我们让它每当走一步前面提到的“pile == 1”的分支时,就增加一次步骤。我用一个全局变量 steps 来计数。

程序有两种编译结果,代表两种运行方法,一种是全速运行,迅速给出答案;另一种是一步步演示,当你看明白某一步后,按下回车键后,(代码里不小心写成 “任意键”……)再继续下一步。代码用一个宏来区分编译:

#define STEPPING 1 // 非0编译为单步演示,为0表示全速演示

可以了吧,这样一个带有步骤输出、单步、全速双模式演示功能,兼容C/C++作业要求的汉诺塔,不用1000行,不用500行,甚至不用200行,给出来在下面了。文末还有可以在线运行演示的链接。

完整代码及在线运行

#include <stdio.h> #define STEPPING 1 // 非0编译为单步演示,为0表示全速演示 #define MAX_LEVEL 10 // 最大层数 typedef struct { int index; int numbers[MAX_LEVEL]; int count; } Column; Column A, B, C; // 三个柱子 int steps; // 用来累计步骤 // 初始化三根柱子,A柱将作为起始的源柱, // 其上套好了由入参 levels_count 指定层数的盘子 void init(int levels_count) { steps = 0; A.count = B.count = C.count = 0; A.index = 1; B.index = 2; C.index = 3; for (int number = levels_count; number > 0; --number) { A.numbers[A.count] = number; A.count++; B.numbers[number] = C.numbers[number] = 0; //B,C柱填0(本行删除估计也没影响) } } int top(Column* src) { return src->numbers[src->count - 1]; } void push(Column *dst, int number) { dst->numbers[dst->count] = number; ++dst->count; } void pop(Column *src) { src->numbers[src->count - 1] = 0; --src->count; } void draw_cell(int number) { if (number > 0) { printf("\t~%02d~\t\t|", number); } else { printf("\t \t\t|"); } } void draw() { int row_count = A.count; if (row_count < B.count) { row_count = B.count; } if (row_count < C.count) { row_count = C.count; } for (int i=row_count-1; i >= 0; --i) { draw_cell(A.numbers[i]); draw_cell(B.numbers[i]); draw_cell(C.numbers[i]); printf("\n"); } printf("\t----------------------------------------------\n"); } void move(int pile, Column *src, Column *tmp, Column *dst) { if (pile == 1) { int number = top(src); printf("\n第%d步:(%d号盘) 柱%d ==> 柱%d\n" , ++steps, number, src->index, dst->index); #if STEPPING printf("按任意键执行...\n"); getchar(); #endif pop(src); push(dst, number); draw(); return; } move(pile - 1, src, dst, tmp); move(1, src, tmp, dst); move(pile - 1, tmp, src, dst); } int main() { int levels = 0; printf("请输入汉诺塔共几层(1~10):"); scanf("%d", &levels); if (levels <= 0 || levels > 10) { printf("非法的层数:%d。", levels); return -1; } getchar(); init(levels); printf("初始状态:\n"); draw(); move(levels, &A, &B, &C); printf("\n======[大功告成]=======\n"); printf("[%d层]汉诺塔移动完成,共%d步。\n", levels, steps); return 0; }

在线运行(时间长了后,链接可能会失效):

汉诺塔程序在线运行 (onlinegdb)