本文目录一览：
用C语言编写汗诺塔的代码谁知道哪里有?
/********hanoi.c*********/
#include graphics.h
struct H
{
int data[15];/*存放每个盘的代号*/
int top;/*每个塔的具体高度*/
}num[3];/*三个塔*/
void move(char x,char y,struct H num[3]);/*移动的具体过程*/
void hanoi(char x,char y,char z,int n,struct H num[3]);/*递归*/
void Init(void);/*初始化*/
void Close(void);/*图形关闭*/
int computer=1;/*自动控制与手动控制的标志*/
int speed=0;/*全局变量speed主要是演示过程的速度*/
void main(void)
{
Init();/*初始状态*/
Close();/*图形关闭*/
exit(0);
}
void Init(void)/*初始化*/
{
int gd=DETECT,gm;
int i,n,color;
clrscr();
printf("please input n(n=10): ");/*输入要演示的盘子数*/
scanf("%d",n);
printf("Please input 1 or 2:\n1.computer 2.people\n");
scanf("%d",i);
if(i==2)/*选择手动控制标志为0*/
computer=0;
if(n1||n10)
n=10;/*越界的话n当10处理*/
if(computer)/*如果是自动控制的话输入速度*/
{
printf("please input speed: ");/*输入速度*/
scanf("%d",speed);
}
initgraph(gd,gm,"c:\\tc");
cleardevice();
for(i=0;i3;i++)
num[i].top=-1;/*三个地方的高度开始都为-1*/
for(i=0;in;i++)/*画一开始的塔座A上的盘子*/
{
num[0].top++;/*栈的高度加1*/
num[0].data[num[0].top]=i; /*最大的盘子代号为0，依次为1，2，…n-1*/
color=num[0].data[num[0].top]+1;/*盘子的颜色代码为栈顶盘子代号加1*/
setfillstyle(SOLID_FILL,color);
bar(100-(33-3*num[0].data[num[0].top]),400-20*i-8,100+
(33-3*num[0].data[num[0].top]),400-20*i+8); /*画矩形*/
}
setcolor(YELLOW);
outtextxy(180,450,"any key to continue");
settextstyle(0,0,2);
outtextxy(90,420,"A"); /*塔座标志*/
outtextxy(240,420,"B");
outtextxy(390,420,"C");
getch();/*接收字符后就执行递归操作*/
hanoi('a','b','c',n,num);
}
void move(char x,char y,struct H num[3])/*移动的具体过程*/
{
int i;
char num1[3],num2[3];
sprintf(num1,"%c",x-32);/*将小写变成大写，并转换成字符串输出*/
sprintf(num2,"%c",y-32);
setfillstyle(SOLID_FILL,BLACK);/*把原来的地方移去涂黑*/
bar(0,0,640,60);
setcolor(RED);
outtextxy(150,30,num1);/*输出移动过程*/
outtextxy(200,30,"---");
outtextxy(310,30,num2);
settextstyle(0,0,2);
setfillstyle(SOLID_FILL,BLACK);/*把原来的地方移去涂黑*/
bar(100+150*(x-97)-(33-3*num[x-97].data[num[x-97].top]),
400-20*num[x-97].top-8,100+150*(x-97)+(33-3*
num[x-97].data[num[x-97].top]),400-20*num[x-97].top+8);
num[y-97].top++;/*入栈，目标点的top加1*/
num[y-97].data[num[y-97].top]=num[x-97].data[num[x-97].top];/*在目标点盘子的代号与源点盘子的代号相同*/
num[x-97].top--;/*出栈，原来地方的top减1*/
setfillstyle(SOLID_FILL,num[y-97].data[num[y-97].top]+1);/*盘子颜色代码是栈顶盘子代号加1*/
bar(100+150*(y-97)-(33-3*num[y-97].data[num[y-97].top]),
400-20*num[y-97].top-8,100+150*(y-97)+
(33-3*num[y-97].data[num[y-97].top]),400-20*num[y-97].top+8);
if(computer)/*自动控制就用delay*/
delay(speed);/*延时函数*/
else
getch();/*手动控制的话就自己按键盘来控制*/
}
void hanoi(char one,char two,char three,int n,struct H num[3])/*递归n为盘子数，num为堆栈*/
{
if(n==1)
move(one,three,num);/*如果盘子为1，将这个盘子从塔座A移动到塔座C*/
else
{
hanoi(one,three,two,n-1,num);/*将塔座A的前n-1个盘子移到塔座B*/
move(one,three,num);/*将塔座A的第n个盘子移到塔座C*/
hanoi(two,one,three,n-1,num); /*将塔座B的n-1个盘子移到塔座C*/
}
}
void Close(void)/*图形关闭*/
{
getch();
closegraph();
}
递归 汉诺塔 问题 快点来个人吧 急死了 出事了
引用谭书第一版。
函数的递归调用
一个函数在它的函数体内调用它自身称为递归调用。 这种函数称为递归函数。C语言允许函数的递归调用。在递归调用中， 主调函数又是被调函数。执行递归函数将反复调用其自身。 每调用一次就进入新的一层。例如有函数f如下：
int f (int x)
{
int y;
z=f(y);
return z;
}
这个函数是一个递归函数。 但是运行该函数将无休止地调用其自身，这当然是不正确的。为了防止递归调用无终止地进行， 必须在函数内有终止递归调用的手段。常用的办法是加条件判断， 满足某种条件后就不再作递归调用，然后逐层返回。 下面举例说明递归调用的执行过程。
你这里的条件是if(n==1)，就是A针上只有一个盘子，才结束调用函数，返回到上一个函数里，依次倒推。
Hanoi塔问题
一块板上有三根针，A，B，C。A针上套有64个大小不等的圆盘， 大的在下，小的在上。如图5.4所示。要把这64个圆盘从A针移动C针上，每次只能移动一个圆盘，移动可以借助B针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。求移动的步骤。
本题算法分析如下，设A上有n个盘子。
如果n=1，则将圆盘从A直接移动到C。
如果n=2，则：
1.将A上的n-1(等于1)个圆盘移到B上；
2.再将A上的一个圆盘移到C上；
3.最后将B上的n-1(等于1)个圆盘移到C上。
如果n=3，则：
A. 将A上的n-1(等于2，令其为n`)个圆盘移到B(借助于C)，
步骤如下：
(1)将A上的n`-1(等于1)个圆盘移到C上，见图5.5(b)。
(2)将A上的一个圆盘移到B，见图5.5(c)
(3)将C上的n`-1(等于1)个圆盘移到B，见图5.5(d)
B. 将A上的一个圆盘移到C，见图5.5(e)
C. 将B上的n-1(等于2，令其为n`)个圆盘移到C(借助A)，
步骤如下：
(1)将B上的n`-1(等于1)个圆盘移到A，见图5.5(f)
(2)将B上的一个盘子移到C，见图5.5(g)
(3)将A上的n`-1(等于1)个圆盘移到C，见图5.5(h)。
到此，完成了三个圆盘的移动过程。
从上面分析可以看出，当n大于等于2时， 移动的过程可分解为
三个步骤：
第一步 把A上的n-1个圆盘移到B上；
第二步 把A上的一个圆盘移到C上；
第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。
当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。 显然这是一个递归过
程，据此算法可编程如下：
move(int n,int x,int y,int z)
{
if(n==1)
printf("%c--%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c--%c\n",x,z);
move(n-1,y,x,z);
}
}
main()
{
int h;
printf("\ninput number:\n");
scanf("%d",h);
printf("the step to moving %2d diskes:\n",h);
move(h,'a','b','c');
}
move(int n,int x,int y,int z)
{
if(n==1)
printf("%--%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c--%c\n",x,z);
move(n-1,y,x,z);
}
}
main()
{ ……
move(h,'a','b','c');
}
从程序中可以看出,move函数是一个递归函数，它有四个形参n,x,y,z。n表示圆盘数，x,y,z分别表示三根针。move 函数的功能是把x上的n个圆盘移动到z 上。当n==1时，直接把x上的圆盘移至z上，输出x→z。如n!=1则分为三步：递归调用move函数，把n-1个圆盘从x移到y；输出x→z；递归调用move函数，把n-1个圆盘从y移到z。在递归调用过程中n=n-1，故n的值逐次递减，最后n=1时，终止递归，逐层返回。当n=4 时程序运行的结果为
input number:
4
the step to moving 4 diskes:
a→b
a→c
b→c
a→b
c→a
c→b
a→b
a→c
b→c
b→a
c→a
b→c
a→b
a→c
b→c
如何推导汉诺塔的公式
求汗诺塔N个盘子须几次移动时得到了下面的递推公式：
a[1] = 1;
a[n] = a[n-1] * 2 + 1;
请教通项公式？
a[1] = 1;
a[n] = a[n-1] * 2 + 1;
可得a[i]= 2^i-1;
证明，采用数学归纳法：
1、猜想a[i]= 2^i-1
2、当i=1时，显然成立。
3、假设i=k时成立，即 a[k] = 2^k - 1;则：
由a[n] = a[n-1] * 2 - 1;得
a[k+1] = a[k] * 2 - 1
= 2^k * 2 - 1
= 2^(k-1) - 1
故得证。
同时：：
汉诺塔问题（又称河内塔问题）是根据一个传说形成的一个问题：
有三根杆子A，B，C。A杆上有N个(N1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须尊循上述两条规则。
问：如何移？最少要移动多少次？
一般取N=64。这样，最少需移动264-1次。即如果一秒钟能移动一块圆盘，仍将需5845.54亿年。目前按照宇宙大爆炸理论的推测，宇宙的年龄仅为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("out.txt");
void Move(int n,char x,char y)
{
fout"把"n"号从"x"挪动到"yendl;
}
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');
fout.close();
cout"输出完毕！"endl;
return 0;
}
C语言精简算法
/* Copyrighter by SS7E */
#includestdio.h /* 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:=2*hanoi(x-1)+1;
end;
end;
begin
read(x){第几个数 }
write(hanoi(x));
end.
思想就是：第N个就等于第n-1个乘以2+1次
