您的位置:

汉诺塔c语言递归流程图,汉诺塔c程序的递归原理

本文目录一览:

求汉诺塔递归全过程的算法详解图,记得一定要是图释哦!!!

图解是什么意思呀。

这个算法 那么简单没必要搞得那么复杂吧。

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');

}