WEB开发网
开发学院软件开发C++ C++数据结构学习:递归(2-1) 阅读

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)。接下来,我们需要考虑假如发生了阻塞,该怎么办,请继续关注下一期的文章。
更多文章 更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

Tags:数据结构 学习 递归

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接