`
xitong
  • 浏览: 6157233 次
文章分类
社区版块
存档分类
最新评论

汉诺塔递归解法

 
阅读更多

汉诺塔的递归算法


假设有3个分别命名为X、Y和Z的塔座,在塔座X上插有n个直径大小各不相同、依小到大编号为1、2…n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排,圆盘移动时必须遵守下列规则:
1、每次只能移动一个圆盘;
2、圆盘可以插在X、Y和Z中任一塔座上;
3、任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。



递归算法的思路:
当n=1时,问题比较简单,只要将编号为1的圆盘从塔座X直接移至塔座Z上即可。
当n>1时,需利用塔座Y作辅助塔座,若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座X移至塔座Y上,则可先将编号为n的圆盘从塔座X移至塔座Z上,然后再将塔座Y上的n-1个圆盘移至塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题,只是问题的规模小1,因此可以用同样的方法求解。

//从src移动第m个圆盘到dest底座上
void move(char src, int m, char dest){
	cout<<"the disk "<<m<<" is moved from src "
		<<src<<" to dest "<<dest<<endl;
}

//汉诺塔解法,将n个圆盘由x盘移动到z盘,y盘为辅助盘
void hanoi(int n, char x, char y, char z){
	if(n==1)move(x,1,z);
	else{
		hanoi(n-1, x,z,y);
		move(x,n,z);
		hanoi(n-1, y,x,z);
	}
}

int main(){
	hanoi(3,'x','y','z');
	return 0;
}

结果:

the disk 1 is moved from src x to dest z
the disk 2 is moved from src x to dest y
the disk 1 is moved from src z to dest y
the disk 3 is moved from src x to dest z
the disk 1 is moved from src y to dest x
the disk 2 is moved from src y to dest z
the disk 1 is moved from src x to dest z
分享到:
评论

相关推荐

    汉诺塔(河内塔)非递归解法

    汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得...

    C++编写汉诺塔的非递归解法

    C++编写汉诺塔的非递归解法,可直接运行 有文档解释.

    汉诺塔图形解法(递归算法)

    汉诺塔的图形演示 将递归可视化 利用了字符进行界面设计

    汉诺塔问题c++递归解法

    汉诺塔问题c++递归解法

    C++汉诺塔问题解法

    用递归 解决了N个盘子的汉诺塔问题 适合新手

    用递归实现汉诺塔的解法

    //注意递归就是调用本身,所以本身算一次,调用本身也算一次 ,这是易错点 //递归这里是A-&gt;C,A-&gt;B,B-&gt;C

    基础算法-python汉诺塔解法

    解法:汉诺塔问题的解法可以使用递归算法来实现。具体步骤如下: # 当只有一个圆盘时,直接将该圆盘从A柱移动到C柱即可。 # 当有n个圆盘时,将前n-1个圆盘从A柱移动到B柱,再将第n个圆盘从A柱移动到C柱,最后将前n...

    汉诺塔解法

    自定义汉诺塔解法,自动执行,含显示过程,新手教学用,理解递归算法

    c++编写的汉诺塔程序

    很俗的程序……输出n级汉诺塔的解法,利用递归。基本上每本程序书上都有的例子。我当初学的时候实验的程序。

    汇编语言-汉诺塔

    hanoi,汉诺塔问题,汇编语言经典解法,利用递归调用,经典

    汉诺塔vc++ 面向对象编程课程作业

    汉诺塔问题,是一个非常经典的运用递归算法实现的问题。虽然也有非递归的算法可以使用,并且非递归的算法可以节省很大的预算量,但是在本程序中,我还是选择了传统的递归算法。 为了描述问题的某一状态,必须用到它...

    递归应用C语言实现

    包含多个经典的递归应用代码: ...2.hanoi.c 是汉诺塔递归算法 3.permutation.c 是全排列递归算法 4.queen.c 是八皇后递归算法 5. reverse.c 是递归的测试代码 6.strlrn.c 是求字符串长度的递归算法

    数据结构与算法综合资料库.CHM

    汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 五例 排序算法一览 穷举密码算法 如何实现DES算法 入栈与出栈的所有...

    数据结构与算法综合资料库

    汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 五例 排序算法一览 穷举密码算法 如何实现DES算法 入栈与出栈的所有...

    数据结构及算法编程(阿蒙工作室)

    ☆ 汉诺塔的非递归 ☆ 何谓数据结构 ☆ 回朔法一例 ☆ 几道有趣的算法题 ☆ 阶梯问题的递归解法 ☆ 精确迭代法 ☆ 矩阵求逆的快速算法 ☆ 快 速 排 序 ☆ 马踏棋盘问题 ☆ 冒 泡 法 ☆ 排序算法 五例 ☆ 排序算法...

    day018-File类代码以及笔记.rar

    (汉诺塔问题) 这类问题虽则本身没有明显的递归结构,但用递归求解比迭代求解更简单,如Hanoi问题。 (3)数据的结构形式是按递归定义的。 如二叉树、广义表等,由于结构本身固有的递归特性,则它们的...

Global site tag (gtag.js) - Google Analytics