最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
汉诺塔非递归算法实现例子
时间:2022-06-25 08:02:38 编辑:袖梨 来源:一聚教程网
最近的算法课,讲到了递归与分治策略,书上递归的例子是很经典的汉诺塔问题。问题大意是有三个塔座,分别为a,b,c,开始时塔座a上叠有n个圆盘,这些圆盘自上而下,由小到大地叠放在一起,各圆盘从小到大编号为1到n。要求将塔座a上的圆盘移动到塔座b上,并且在移动时每次只能移动一个圆盘,且每个塔座上的圆盘都必须保持自上而下、由小到大的排列顺序。
本文不涉及对非递归算法的数学性证明,若想理解非递归算法的道理,下面的就不用看啦。
递归的解法就不再说了,这里谈一下非递归的解法。教科书上对于非递归解法是这样描述的:
假设塔座a,b,c排成一个三角形,a->b->c->a构成一顺时针循环,在移动圆盘的过程中,若是奇数次移动,则将最小的圆盘移到顺时针方向的下一塔座;若是偶数次移动,则保持最小的圆盘不动,而在其他两个塔座之间,将较小的圆盘移到另一塔座上去。
在这里我们默认塔座a是初始圆盘放置的塔座,塔座b是圆盘需要移到的目标塔座,塔座c是目标塔座,n是初始的圆盘数量。经过个人编码验证,证实书上说的有一点不妥,正确的说法是:
当n是奇数时,塔座按a->b->c->a排列,而当n是偶数时,塔座应该按a->c->b->a排列。
自己编码之前,也上网看过别人写的代码,自己都不是很喜欢,定义了各种复杂的结构体还有函数等,于是自己写了一个c++版本的,只用到了vector这一种数据结构,不过由于都写在一个hanoi函数体内,关于打印信息方面可能处理的不是很好,显得程序有点冗长,但整体结构还是挺清晰的。代码如下:
代码如下 | 复制代码 |
void hanoi(int n) { if(iter % 2) { // odd plate move if(n%2) { // different n, different messages if(n%2) { // different n, different messages |
上面代码的5,6两行定义的两个vector是用于打印信息的时候用的,当n是奇数时,就采用odd里面的顺序,n是偶数时,就采用even里面的顺序,所有打印处理信息的时候要考虑到n的奇偶性,显得打印信息那几块地方比较罗嗦。记录每个塔座上的圆盘信息只用了一个二维vector tower,初始化的时候tower[0],即塔座a上面自下而上从大到小放置了n个圆盘。
然后就进入循环了,由于n的奇偶问题,所以终结循环的判定条件也有两种,在第17、18行。进入循环分成两大块,即判定当前移动次数是奇数次还是偶数次,如果是奇数次,就执行22行开始的代码,将标号为1的圆盘顺时针移动到下一个塔座,要考虑n的奇偶性不同带来的顺时针顺序不同的问题;如果是偶数次,就执行46行开始的代码,保持最小的圆盘不动,移动另外两个塔座上较小的圆盘到另一个塔座,这里要判定一下这两个塔座其中是否不存在圆盘,同样的还是要考虑n的奇偶性带来的顺时针顺序不同的问题。
后面进行一些改进
代码如下 | 复制代码 |
#include const int MAX = 64; void hanoi(int n) { if(iter % 2) { // odd plate move if(n%2) { // different n, different messages if(n%2) { // different n, different messages int main() { |
相关文章
- 世界之外易遇生日活动怎么玩 12-23
- 无期迷途空条徐伦什么时候复刻 12-23
- 无期迷途黛伦蝶之影怎么样 12-23
- 无期迷途空条承太郎什么时候up 12-23
- 无期迷途艾梅斯怎么样 12-23
- 阴阳师小袖之手幽篁流影怎么样 12-23