数据结构学习（C++）——递归【2】（1）

作者： happycock

汉诺塔的非递归解法

（真的很抱歉，由于CSDN能贴的长度有限，所以分成了4部分，让您麻烦了。——我用表格拼成的盘子，导致HTML代码数量激增，虽然看起来不长，但是实际上相当的长。）

似乎这个问题的最佳解法就是递归，如果你想用栈来消解掉递归达到形式上的消除递归，你还是在使用递归的思想，因此，他本质上还是一个递归的算法。我们这本黄皮书在谈论到“什么情况使用递归”的时候，在“3.问题的解法是递归的”这里面，就这样说了“有些问题只能用递归的方法来解决，一个典型的例子就是汉诺塔”。

但我坚信，如果一个问题能用分析的办法解决——递归实际上就是一个分析解法，能将问题分解成－1规模的同等问题和移动一个盘子，如果这样分解下去一定会有解，最后分解到移动1号盘子，问题就解决了——那么我也应该能用综合的办法解决，就是从当前的状态来确定怎样移动，而不是逆推得到决定。这是对实际工作过程的一个模拟，试想如果让我们去搬盘子，我们肯定不会用递归来思考现在应该怎么搬——只要8个盘子，我们脑子里的“工作栈”恐怕就要溢出了——我们要立即决定怎么搬，而不是从多少步之后的情景来知道怎么搬。下面我们通过模拟人的正向思维来寻找这个解法。

假设如下搬7个盘子的初始状态（选用7个是因为我曾经写出了一个1～6结果正确的算法，而在7个的时候才发现一个条件的选择错误，具体大家自己尝试吧），我们唯一的选择就是搬动1号盘子，但是我们的问题是向B搬还是向C搬？

1
2
3
4
5
6
7
	A	B	C

显然，我们必须将7号盘子搬到C，在这之前要把6号搬到B，5号就要搬到C，……以此类推，就会得出结论（规律1）：当前柱最上面的盘子的目标柱应该是，从当前柱上“需要搬动的盘子”最下面一个的目标柱，向上交替交换目标柱到它时的目标柱。就是说，如果当前柱是A，需要移动m个盘子，从上面向下数的第m个盘子的目标柱是C，那么最上面的盘子的目标柱就是这样：if (m % 2) 目标和第m个盘子的目标相同（C）;else 目标和第m个盘子的目标不同（B）。接下来，我们需要考虑如果发生了阻塞，该怎么办，如下所示：

返回顶部

下一篇：数据结构学习（C++）——递归【2】（2） >>