C++数据结构学习:递归(2-1)
敬业的IT人
互联网
佚名
2008-1-3 19:14:14
访问 汉诺塔的非递归解法
似乎这个问题的最佳解法就是递归，如果你想用栈来消解掉递归达到形式上的消除递归，你还是在使用递归的思想，因此，他本质上还是一个递归的算法。我们这本黄皮书在谈论到“什么情况使用递归”的时候，在“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）。接下来，我们需要考虑如果发生了阻塞，该怎么办，请继续关注下一期的文章。
进入讨论组讨论。
似乎这个问题的最佳解法就是递归，如果你想用栈来消解掉递归达到形式上的消除递归，你还是在使用递归的思想，因此，他本质上还是一个递归的算法。我们这本黄皮书在谈论到“什么情况使用递归”的时候，在“3.问题的解法是递归的”这里面，就这样说了“有些问题只能用递归的方法来解决，一个典型的例子就是汉诺塔”。
- 最新数据结构(试题）习题解答
- 《数据结构》试题下载2004
- 数据结构自测试题(节选章节)
- 2000年试题集锦（下半年）数据结构试
- 《数据结构》教学大纲--入门必看
- 湖南大学2003年数据结构试题
- C++数据结构学习:二叉树(2)
- C++数据结构学习:用栈做表达式求值
- 电信系本科2002级 《数据结构》试题下
- C++数据结构学习:二叉树(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）。接下来，我们需要考虑如果发生了阻塞，该怎么办，请继续关注下一期的文章。
进入讨论组讨论。
- 最新文章
- C++接口概念“方法学”[01-03]
- Microsoft Visual C++Runtime Li..[01-03]
- 深入C++ Builder之编写自己的元件(3)[01-03]
- C++ Builder中各种资源的利用[01-03]
- 利用C++ Builder设计实现文件切割机[01-03]
- 用C++ Builder开发Web程序[01-03]
- 相关文章
