王朝网络
分享
 
 
 

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

王朝c/c++·作者佚名  2008-06-01
宽屏版  字体: |||超大  

汉诺塔的非递归解法

似乎这个问题的最佳解法就是递归,假如你想用栈来消解掉递归达到形式上的消除递归,你还是在使用递归的思想,因此,他本质上还是一个递归的算法。我们这本黄皮书在谈论到“什么情况使用递归”的时候,在“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)。接下来,我们需要考虑假如发生了阻塞,该怎么办,请继续关注下一期的文章。

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
>>返回首页<<
推荐阅读
 
 
频道精选
 
静静地坐在废墟上,四周的荒凉一望无际,忽然觉得,凄凉也很美
© 2005- 王朝网络 版权所有