c语言编写汉诺塔函数 汉诺塔循环求解C语言
C语言汉诺塔
要看懂递归程序,往往应先从最简单情况看起。
成都创新互联-专业网站定制、快速模板网站建设、高性价比海西网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式海西网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖海西地区。费用合理售后完善,十载实体公司更值得信赖。
先看hanoi(1, one, two, three)的情况。这时直接将one柱上的一个盘子搬到three柱上。注意,这里one柱或three柱到底是A、B还是C并不重要,要记住的是函数第二个参数代表的柱上的一个盘被搬到第四个参数代表的柱上。为方便,将这个动作记为:
one =》three
再看hanoi(2, one, two, three)的情况。考虑到hanoi(1)的情况已经分析过了,可知这时实际上将产生三个动作,分别是:
one =》two
one =》three
two =》three
很显然,这实际上相当于将one柱上的两个盘直接搬到three柱上。
再看hanoi(3, one, two, three)的情况。分析
hanoi(2, one , three, two)
one =》three
hanoi(2, two, one, three)
即:先将one柱上的两个盘搬到two柱上,再将one柱上的一个盘搬到three柱上,最后再将two柱上的两个盘搬到three柱上。这不就等于将one柱上的三个盘直接搬到three柱上吗?
运用归纳法可知,对任意n,
hanoi(n-1, one , three, two)
one =》three
hanoi(n-1, two, one, three)
就是先将one柱上的n-1个盘搬到two柱上,再将one柱上的一个盘搬到three柱上,最后再将two柱上的n-1个盘搬到three柱上。这就是我们所需要的结果!
C语言汉诺塔程序
将以下内容全部复制到新建的源文件中:(本人自己写的,因为你那课本上的代码,没解释,书写不规范,很难理解清楚,所以我直接新写了一个完整的代码,附带详细说明)
#include stdio.h
//汉诺塔x层塔从A塔整体搬到C塔,中间临时B塔。
//x层塔是从大到小往上叠放。每次移动只能移动一层塔。并且在移动过程中必须保证小层在上边
//借助B塔可以将x层塔全部从A搬到C上,并且符合要求(在移动过程中大的那块在下边,小的那块在上边)
int main()
{
void tower(int x,char a,char b,char c); //声明函数
int x=5,a='A',b='B',c='C'; //x表示有5层塔,具体要多少层自己修改这个值。abc分别表示ABC塔。
tower(x,a,b,c); //x层塔从a移动到c的全过程,主程序只有这条有效语句
return 0;
}
//以下是tower函数的定义
//参数解析:x层塔放在a上,b是中间塔,c是目标塔。即x层塔要从a搬到c上。
//此函数实现x层塔从a整体转移到c上。以及这个过程是怎么搬的全部过程。
void tower(int x,char a,char b,char c)
{
if(x==1)printf("将%d从%c放到%c\n",x,a,c); //只有1层塔时,直接从a搬到c上。
else //不止1层塔,则先将x-1层塔从a按照规律搬到b上,再将最后一块从a搬到c上,最后再将b上的x-1层塔按照规律搬到c上。
{
tower(x-1,a,c,b); //先将x-1层塔从a按照规律搬到b上,注意参数b放在最后,因为放在最后的参数是准备搬过去的目标塔。
printf("将%d从%c放到%c\n",x,a,c); //将最后一块从a搬到c上
tower(x-1,b,a,c); //最后再将b上的x-1层塔按照规律搬到c上,注意参数b放在开头,因为x-1层是要从b上搬过去的。
}
}
c语言用递归实现汉诺塔
见代码注释,还有不懂可以问。
#include stdio.h
void move(char x,char y)
{
printf("%c--%c\n",x,y);
}
//hannuota函数的作用:把n个圆盘从one柱子借助two柱子放到three柱子
void hannuota(int n,char one,char two,char three)
{
if(n==1)//如果只有一个柱子
move(one,three);//直接移动即可
else
{
hannuota(n-1,one,three,two);//先把one柱子上的n-1个圆盘借助three柱子移动到柱子two
move(one,three);//把第一个柱子的剩下那一个(第n个)移动到第三个柱子
//由于原来one柱子上的n-1个圆盘已经移动到了two柱子上,因此不会有圆盘挡住n圆盘出来
hannuota(n-1,two,one,three);
//最后再把那n-1个圆盘从two柱子借助one柱子移动到three柱子
//(上面第一句话hannuota(n-1,one,three,two)已经移动到了two柱子,因此这里是从two柱子移动到three柱子)
}
}
int main()
{
int m;
printf("input the number of diskes:");
scanf("%d",m);
printf("The step to move %d diskes:\n",m);
hannuota(m,'A','B','C');
return 0;
}
用C语言代码来编写含汉诺塔问题,利用堆栈来实现.求代码
算法思想
对于汉诺塔问题,当只移动一个圆盘时,直接将圆盘从 A 针移动到 C 针。若移动的圆盘为 n(n1),则分成几步走:把 (n-1) 个圆盘从 A 针移动到 B 针(借助 C 针);A 针上的最后一个圆盘移动到 C 针;B 针上的 (n-1) 个圆盘移动到 C 针(借助 A 针)。每做一遍,移动的圆盘少一个,逐次递减,最后当 n 为 1 时,完成整个移动过程。
因此,解决汉诺塔问题可设计一个递归函数,利用递归实现圆盘的整个移动过程,问题的解决过程是对实际操作的模拟。
程序代码
#include stdio.h
int main()
{
int hanoi(int,char,char,char);
int n,counter;
printf("Input the number of diskes:");
scanf("%d",n);
printf("\n");
counter=hanoi(n,'A','B','C');
return 0;
}
int hanoi(int n,char x,char y,char z)
{
int move(char,int,char);
if(n==1)
move(x,1,z);
else
{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z);
}
return 0;
}
int move(char getone,int n,char putone)
{
static int k=1;
printf("%2d:%3d # %c---%c\n",k,n,getone,putone);
if(k++%3==0)
printf("\n");
return 0;
}
c语言汉诺塔
我先回答最后一个问题,move只有输出是因为,我们本来就不需要真的挪动它,也没办法真的挪动它,只要打印挪动方法就可以了
n=3的情况中
我们要做的是把三个盘子挪到第三个柱子
hanoi函数的功能是,把最小的n个盘子从one柱挪到three柱
步骤1 首先把前n-1个盘子从one柱挪到two柱,这样就可以最大盘上面就什么都没有了
步骤2 直接把最大的盘子挪到three了
步骤3 然后再把那n-1个从two柱挪到one柱
为了实现步骤1,也是一样的方法
我们把前两个盘子挪到two,需要下面三个步骤
步骤1 首先把前n-2个盘子从one柱挪到three柱,这样就可以最大盘上面就什么都没有了
步骤2 直接把最大的盘子挪到two了
步骤3 然后再把那n-2个从three柱挪到two柱
原先的步骤3也是一样的道理
理解递归,并不需要完全搞清楚执行顺序,只需要把递归调用的关系找到就行了
另外,你可以在hanoi开始就把n,one,two,three打印出来,可以很清晰的看到执行过程
当前文章:c语言编写汉诺塔函数 汉诺塔循环求解C语言
本文URL:http://myzitong.com/article/hejjjc.html