C语言汉诺塔问题

纯C环境下需要把变量的定义放到模块的最上方，不能先调用函数再定义变量之类的

#include<stdioh> han函数中的 int n;去掉，n是函数参数传过来的值，不去掉会出现类似死循环的无限递归；

给个我写的汉诺塔:

#include<stdioh>

int count=0;

struct queue{

int num;

char from;

char dst;

}Queue[1000];

void move(int n,char from,char ast,char dst)

{

if(n<=1) {Queue[count]num=n;Queue[count]from=from;Queue[count]dst=dst;count++;}

else

{

move(n-1,from,dst,ast);

Queue[count]num=n;Queue[count]from=from;Queue[count]dst=dst;count++;

move(n-1,ast,from,dst);

}

}

int main(void)

{

int n,i;

scanf("%d",&n);

if(n==0) return 0;

move(n,'A','B','C');

printf("%d\n",count);

for(i=0;i<count;i++)

{

printf("%d from %c to %c",Queue[i]num,Queue[i]from,Queue[i]dst);

if(i+1<count) printf("\n");

}

return 0;

}

输入是盘子数，输出是步数跟每一步的 *** 作

根据你的程序 当n=3 不满足n=1条件 所以走else 然后执行

hanoi(n-1,one,three,two); // 2 A C B

move(one,three); //调用move函数 输出 c-->B

hanoi(n-1,two,one,three); // 1 A B C

至于你说为什么此时n=1不执行if(n==1)是因为你的程序if和else没有在一个循环中，程序只会判断一次，如果你加一个while(n-1!=0)或者for循环在if前面才会不停检验n的值

void Move(char chSour, char chDest)

{

/打印移动步骤/

printf("\nMove the top plate of %c to %c",chSour, chDest);

}

Hanoi(int n, char chA, char chB, char chC)

{

/检查当前的盘子数量是否为1/

if(n==1) /盘子数量为1，打印结果后，不再继续进行递归/

Move(chA,chC);

else/盘子数量大于1，继续进行递归过程/

{

Hanoi(n-1,chA,chC,chB);

Move(chA,chC);

Hanoi(n-1,chB,chA,chC);

}

}

main()

{

int n;

/输入盘子的数量/

printf("\nPlease input number of the plates: ");

scanf("%d",&n);

printf("\nMoving %d plates from A to C:",n);

/调用函数计算，并打印输出结果/

Hanoi(n,'A','B','C');

}

这是基本算法

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

1 每次只能移动一个圆盘；

2 大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须尊循上述两条规则。

问：如何移？最少要移动多少次？

一般取N=64。这样，最少需移动264-1次。即如果一秒钟能移动一块圆盘，仍将需584554亿年。目前按照宇宙大爆炸理论的推测，宇宙的年龄仅为137亿年。

在真实玩具中，一般N=8；这将需移动255次。如果N=10，需移动1023次。如果N=15，需移动32767次；这就是说，如果一个人从3岁到99岁，每天移动一块圆盘，他仅能移动15块。如果N=20，需移动1048575次，即超过了一百万次。

先看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柱上。这就是我们所需要的结果！

回答者：wuchenghua121 - 经理 四级 12-5 11:51

汉诺塔

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

后来，这个传说就演变为汉诺塔游戏:

1有三根杆子A,B,C。A杆上有若干碟子

2每次移动一块碟子,小的只能叠在大的上面

3把所有碟子从A杆全部移到C杆上

经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：

如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

此外，汉诺塔问题也是程序设计中的经典递归问题。

补充：汉诺塔的算法实现（c++）

#include <fstream>

#include <iostream>

using namespace std;

ofstream fout("outtxt");

void Move(int n,char x,char y)

{

fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;

}

void Hannoi(int n,char a,char b,char c)

{

if(n==1)

Move(1,a,c);

else

{

Hannoi(n-1,a,c,b);

Move(n,a,c);

Hannoi(n-1,b,a,c);

}

}

int main()

{

fout<<"以下是7层汉诺塔的解法:"<<endl;

Hannoi(7,'a','b','c');

foutclose();

cout<<"输出完毕！"<<endl;

return 0;

}

C语言精简算法

/ Copyrighter by SS7E /

#include<stdioh> / Copyrighter by SS7E /

void hanoi(int n,char A,char B,char C) / Copyrighter by SS7E /

{

if(n==1)

{

printf("Move disk %d from %c to %c\n",n,A,C);

}

else

{

hanoi(n-1,A,C,B); / Copyrighter by SS7E /

printf("Move disk %d from %c to %c\n",n,A,C);

hanoi(n-1,B,A,C); / Copyrighter by SS7E /

}

}

