本文目录一览:
- 1、求汉诺塔递归全过程的算法详解图,记得一定要是图释哦!!!
- 2、c语言用递归实现汉诺塔
- 3、汉诺塔流程图
- 4、求C汉诺塔递归过程详解
- 5、汉诺塔n=4(4个盘)c语言递归编程代码
- 6、汉诺塔问题的递归算法流程图
求汉诺塔递归全过程的算法详解图,记得一定要是图释哦!!!
图解是什么意思呀。
这个算法 那么简单没必要搞得那么复杂吧。
an = an-1 + 1;
你明白这个等式的意义吗?
这个等式已经包含了递归算法的全部含义。
an 表示 n个数的和,an-1 表示n-1个数的和 ,an = an-1 + 1;表示n个数的和可以通过n-1个数的和来求的。
上述说明哪些情况可以使用递归呢?
那就是:已知前一个步骤可以求得后一个步骤的结果的情况,并且前一个步骤和后一个步骤是有规律过度的。
比如汉诺塔问题:
移n个盘是已移n-1个盘为条件的,两者的共同点是移盘。所以可以用f(n)表示移n个盘,f(n-1)表示移n-1个盘,那么移n个盘和移n-1个盘有什么关系呢?
这就需要预先分析问题才能得出具体的关系
在这个问题中,把n个盘从a移到c需要三个步骤来完成。
1.n-1个盘从a移到b
2 1个盘从a移到c
3 n-1个盘从b移到c
已知n-1个盘从a移到b是可行的,为什么?
因为移1个盘是可行,那么移2个盘也是可行,移 3个盘是已移2个盘为条件的,所以移3个盘也是可行的,所以移n个 盘是可行的。
所以根据已知条件可以解得:
设f(n, a, b,c) 表示 把n个盘从a移到c 借助b --------------------------这里很关键,这是搞懂递归的关键关键。
那么把n-1个盘从a移到b 借助c 怎样表示呢?
很明显是:f(n-1, a, c,b)
那么把1个盘从a移到c怎样表示呢?
很明显是:f(1, a, b,c)
那么把n-1个盘从b移到c 借助a 怎样表示呢?
很明显是:f(n-1, b, a,c)
所以f(n, a, b,c) = ( f(n-1, a,c,b) , f(1, a, b,c), f(n-1, b,a,c))
这和等差等比数列一个原理。
没有什么 特别的。
记住是问题有这样递推关系才可以使用这种方法。
如果要你计算1+2+8+22 的结果 你就不能使用递归。
因为该问题的后一步骤与前一步骤不具有规律性,所以已知前一个步骤并不能求的后一个步骤的值
1+2+3+4 ...+ 111111111111111111111111111111
这个问题就可以使用递归
原因你懂了吧。
至于爬楼梯问题,无限级分类 问题等一些递归问题,那不过时小菜一碟。
一句话:后一步骤依赖前一步骤并且二者联系具有规律性,运用递归必然成功。
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;
}
汉诺塔流程图
你好!
汉诺塔流程图:
void move(int , char ,char,char); /*声明函数,告诉系统我随后要定义一个函数,他不对其中参数进行检查,所以可以省略参数,一般只写类型,表示有多少个什么类型的参数,便于自己理解 */
main()
{int n;
printf("请输入盘数n=" );
scanf("%d",n);
printf("在3根柱子上移%d只盘的步骤为:\n",n);
move(n,'a','b','c');}/*函数调用,用a,b,c代表3跟柱子,把盘子数,柱子代码传给函数*/
void move(int m, char p, char q, char r) //定义函数
{if (m==1)
{printf("[%d] move 1# from %c to %c\n", step, p,r);
step=step+1;}
else{move(m-1,p,r,q); //调用本身函数,进行递归 A
printf("[%d] move %d# from %c to %c\n",step, m,p,r);
step=step+1;
move(m-1,q,p,r); //再次调用 B
}
getch();}
递归其实是嵌套调用,
所谓嵌套调用,就是在一个函数里调用另一个函数,
main函数不能被调用的,
所以递归就是有限次的嵌套调用本身函数
每次调用,系统都会重新分配内存,
返回时就返回上次调用他的那块内存中的调用函数处,
这样理解应该很简单了
汉诺塔流程图解析:
这里面的递归涉及一个汉诺塔的算法问题,具体讲明白的话有点麻烦,总体思路是假设盘子全在a柱上,想放到c上
第N个人就想要是有人搬动其他N-1个盘子到b,那他只要搬一次从a到c就可以,在让那个人把N-1个盘子放到c上
第N-1那个人就想要是有人搬动其他N-2个盘子到c,他只要搬动一次从a到b就可以,在让那个人把N-2个盘子放到b上
....
第1个人就直接把盘子从a到c
这样形成递归
我在俩处调用标记了A,B,我写出步踌,你看看.
假设3个盘子
A函数相当于双重循环中的外层循环
B函数相当于双重循环中的内层循环
1,主函数调用,p=a,q=b,r=c,m=3,运行A,调用本身(A第一次调用)传入p,r,q(a,c,b) 注意调用函数中p,r,q排列
2,被调函数是用p,q,r的顺序接收传入的p,r,q.p=a,q=c,r=b,m=2,执行A,调用本身(A第二次调用) 调用传入p,r,q(a,b,c)
3,p=a,q=b,r=c,m=1,执行if,输出a-c,返回A第二次调用
4,本次函数中p=a,q=c,r=b,m=2,向下执行,输出a-b,执行B,调用本身(B第一次调用),传入q,p,r(c,a,b),m=1
5,p=c,q=a,r=b,m=1,执行if,输出c-b,返回B第一次调用
6,向下执行,执行完毕,返回A第一次调用
7,本次函数中p=a,q=b,r=c,m=3,向下执行,输出a-c,执行B,调用本身(B第一次调用),传入q,p,r(b,a,c),m=2
8,p=b,q=a,r=c,m=2,执行A,调用本身(A'第一次调用,注意是B函数调用中再次调用A) 传入p,r,q(b,c,a)
9,p=b,q=c,r=a,m=1,执行if,输出b-a,返回A'第一次调用
10,本次函数中p=b,q=a,r=c,m=2向下执行,输出b-c,执行B,调用本身(B'的第一次调用,注意是B函数中再次调用B) 传入q,p,r(a,b,c),m=1
11,p=a,q=b,r=c,m=1,执行if,输出a-c返回B'第一次调用
12,向下执行,执行完毕,返回B第一次调用
13,向下执行,执行完毕,返回主函数
仔细分析每次调用时当前变量p,q,r中所代表的a,b,c,每次调用时,p,q,r都是新的变量
我看了你的问题,估计你把调用函数中的p,q,r变量与被调函数中p,q,r变量搞混了
/*
4,向下执行,执行B,调用本身(B第一次调用),由于本次函数中p=a,q=c,r=b,m=2,先输出a-b,再传入q=c,p=a,r=b,m=1
这里不是[4] move 3# from a to c吗
*/
注意调用传入的顺序是q,p,r,传入的值是c,a,b的顺序,被调函数中是拿p,q,r的顺序在接收,所以被调函数中值的顺序就该是p=c,q=a,r=b,执行if就输出c-b
补充:流程图步骤画了好久额,有什么疑问发我邮箱315946173@qq.com
求C汉诺塔递归过程详解
解决汉诺塔的基本思想是先把n个盘子除了最下面的盘子以外的所有盘子从第一根柱子(初始柱子)移动到中间那个柱子上(辅助柱子),然后把最下面的盘子移动到最后一根柱子上(目标柱子)。最后把剩下的盘子移动到目标柱子上。这样,然而,完成第一步和第三步也同样是一个移动n-1个盘子的汉诺塔问题。于是,递归调用在这里不可避免。程序你已经写的很清楚,给你解释一下。现把你的程序画上行以便说明。
1
#include
"stdio.h"
2
main()
3
{void
hanoi(int,char,char,char);
4
int
m;
5
printf("input
the
number
of
disks:");
6
scanf("%d",m);
7
printf("The
step
to
moving
%d
disks:\n",m);
8
hanoi(m,'A','B','C');
9
}
10
void
hanoi(int
n,char
a,char
b,char
c)
11
{//void
move(char,char);
12
if(n==1)
move(a,c);
13
else
14
{hanoi(n-1,a,c,b);
15
move(a,c);
16
hanoi(n-1,b,a,c);
17
}
18
}
19
void
move(char
x,char
y)
20
{printf("%c--%c\n",x,y);
21
}
当m=4时,程序走到第8行,调用函数hanoi(int
n,char
a,char
b,char
c)。此时,实参把值传递给了形参,于是此时,n=4,a=A,b=B,c=C。我把第11行的void
move(char,char);
注释掉了,应该知道这一句的意思。因为这一行虽然可以让程序更加完整,但是解释的时候加上它会很麻烦。程序走到第12行,因为此时n=4,而不等于1,程序直接走第13行。于是调用第14行的hanoi(n-1,a,c,b)。这是一个递归调用。此时,n=3,a=A,c=B,b=C。要清楚,A,B,C代表的意义。A代表初始柱子,B代表辅助柱子,C代表目标柱子。而a代表第一根柱子,b代表第二根柱子,c代表第三根柱子。这是不一样的。程序继续走,到12行时n依然不等于1。走到14行调用hanoi(n-1,a,c,b)。此时,n=2,a=A,c=C,b=B。程序再走,到12行时n依然不等于1,走到14行调用hanoi(n-1,a,c,b)。此时,n=1,a=A,c=B,b=C。程序走到12行时发现n=1,程序开始走15行。调用move(char
x,char
y)到20行时输出A--B。调用结束,回到上一个调用即n=2,a=A,c=C,b=B。程序回到第15行,输出
A--B。再走第16行,调用hanoi(n-1,b,a,c)。此时n=1,b=A,a=B,c=C。程序回到12行再调用19行输出B--C。调用结束,回到上一个调用n=3,a=A,c=B,b=C。程序走到15行,输出A--C,这时,第一根柱子上有一个盘子,第二根柱子上有一个盘子,第三根柱子上有两个盘子。再调用16行就可以完成把第三根柱子里的所有盘子都移动到第二根柱子上。这样。我们就完成了整体目标的第一步。把n个盘子除了最下面的盘子以外的所有盘子从第一根柱子(初始柱子)移动到中间那个柱子上(辅助柱子),调用完成后程序回到15行,此时n=3,a=A,c=B,b=C。15行时输出A--C,这时便完成了整体目标的第二步,最下面的盘子移动到最后一根柱子上(目标柱子)。再根据程序走到16行,经过跟14行类似的一系列的递归调用,我们就可以完成最终目标了。
汉诺塔n=4(4个盘)c语言递归编程代码
/****************************
汉诺塔的算法就3个步骤:
第一,把a上的n-1个盘通过c移动到b。
第二,把a上的最下面的盘移到c。a成了空的。
第三,因为n-1个盘全在b上了,所以把b当做a.
重复以上步骤就好了。所以算法看起来就简单多了。
******************************/
#includestdio.h
static int m=0;
void move(int n,char a,char b,char c)
{
if(n==1)
{
m++;
printf("第 %d 次移动:\n", m );
printf("\t%c-%c\n",a,c); //当n只有1个的时候直接从a移动到c
}
else
{
move(n-1,a,c,b); //第n-1个要从a通过c移动到b
m++;
printf("第 %d 次移动:\n", m );
printf("\t%c-%c\n",a,c);
move(n-1,b,a,c); //n-1个移动过来之后b变开始盘,b通过a移动到c,这边很难理解
}
}
int main()
{
int n=4;
//printf("请输入要移动的块数:");
// scanf("%d",n);
move(n,'a','b','c');
return 0;
}
汉诺塔问题的递归算法流程图
#include stdio.h
void hano(int n,char a,char b,char c)
{
if(n==1)
printf("\t将%d个盘片从%c移动到%c\n",n,a,c);
else {
hano(n-1,a,c,b);
printf("\t将第%d个盘片从%c移动到%c\n",n,a,c);
hano(n-1,b,a,c);
}
}
main()
{
int n;
printf("输入将要移动多少个盘子n:");
scanf("%d",n);
printf("递归结果:\n");
hano(n,'x','y','z');
}