汉诺塔递归算法c语言（汉诺塔递归算法c语言代码讲解）

by intanet.cn ca 算法 on 2024-03-18

本篇文章给大家谈谈汉诺塔递归算法c语言，以及汉诺塔递归算法c语言代码讲解对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

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语言汉诺塔递归算法的简易理解

一开始我接触汉诺塔也是很不解，随着代码量的积累，现在很容易就看懂了，因此楼主主要还是对递归函数的理解不够深刻，建议你多写一些递归程序，熟练了自己就能理解。

圆盘逻辑移动过程+程序递归过程分析

hanoi塔问题, 算法分析如下，设a上有n个盘子，为了便于理解我将n个盘子从上到下编号1-n，标记为盘子1，盘子2......盘子n。

如果n=1，则将“ 圆盘1 ” 从 a 直接历庆移动到 c。

如果n=2，则：

（1）将a上的n-1（等于1）个圆盘移到b上，也就是把盘1移动到b上；

（2）再将a上 “盘2” 移到c上；

（3）最后将b上的n-1（等于1）个圆盘移到c上，也就是第（1）步中放在b上的盘1移动到c上。

注意：在这里由于超过了1个盘子，悉烂判因此不能直接把盘子从a移动到c上，要借助b，那

么 hanoi（n，one，two，three）的含义就是由n个盘子，从one移动到three，如果n2

那么就进行递归，如果n=1，那么就直接移动。

具体流程：

hanoi（2，a，b，c）；由于21因此进入了递归的环节中。

1执行hanoi（1，a，c，b）：这里就是刚才的步骤（1），代表借助c柱子，将a柱子上的 1个圆盘（盘1）移动到b柱子，其实由于是n=1，此时c柱子并没被用到，而是直接移动了。

2执行hanoi（1，a，b，c）：这是步骤（2），借助b柱子，将a柱子上的一个圆盘（盘2）移动到c柱子上。这里由于也是n=1，也并没有真正借助b柱子，直接移动的。

3执行hanoi（1，b，a，c）：这是步骤（3），将b上的一个盘子（盘1）移动到c

函数中由于每次调用hanoi的n值都是1，那么都不会进入递归中，都是直接执行了mov移动函数。

如果n=3，则：（倒着想会想明白）移动的倒数第二部，必然是下面的情况

