汉诺塔问题（递归与非递归）_汉诺塔非递归算法

汉诺塔问题（递归与非递归）

问题描述如下

​ 相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

以上内容引用自百度百科“汉诺塔问题”

https://baike.baidu.com/item/汉诺塔问题/1945186?fr=aladdin

这是一个经典的问题，普遍采用递归的解法来处理。

这里整理出递归与非递归两种解法，仅供参考。

递归

首先我们知道递归的设计方法：

 1. 找重复（子问题）  
 2. 找重复中的变化量（参数）   
 3. 找参数变化趋势（出口）
1
2
3

那么如何使用上述方法来设计汉诺塔（Hanoi）问题的递归解法呢？

我们可以先从简单的例子开始： 设层数为N，要把所有的盘子从 A 移动到 C 。

当 N = 1 时：直接把盘子从 A 移动到 C 即可。

当 N = 2 时：虽然没有像 N = 1时那么浅显，但是还是比较容易想到的。

当 N = 3 时：大家可以自己手动模拟一下应该怎么移动，这个时候就感觉有点吃力了，移动过程参考如下。

当 N = 4， N = 5， N = …… 时：什么？感觉脑子要炸了，不想算了？确实，我也一样，我们来研究一下上面的例子看看有什么规律。

这是在 N = 3 情况下的最后一步，如果丢给你这样一个局面，你是不是立刻就可以通过把 A 移动到 C 来得到正确的结果。

这跟 N = 1 情况是一致的，为什么？

表面上 C 柱上有两个盘子似乎和 N = 1 的情况是不一样的，但是这两块盘子都比 A 柱上的盘子来得大，所以对于要移动的盘子来说根本没有影响，可以直接忽略掉，相当于 C 柱上面没有盘子。

因此，我们可以知道，N = 1 实际上是一个出口，也就是递归的出口。

接下来我们来比对一下 N = 2 和 N = 3 的对应状态：

左边是 N = 2 的完整步骤，右边是 N = 3 的部分状态截图，是不是觉着两种情况有相似之处？

是的，我们只要把 N = 3 中圈出来的两块盘子当做是一个整体，那么还原的步骤就跟 N = 2 的情况是一致的。

那其他的情况也是这样的吗？举个例子， N = 4 。

由此可知，不论 N 有多大，我们都可以依据这样的策略来得到解决。

而其中又包含了许多的重复子问题，重复在哪儿呢？

例如上图的第一步，将 1~3 个盘子从 A 移动到 B，这实际上是跟 N = 3 的情况是相同的，只不过是目标的柱子换了一个罢了。

在 N = 3 情况中，要把盘子从 A 移动到 C，使用 B 作为辅助；上面的情况中，要把盘子从 A 移动到 B，使用 C 作为辅助。

而在 N = 3 的情况中又包含了 N = 2 的情况，N = 2 的情况又包含了 N = 1 的情况…

那么这些重复子问题中是什么参数在变化呢？就是 A 、B、C 三个柱子上的盘子数量。

有了递归设计的三要素，那么我们就可以顺利设计出递归的函数，以下的 Hano 函数仅供参考。

void printHano(int n, string from, string to, string help){
	if(n == 1){
		cout << "move " << n << " from " << from << " to " << to << endl;
	}
	else{
		printHano(n-1, from, help, to);
		cout << "move " << n << " from " << from << " to " << to << endl;
		printHano(n-1, help, to, from);
	}
}
1
2
3
4
5
6
7
8
9
10

还可以这么写：

int hano(int n){
	if(n == 1) return 1;
	return 2*hano(n-1)+1;
}
1
2
3
4

实际上 printHano(n-1, from, help, to) 和 printHano(n-1, help, to, from) 是相同的问题，可以合并。

而每一次递归都要移动一个盘子，因此需要 +1。

时间复杂度为 O(2^n)。

接下来插入一个对于汉诺塔问题错误的递归思路来比对：

​ 先把第一个盘子移动到 B 柱，再把剩下 2~N 个盘子移动到 C 柱，最后把 B 柱上的盘子移动到 C 柱上。

​ 这样好像也是一种 “整体” 的思想，但是好像哪里有错？

​ 把第一个盘子移动到 B 柱是没有问题的，但是要把 2~N 个盘子从 A 柱移动到 C 柱，这种情况下做得到吗？

​ 无论如何都做不到。因为现在 B 柱上已经有一个最小的盘子，任何盘子都不能放在上面。

​ 也就是说 B 柱这种局面下是不能当做辅助的柱子的，而原问题中是可以使用辅助柱子的。

​ 这就违背了递归的子问题的要求（规模更小，性质相同）中的性质相同，因此是不可行的。

个人对于递归的理解：

​ 如果在知道可能要使用递归来解决问题的时候，一定要有整体的概念！

​ 递归是电脑特有的，人脑可能没有办法想通的事情，电脑会帮助你忠实地一步一步完成。

​ 电脑呈现给你的是一个答案（前提是你是否想好了当前局面的解决方法与子局面的解决方法是不是一样的，并且设计了递归的出口）。

​ 这样的话，可能会更好的帮助你设计出正确的递归解法。

————————————————————————————————————————————

非递归

非递归的解法比递归的解法还要难想，因此使用的人很少。

参考书籍《图解算法》 俞征武 著

以 N = 3 的情况为例子进行说明：

​ 由前面的讨论可以知道 N = 3 的汉诺塔需要 2^3-1 = 7 次移动，我们使用表格来展示。

似乎还是看不出有什么规律？再换一种表示方法。

再试试 N = 4 的情况。

观察出规律了吗？

​ ① 好像 1 号盘子出现在奇数的搬动次数上？

​ 可是 2 号没有这个现象？

​ 好像 2 号盘子隔 4 次才搬动一次。

​ 好像 3 号盘子隔 8 次才出现一次。

​ 好像 k 号盘子每隔 2^k 次搬动一次。

​ ② 可以知道第 i 步骤搬动第几号盘子吗？

​ 第 1，3，5，7，9，11，13，15 步搬动 1 号盘子。

​ 第 2，6，10，14 步搬动 2 号盘子。

​ 第 4 和 12 步搬动 3 号盘子。

​ 第 8 步搬动 4 号盘子。

​ 可能和这些数字的因子为 2 的倍数有关？

​ 当进行第 i 步时，找出最大的 k 使得 i = 2^k * z （z 为正整数）。

​ 因此，在第 i 步时，搬动 k+1 号盘子。

​ ③ 那么每次搬动盘子的方向知道了吗？

​ 我们来观察 1 号盘子的移动方向：

​ 好像每次移动到最顶端就掉下来了？

​ 再试着观察 2 号和 3 号盘子的移动方向？

​ 2 号盘子每次移动到最低端就跳上去了。

​ 3 号盘子的移动方向和 1 号相同。

​ 奇数号盘子搬动的方向一致。

​ 那么偶数号盘子呢？来观察：

​ 偶数号盘子的搬动方式一致，但是方向正好相反。

​ ④ 是否其他的例子也是这样？

​ 当 N 为奇数时，好像整个搬动方向全部相反。

​ 当汉诺塔问题的盘子数是奇数时，奇数号盘子往下移动倒地后，就跳上去；

​ 而偶数号盘子往上移动到顶后，就掉下来。

讨论至此，下面给出汉诺塔问题非递归解法的算法：

【END】感谢观看