main() / Copyrighter by SS7E /

{

int n;

printf("请输入数字n以解决n阶汉诺塔问题：\n");

scanf("%d",&n);

hanoi(n,'A','B','C');

}/ Copyrighter by SS7E /

回答者： Vanquisher_ - 举人 五级 12-5 13:57

parcel::::::::::

program hanoi;

functionhanoi(x:integer):longint;

begin

if x=1 then hanoi:=1;

if x=2 then hanoi:=3;

else

begin

hanoi:=2hanoi(x-1)+1;

end;

end;

begin

read(x){第几个数 }

write(hanoi(x));

end

思想就是：第N个就等于第n-1个乘以2+1次

move(n-1,x,z,y);——这句是调用函数,这个函数就是前面声明的:void move(int n,int x,int y,int z)

printf("%c-->%c",x,z);——这句是输出，%c 是指按CHAR型输出，"%c-->%c"，就是输出两个CHAR型数据，中间用-->连接。而这两个CHAR的数据就是x和z。比如结果是：a-->c

move(n-1,y,x,z);——这句还是调用函数,这个函数就是前面声明的:void move(int n,int x,int y,int z)

int game2()要改为int main()后才可编译运行：

#include<stdioh>

#include<stdlibh>

#define CSZL 10

#define FPZL 10

typedef struct hanoi

{

int n;

char x,y,z;

}hanoi;

typedef struct Stack //定义栈结点

{

hanoi base,top;

int stacksize;

}Stack;

int InitStack(Stack S)

{

S->base=(hanoi )malloc(CSZLsizeof(hanoi)); //申请栈空间

if(!S->base) //若申请不成功返回失败信息

return 0;

S->top=S->base; //置为空栈

S->stacksize=CSZL; //栈结点数

return 1;

}

int PushStack(Stack S,int n,char x,char y,char z) //入栈

{

if(S->top-S->base==S->stacksize) //若栈已满

{

S->base=(hanoi )realloc(S->base,(S->stacksize+FPZL)sizeof(hanoi)); //补充申请，扩充栈空间

if(!S->base)   //若申请不成功返回失败信息

return 0;

S->top=S->base+S->stacksize; //重置栈顶指针

S->stacksize+=FPZL; //重置栈空间尺寸

}

S->top->n=n; //新结点信息存入栈顶结点

S->top->x=x;

S->top->y=y;

S->top->z=z;

S->top++; //栈中元素加1

return 1;

}

int PopStack(Stack S,int n,char x,char y,char z) //出栈

{

if(S->top==S->base) //若栈已空

return 0; //返回出错信息

else

{

S->top--; //栈顶指针减1

n=S->top->n; //返回出栈元素信息

x=S->top->x;

y=S->top->y;

z=S->top->z;

return 1;

}

}

int EmptyStack(Stack S) //判定是否空栈

{

if(S->base==S->top)

return 1;

else

return 0;

}

int i=1;

void Move(char x,char z) //打印移动盘子的信息

{

printf("\n\t\t第%d步，%c-->%c",i++,x,z);

}

int main() / 非递归法 /

{

int n;

char x,y,z;

Stack S;

system("cls"); /清屏指令/

S=(Stack )malloc(sizeof(Stack)); //申请栈空间

if(!S)

return 0;

if(!InitStack(S)) //初始化栈

return 0;

printf("请输入汉诺塔的初始盘子数量以及轴的名称：");

scanf("%d\t%c%c%c",&n,&x,&y,&z);

if(!PushStack(S,n,x,y,z)) //要移动的盘子数及各轴名称入栈

return 0;

while(!EmptyStack(S)) //当栈非空时循环

{

if(!PopStack(S,&n,&x,&y,&z)) //若空栈则退出循环，否则出栈一个任务

break;

if(n==1) //若只有一个盘子，直接移动

{

Move(x,z);

}

else //有1个以上的盘子时入栈（注意栈的工作特点，是后进先出，所以最先做的事要最后入栈）

{

if(!PushStack(S,n-1,y,x,z)) //将上层的n-1个盘子从y移向z

break;

if(!PushStack(S,1,x,y,z)) //将底层的盘子从x移向z

break;

if(!PushStack(S,n-1,x,z,y)) //将上层的n-1个盘子从x移向y

break;

}

}

free(S->base);

S->base=NULL;

S->top=NULL;

S->stacksize=0;

return 0;

}

我先回答最后一个问题，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语言汉诺塔问题、关于C语言汉诺塔的理解求帮助、C语言题——汉诺塔问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！