汉诺塔的非递归解法
似乎这个问题的最佳解法就是递归，如果你想用栈来消解掉递归达到形式上的消除递归，你还是在使用递归的思想，因此，他本质上还是一个递归的算法。我们这本黄皮书在谈论到“什么情况使用递归”的时候，在“3.问题的解法是递归的”这里面，就这样说了“有些问题只能用递归的方法来解决，一个典型的例子就是汉诺塔”。
但我坚信，如果一个问题能用分析的办法解决——递归实际上就是一个分析解法，能将问题分解成－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）。接下来，我们需要考虑如果发生了阻塞，该怎么办，请继续关注下一期的文章。
保留地址 http://www.qqread.com/cpp/p920596030.html
更多内容请看数据结构、C/C++技术专题、数据结构教程专题，或进入讨论组讨论。
似乎这个问题的最佳解法就是递归，如果你想用栈来消解掉递归达到形式上的消除递归，你还是在使用递归的思想，因此，他本质上还是一个递归的算法。我们这本黄皮书在谈论到“什么情况使用递归”的时候，在“3.问题的解法是递归的”这里面，就这样说了“有些问题只能用递归的方法来解决，一个典型的例子就是汉诺塔”。
但我坚信，如果一个问题能用分析的办法解决——递归实际上就是一个分析解法，能将问题分解成－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）。接下来，我们需要考虑如果发生了阻塞，该怎么办，请继续关注下一期的文章。
保留地址 http://www.qqread.com/cpp/p920596030.html
更多内容请看数据结构、C/C++技术专题、数据结构教程专题，或进入讨论组讨论。
相关图文阅读
频道图文推荐
健 康 咨 询
时 尚 咨 询
相关专题
- 在Ubuntu 7.10中用终端编译运行C++程序 (0次浏览)
- C与C++在Linux下的集成问题 (0次浏览)
- 浅析C++中虚函数的调用及对象内部布局 (0次浏览)
- 在C++中实现四种进程或线程同步互斥的控制 (0次浏览)
- Ubuntu下面的C语言代码检查工具 Splint (0次浏览)
