C++数据结构学习:递归(2-1)

　2008-03-08 21:36:36　来源：WEB开发网　　　

核心提示：　　汉诺塔的非递归解法　　似乎这个问题的最佳解法就是递归，假如你想用栈来消解掉递归达到形式上的消除递归，C++数据结构学习:递归(2-1)，你还是在使用递归的思想，因此，该怎么办，请继续关注下一期的文章，他本质上还是一个递归的算法，我们这本黄皮书在谈论到“什么情况使用递归”的时候

　　汉诺塔的非递归解法

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

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

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

　　显然，我们必须将7号盘子搬到C，在这之前要把6号搬到B，5号就要搬到C，……以此类推，就会得出结论（规律1）：当前柱最上面的盘子的目标柱应该是，从当前柱上“需要搬动的盘子”最下面一个的目标柱，向上交替交换目标柱到它时的目标柱。

　　就是说，假如当前柱是A，需要移动m个盘子，从上面向下数的第m个盘子的目标柱是C，那么最上面的盘子的目标柱就是这样：if (m % 2) 目标和第m个盘子的目标相同（C）;else 目标和第m个盘子的目标不同（B）。接下来，我们需要考虑假如发生了阻塞，该怎么办，请继续关注下一期的文章。