【看这一篇就够了】递归与汉诺塔问题(Hanoi)的超详细算法详解

素颜马尾好姑娘i 2022-05-22 06:46 87阅读 0赞

现有这样一个问题：上帝创造了三根柱子，并在第一根柱子上按顺序套有N个大小不同的圆盘（自下而上，圆盘由大到小，呈金字形）。规定每次只能移动最顶端的一个圆盘，并且保证整个过程中大圆盘不能放在小圆盘之上。欲将所有圆盘从第一根柱子移动到第三根柱子，试给出解决方案。

将三个柱子分别记为A，B，C，原问题可简化为：

将N个大小不同的圆盘由A移动到C，每次只允许移动最顶端的单个圆盘，同一柱子上不得打乱圆盘的原有上下位置。

我们首先来进行如下的分析（多图预警）：

如果只有一个圆盘，那么操作很简单，只需要直接把圆盘自A移动到C，也就是A----->C。

如果有两个圆盘，那么大概就是这个样子：

![70][]

这时候，我们首先把绿圆盘从A移动到B：

![70 1][]

再把紫色圆盘从A移动到C：

![70 2][]

最后再把绿色圆盘移动到C即可：

![70 3][]

就这样，两个圆盘的问题，我们已经解决了。

接下来，我们来研究三个圆盘的情景。

![70 4][]

把红色圆盘移动到C：

![70 5][]

再把绿色圆盘移动到B：

![70 6][]

再把红色圆盘从C移动到B：

![70 7][]

在这里我们先停一下。由之前的几步操作，我们实际上是把A最上面的两个圆盘从A移动到了B。

我们继续移动，把最大的紫色圆盘移动到C：

![70 8][]

我们再停一下，分析一下接下来我们该怎样移动。

从图中我们可以看出，只需要再把B上的两个圆盘移动到C就可以了，如何移动两个圆盘的问题我们是已经解决了的。

也就是：红色移动到A，绿色移动到C，再把A上的红色圆盘移回到C。

就这样，三个圆盘的问题我们已经解决。

圆盘的个数不妨再加一个，这一次我们来研究四个圆盘的情况。

![70 9][]

直接再像原来一样一步步思考如何移动？

其实这里已经没这个必要了：

在之前我们已经解决了三个圆盘的移动问题。

想一想刚刚我们在两个地方“停一下”，忘记了可以再回去看看。

类似于刚刚的情况，我们可以这样处理：

先把A最上面的三个圆盘移动到B，再把A最下面的圆盘移动到C，最后再把已经在B上的三个圆盘移动到C。

就这样，整个问题就解决了。

也就是，我们把整个过程分为三步：

第一步：

![70 10][]

第二步：

![70 11][]

第三步：

![70 12][]

至于具体每一步内的操作如何实现，我们在之前的分析都已经解决了。

也就是，

移动4个圆盘时需要用到移动3个圆盘的操作，

移动3个圆盘时需要用到移动2个圆盘的操作，

移动2个圆盘时需要用到移动1个圆盘的操作，

移动1个圆盘只需要直接一步。

以此类推，对于N个圆盘从A移动到C的问题，

我们只需要先把最上面的N-1个圆盘移动到B，

再把最后一个圆盘移动到C，

最后再把在B上暂存的N-1个圆盘移到C上就可以了。

至于N-1个圆盘怎样移动（从A移动到B），

只需要向前类推，

研究N-2个圆盘的情况，

再向前依次类推，最终推至1个圆盘的情况，

从而问题得到最终解决。

代码如下：

#include <iostream>
    using namespace std;
    void Hanoi(int n, char a, char b, char c) {
    	if(n==1)
    		cout<<a<<"----->"<<c<<endl;
    	else {
    		Hanoi(n-1,a,c,b);
    		Hanoi(1,a,b,c);
    		Hanoi(n-1,b,a,c);
    	}
    }
    int main() {
    	int left;
    	cout<<"请输入A座上盘子的数目：";
    	cin>>left;
    	cout<<"将A座上的"<<left<<"个盘子全部移动到C的步骤为："<<endl;
    	Hanoi(left,'A','B','C');
    	return 0;
    }

需要注意的是，

Hanoi(int n, char a, char b, char c)

这一函数的参数中，

n指需要移动的圆盘数量，

a表示起始位置对应的大写字母，

c表示目标位置对应的大写字母。

举个例子：

Hanoi(n-1,'A','C','B')

这样一行就代表把n-1个圆盘从A移动到B。

Hanoi(n-1,'B','A','C');

这样一行就代表把n-1个圆盘从B移动到C。

递归函数的核心代码只有这三行：

Hanoi(n-1,a,c,b);
    Hanoi(1,a,b,c);
    Hanoi(n-1,b,a,c);

也就是刚刚我们所划分的三大步。

具体是哪三步，在这里就不再重复了。

具体到函数的内部实现，也就是：

函数再次调用函数自身，

继而依次调用一直到n=1，

把我们的三大步依次“分解”为三个步骤，

最终归于n=1的情况，直接解决。

代码敲好了，我们来运行试一下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70 2][]

我们可以看到，仅仅是移动五个圆盘，

就已经需要这么多步了！

如果我们自己一步一步分析，

那会有多么困难！

感谢“递归”，让复杂的汉诺塔问题变得简单。

[70]: /images/20220522/3eab8c390f1743c2a1b43f9123e83666.png
[70 1]: /images/20220522/8e89f7a982e64cf897ca084f79f126aa.png
[70 2]: /images/20220522/611a074d430a4796b452a7e5c073eb46.png
[70 3]: /images/20220522/203495bb29eb4f1ca739260442bda380.png
[70 4]: /images/20220522/313efc0f9fe4423baced6c67e824add8.png
[70 5]: /images/20220522/241ccf1c01734a5fab160f4e42ddc53f.png
[70 6]: /images/20220522/1f1623f318fd48ea95fc0d073a9ec399.png
[70 7]: /images/20220522/1e54d5210a3e401180019d29dd1a25ba.png
[70 8]: /images/20220522/d2f1c76747354285bac655cd96d79c2a.png
[70 9]: /images/20220522/ab3433d74d874a78a8b20e834ac10c1f.png
[70 10]: /images/20220522/c6974fae6c0b4de88f1ee9caf1ce6b4c.png
[70 11]: /images/20220522/d74ba4d477cc4769bb66d2f55173f84c.png
[70 12]: /images/20220522/7dbbc166839a4729bec8606d13b68812.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70]: /images/20220522/67677b4dd7d14c18bcb104209e5ee233.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70 1]: /images/20220522/928eb766685247a8be59287d32fd6e9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70 2]: /images/20220522/eaedfa3addad4c38893d0a5f9bb83c18.png