（1）将a上的n`-1（等于2）个圆盘移到c上，也就是将盘1、盘2 此时都在b柱子上，只有这样才能移动最下面的盘子（盘3）。那么由于现在我们先忽略的最大的盘子（盘3），那么我们现在的目标就是，将两个盘子（盘1、盘2）从a柱子上，借助c柱 子，移动到b柱子上来，这个过程是上面n=2的时候的移动过程，n=2的移动过程是“2 个盘子，从柱子a，借助柱子b，移动到柱子c”。现在是“2个盘子，从柱子a，借助柱子 c，移动到柱子b上”。因此移动过程直接调用n=2的移动过程就能实现。

（2）将a上的一个圆盘（盘3）移到c。

（3）到这一步，由于已经将最大的盘子（盘3）移动到了目的地，此时无论后面怎么移动都不需要在用到最大的那个盘子（盘3），我们就先忽略他，剩下的目标就是将b上面的n-1个盘子（盘1、盘2）移动到c上，由于a上没有盘子了，此时要完成上面的目标，就要借助a盘子。最终达到的目标就是将b上的2个盘子，借助a移动到c上，这个过程就是当n=2时分析的过程了，仅仅是最开始的柱子（b柱子）和被借助的柱子（a柱子）不同了。所以直接调用n=2时候的过程就能股实现了。

具体执行过程：

hanoi（3，a，b，c）；由于31因此进入了递归的环节中。

1执行hanoi(2,a,c,b):这里代表刚才的步骤（1），将两个盘子（盘1、盘2）从a移动到b，中间借助c。根据n=2的分析过程，必然是能够达到我们的目的。

2执行hanoi（1，a，b，c）：现在a上只有一个盘子（盘3），直接移动到c上面即可。

3执行hanoi（2，b，a，c）：此时对应步骤（3），剩下的目标就是将b上的两个盘子，借助a移动到c上。那么同样根据n=2的移动过程，必然能达到目的。

最终实现了3个盘子从a，借助b移动到了睁改c。

c语言递归问题： 汉诺塔问题：

这里没有运算，只是每一步都按照你最顶上的伪算法描述，掘枯耐按某个固定的顺序去递归调用所谓的搬移程序，注意关键不是搬移程序里面干什么（其实什么都不用干，算法分析而已），而是递归调用时的参数顺序。如果一定要干点什么，我自己当时也是觉判春得要干点什么，所以自己加上了个演示的东西，结果就真的干了点什么，给你看看吧（已通过dev c++ 5 编译执行）。

/*

Name: hanoi tower show

Copyright: whatever you want,i donn't care

Author: zero_fn

Date: 07-04-11 11:52

Description: first try of hanoi tower and stack OP

*/

#include stdio.h

#define UCHAR unsigned char

#define UINT32 unsigned int

#define CLS system("CLS")

/*share var define*/

UINT32 * A_top = NULL, * A_bottom = NULL, * B_top = NULL, * B_bottom = NULL, * C_top = NULL, * C_bottom = NULL;

UINT32 steps = 0;

/*function define*/

UINT32 * build_stack(UINT32 f);

UINT32 push(UINT32 ** top, UINT32 * bot, UINT32 f,UINT32 tmp);

UINT32 gettop(UINT32 ** top, UINT32 * bot);

UINT32 ptop(UINT32 ** top , UINT32 * bot);

void move(UINT32 **stop , UINT32 * sbot, UINT32 **dtop, UINT32 * dbot ,UINT32 f);

void show_stack(UINT32 f);

void Pan(UINT32 n, UINT32 f, UINT32 **topA, UINT32 *botA, UINT32 **topB, UINT32 *botB,UINT32 **topC, UINT32 *botC);

void delay(void)

{

UINT32 tmp = 3000;

while(tmp)

tmp--;

}

void hanoi(void)

{

UINT32 flo = 0, f = 0;

puts("输入演示汉诺塔的层数 max 13:");

scanf("%d",flo);

if(flo13) f=13;

else f = flo;

A_top = build_stack(f);

B_top = build_stack(f);

C_top = build_stack(f);

if((NULL == A_top) || (NULL == B_top) || (NULL == C_top))

{

free(A_top); free(B_top); free(C_top);

return;

}

else

{

A_bottom = A_top+f;

B_bottom = B_top+f;

C_bottom = C_top+f;

for(flo = 0; flo f; flo++)

{

*(A_top+flo) = 2*flo+1;

}

B_top = B_bottom;

C_top = C_bottom;

}

CLS;

show_stack(f);

puts("按任意键开始演示"败敏);

getch();

steps = 0;

Pan(f, f, (A_top), A_bottom, (B_top), B_bottom, (C_top), C_bottom);

printf("完成！ 共搬移:\"%d\"次 任意键继续",steps);

getch();

}

void Pan(UINT32 n, UINT32 f, UINT32 **topA, UINT32 *botA, UINT32 **topB, UINT32 *botB,UINT32 **topC, UINT32 *botC)

{

/*递归调用，不断的搬盘子*/

if(1 == n)

{

move(topA, botA, topC, botC, f);

CLS;

show_stack(f);

delay();

}

else

{

Pan(n-1, f, topA, botA, topC, botC, topB, botB);

move(topA, botA, topC, botC, f);

CLS;

show_stack(f);

delay();

Pan(n-1, f, topB, botB, topA, botA, topC, botC);

}

}

void move(UINT32 **stop , UINT32 *sbot, UINT32 **dtop, UINT32 *dbot ,UINT32 f)

{

/*模拟搬移盘子的过程 */

UINT32 tmp;

tmp = ptop(stop, sbot);

push(dtop, dbot, f, tmp);

steps++;

}

UINT32 * build_stack(UINT32 f)

{

/* 建立堆栈 ，用于模拟放盘子的柱子*/

UINT32 * top;

if(NULL == (top = (UINT32 *)calloc(f , sizeof(UINT32))))

return NULL;

return top;

}

UINT32 push(UINT32 **top,UINT32 * bot,UINT32 f,UINT32 tmp)

{

/*值压栈 把盘子放到某根柱子最上层*/

if(*top =((bot-f)))

{

puts("stack overflow...");

return 0;

}

(*top)--; //fix Top ADD

**top = tmp;

return 1;

}

UINT32 ptop(UINT32 **top ,UINT32 *bot)

{

/*取值出栈 把盘子从某根柱子上取下来*/

UINT32 tmp;

if(*top == bot)

{

puts("stack underflow...");

return 0;

}

tmp = **top;

**top = 0;

(*top)++; ////fix Top ADD

return tmp;

}

UINT32 gettop(UINT32 ** top, UINT32 * bot)

{

/*取值不出栈*/

UINT32 tmp;

if(*top == bot)

{

puts("stack underflow...");

return 0;

}

tmp = **top;

return tmp;

}

void show_stack(UINT32 f)

{

/*显示各个柱子和上面盘子的情况*/

UCHAR buff[30] = {0};

UCHAR buff1[30] = {0};

UINT32 i,j,k;

sprintf(buff1,"%26s","========================= ");

printf("%s",buff1);

printf("%s",buff1);

printf("%s\n",buff1);

for(i=1;i=f;i++)

{

for(k=0;k((25-*(A_bottom-i))/2);k++)

{

buff[k] = ' ';

}

for(j=0;j*(A_bottom-i);j++)

{

buff[j+k] = '*';

}

buff[j+k] = '\0';

sprintf(buff1,"%-25s",buff);

printf("%s",buff1);

//sprintf(buff1,"%-13s",buff);

//printf("%s",buff1);

printf(" ");

buff[0]='\0';

for(k=0;k((25-*(B_bottom-i))/2);k++)

{

buff[k] = ' ';

}

for(j=0;j*(B_bottom-i);j++)

{

buff[j+k] = '*';

}

buff[j+k] = '\0';

sprintf(buff1,"%-25s",buff);

printf("%s",buff1);

//sprintf(buff1,"%-13s",buff);

//printf("%s",buff1);

printf(" ");

buff[0]='\0';

for(k=0;k((25-*(C_bottom-i))/2);k++)

{

buff[k] = ' ';

}

for(j=0;j*(C_bottom-i);j++)

{

buff[j+k] = '*';

}

buff[j+k] = '\0';

sprintf(buff1,"%-25s",buff);

printf("%s",buff1);

//sprintf(buff1,"%-13s",buff);

//printf("%s",buff1);

puts(" ");

buff[0]='\0';

}

}

int main(int argc, char *argv[])

{

hanoi();

system("PAUSE");

}

[img]

求C语言汉诺塔源码（递归和非递归都要）

递归算法是我前些天写的，非递归是刚才找的，里面含递归和非递归。\x0d\x0a递归算法：\x0d\x0a#include \x0d\x0a//递归求汉诺塔问题\x0d\x0avoid hanoi(int n, char A, char B, char C, int *time)\x0d\x0a{\x0d\x0aif (n=1)\x0d\x0a{\x0d\x0a hanoi(n-1, A, C, B, time);\x0d\x0a move(A, C);\x0d\x0a (*time)++;\x0d\x0a hanoi(n-1, B, A, C, time);\x0d\x0a }\x0d\x0a}\x0d\x0a//打印出每一步的路径\x0d\x0avoid move(char a, char c)\x0d\x0a{\x0d\x0aprintf(" %c--%c\n", a, c);\x0d\x0a}\x0d\x0a\x0d\x0aint main(void)\x0d\x0a{\x0d\x0aint n, time = 0;;\x0d\x0aprintf("请输入汉诺塔的盘数:");\x0d\x0ascanf("%d", n);\x0d\x0aprintf("%d个盘的汉诺塔移动方法是：", n);\x0d\x0aprintf("\n");\x0d\x0ahanoi(n, 'A', 'B', 'C', time);\x0d\x0aprintf("移动了%d次\n", time);\x0d\x0asystem("pause");\x0d\x0areturn 0;\x0d\x0a}\x0d\x0a\x0d\x0a非递裤做归算法：\x0d\x0a#include \x0d\x0a\x0d\x0a#define MAXSTACK 10 /* 栈的最大深度 */\x0d\x0a\x0d\x0aint c = 1; /* 一个全局变量，表示目前移动的步数 */\x0d\x0a\x0d\x0astruct hanoi { /* 存储汉诺塔的结构，包括盘的数目和三个盘的名称 */\x0d\x0aint n;\x0d\x0achar x, y, z;\x0d\x0a};\x0d\x0a\x0d\x0avoid move(char x, int n, char y) /* 移动函数，表示把某个盘从某根针移动到另一根针 */\x0d\x0a{\x0d\x0aprintf("%d- %d from %c - %c\n", c++, n, x, y);\x0d\x0a}\x0d\x0a\x0d\x0avoid hanoi(int n, char x, char y, char z) /* 汉诺塔的递归算法 */\x0d\x0a{\x0d\x0aif (1 == n)\x0d\x0amove(x, 1, z);\x0d\x0aelse {\x0d\x0ahanoi(n - 1, x, z, y);\x0d\x0amove(x, n, z);\x0d\x0ahanoi(n - 1, y, x, z);\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0avoid push(struct hanoi *p, int top, char x, char y, char z,int n)\x0d\x0a{\x0d\x0ap[top+1].n = n - 1;\x0d\x0ap[top+1].x = x;\x0d\x0ap[top+1].y = y;\x0d\x0ap[top+1].z = z;\x0d\x0a}\x0d\x0a\x0d\x0avoid unreverse_hanoi(struct hanoi *p) /* 汉诺塔的非递归算法 */\x0d\x0a{\x0d\x0aint top = 0;\x0d\x0a\x0d\x0awhile (top 胡闷衡= 0) {\x0d\x0awhile (p[top].n 1) { /* 向左走到尽头 */\x0d\x0a push(p, top, p[top].x, p[top].z, p[top].y, p[top].n);\x0d\罩衫x0a top++;\x0d\x0a}\x0d\x0aif (p[top].n == 1) { /* 叶子结点 */\x0d\x0a move(p[top].x, 1, p[top].z);\x0d\x0a top--;\x0d\x0a}\x0d\x0aif (top = 0) { /* 向右走一步 */\x0d\x0a move(p[top].x, p[top].n, p[top].z);\x0d\x0a top--;\x0d\x0a push(p, top, p[top+1].y, p[top+1].x, p[top+1].z, p[top+1].n);\x0d\x0a top++;\x0d\x0a}\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0aint main(void)\x0d\x0a{\x0d\x0aint i;\x0d\x0aprintf("递归:\n");\x0d\x0ahanoi(3, 'x', 'y', 'z');\x0d\x0aprintf("非递归:\n");\x0d\x0astruct hanoi p[MAXSTACK];\x0d\x0ac = 1;\x0d\x0ap[0].n = 3;\x0d\x0ap[0].x = 'x', p[0].y = 'y', p[0].z = 'z';\x0d\x0aunreverse_hanoi(p);\x0d\x0a\x0d\x0areturn 0;\x0d\x0a}

汉诺塔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;

}

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语言和汉诺塔递归算法c语言代码讲解的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。

数据支持（邮件数据统计为邮件活动策划提供数据支持） jmeterjson（jmeterjson提取器）
相关阅读
最近发表
文章归档
标签列表