Question

谁会用C语言解决汉诺塔问题？请进，最好把每一步的解释写上。

有三个柱子，编号A、B、C，在A柱上有n个圆盘，直径不同，按直径从大到小依次叠放在柱子上，要求：把A柱上的圆盘借助B柱移动到C柱。每次移动一个，任何情况下保证大的在下，小的在上。
设计并实现该算法，输出搬动圆盘过程。
这个是我们数据结构（C语言版）的课程设计，请人帮我写下，最好有每部程序是干什么的，很急，谢谢！！本人在线等，如果分不够我加分。

Answer 1

#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);
getch();
}
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(n<1||n>10)
n=10;/*越界的话n当10处理*/
if(computer)/*如果是自动控制的话输入速度*/
{
printf("please input speed: ");/*输入速度*/
scanf("%d",&speed);
}
initgraph(&gd,&gm,"c:\\tc");
cleardevice();
for(i=0;i<3;i++)
num[i].top=-1;/*三个地方的高度开始都为-1*/
for(i=0;i<n;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();
}

Answer 2

汉诺塔问题的非递归非堆栈算法（一）
＃i nclude <iostream.h>
＃i nclude <math.h>
#define maxno 10000
int step_d,step_s,no;//定义将要行进的步数
void main()
{
cout<<"请输入数字（1－64）：";
cin>>no;//获取实际的塔片数
//初始化

int **p=new int*[3];

p[0]=new int[no+1];

p[1]=new int[no+1];

p[2]=new int[no+1];
p[0][0]=maxno;p[1][0]=maxno;p[2][0]=maxno;
for(int count=1;count<=no;count++)
{
p[0][count]=no-count+1;
p[1][count]=0;
p[2][count]=0;
}
//初始化完毕
if(fmod(no,2)){step_s=2;step_d=1;}else {step_s=1;step_d=2;}//判断奇数盘的步数和偶数盘的步数
int from,to;
from=0;
to=step_s+from;
p[0]=&p[0][no];
while(*(p[0]) != *(p[1]))
{
cout<<"从柱："<<from+1<<" 到柱: "<<to+1<<endl;
*(++p[to])=*(p[from]);
*(p[from]--)=0;
//以下求得下一步将要From移动的柱子
switch(to)
{
case 2:
if(*(p[0]) < *(p[1]))from=0;else from=1;
break;
case 1:
if(*(p[0]) < *(p[2]))from=0;else from=2;
break;
case 0:
if(*(p[2]) < *(p[1]))from=2;else from=1;
break;
}
//以下一行求得下一步将要移动到的柱子
if(fmod(*(p[from]),2))to=fmod(from+step_s,3);else to=fmod(from+step_d,3);
}
char c;
cin>>c;
}

汉诺塔问题的非递归非堆栈算法（二）

前一种方法的/*原理：
如果把三个柱子围成一个环，盘子总数为N，其移动的规律是：
如果N为偶数：奇数号盘每次2步；偶数号盘每次1步；
如果N为奇数：奇数号盘每次1步；偶数号盘每次2步；
至于下一步该移动哪个柱子上的盘子，通过大小和顺序即可判断。

以上可以通过数学证明，不赘述！
*/

以下是第二种算法：

＃i nclude <iostream.h>
＃i nclude <math.h>
void main(){
int tt = 1,ff=1,fff=1,t;
cout<<"请输入（1-64）：";
cin>> t;
cout<<"F：表示盘子的起始柱子既From的意思"<<endl;
cout<<"T：表示盘子的目标柱子既To的意思"<<endl;
cout<<"o：表示在这一步中没有用到的柱子"<<endl<<endl;
for(int i1=1;i1<=t;i1++,ff*=2 );
char **hand;
hand=new char*[ff + 1];
for(int i2=0;i2<ff+1;i2++) hand[i2] = new char[4];
//char **hand=new char[ff + 1][ 4];
hand[0][1] = ''O'';
hand[0][2] = ''O'';
hand[0][3] = ''O'';
hand[1][1] = ''F'';
hand[1][2] = ''o'';
hand[1][3] = ''T'';
for(int i = 2;i<= t;i++){
tt ++;
if(fmod(i,2) == 0){
hand[tt][ 1] = ''F'';
hand[tt][ 2] = ''T'';
hand[tt][ 3] = ''o'';
}
else{
hand[tt][ 1] = ''F'';
hand[tt][ 3] = ''T'';
hand[tt][ 2] = ''o'';
}
fff=1;
for(int h=1;h<=i-1;h++,fff*=2);
for(int ii = 1;ii<= fff - 1;ii++)
{tt ++; <br/>if(fmod(i, 2)== 0){ <br/>hand[tt][ 1] = hand[ii][ 2]; <br/>hand[tt][ 2] = hand[ii][ 3]; <br/>hand[tt][ 3] = hand[ii][ 1];}
else{
hand[tt][ 1] = hand[ii][ 3];
hand[tt][ 2] = hand[ii][ 1];
hand[tt][ 3] = hand[ii][ 2];
}
}
}
if(fmod(t, 2) == 0){//调换位置
for(int i = 1;i<=tt;i++){
hand[i][ 0] = hand[i][ 2];
hand[i][ 2] = hand[i][ 3];
hand[i][ 3] = hand[i][ 0];}
}
for(int u=1;u<ff;u++ )
cout<<u<<": "<<hand[u][1]<<" "<<hand[u][2]<<" "<<hand[u][3]<<" "<<endl;
cin>>fff;
}
}

Answer 3

#include <stdio.h>
void move(int n,char a,char b,char c)
{
if(n==1)
printf("%d%c-->%c\n",n,a,c);
else
{
move(n-1,a,c,b);
printf("%d%c-->%c\n",n,a,c);
move(n-1,b,a,c);
}
}
int main()
{
int n;
scanf("%d",&n);
move(n,'a','b','c');
printf("Press any key to quit!");getchar();
getchar();
return 0;}

Answer 4

我是自在风舞的朋友，他补充3次后不能再补了。让我帮他回答。他说本来想发带解释的。但好像有字数限制没有发成。让我帮他发一下。
#include <stdio.h>
void move(int n,char a,char b,char c)//该问题时把A上的n各盘通过B搬到C
{
static int m=1;//设置一个静态变量，用于计算步数
//如果只有一个，就可以直接把A上的盘搬过去，输出是第几步，怎么移动。计数器加1
if(n==1)
{printf("%3d: %c-->%c\n",m,a,c);<br/>m++;}
//若n>1的话，就要分3步进行，第一步把A上的n-1个移动到B上；
//第二步，把A上的最后一个移动到C；第三步，把B上的n-1个移动到C
else
{
move(n-1,a,c,b);
printf("%3d: %c-->%c\n",m,a,c);m++;//也可以用move(1,a,b,c);
move(n-1,b,a,c);
}
}
int main()
{
int n;
printf("Put in the number of disks:");
scanf("%d",&n);//输入盘数；
move(n,'a','b','c');
printf("Press any key to quit!");getchar();
getchar();
return 0;}

Answer 5

#include <stdio.h>
#include <stdlib.h>
#define N 4

int count = 1;
int ldx(int, int);
void MoveHanoi(int, char, char);
void Hanoi(char, char, char);

int main()
{
char a = 'A',b = 'B',c = 'C';
Hanoi(a, b, c);
return 0;
}

int ldx(int a,int x)
{
int sum = 1;
for (; x > 0; x--)
{
sum *= a;
}
return sum;
}

void MoveHanoi(int j, char ch1, char ch2)
{
printf("%d (%c,%c)%d\n", j, ch1, ch2, count++);
}

void Hanoi(char a,char b,char c)
{
int n = 1,j = 1;
char temp;
if (!(N % 2))
{
temp = b;
b = c;
c = temp;
}
while (n < ldx(2,N))
{
j = 1;
while (j <= N)
{
if (n % ldx(2,j) == ldx(2,j-1))
{
if (j % 2 == 1)
{
if (n % (3 * ldx(2,j)) == ldx(2,j-1))
{
MoveHanoi(j,a,c);
break;
}
if (n % (3 * ldx(2,j)) == 3 * ldx(2,j-1))
{
MoveHanoi(j,c,b);
break;
}
if (n % (3 * ldx(2,j)) == 5 * ldx(2,j-1))
{
MoveHanoi(j,b,a);
break;
}
j++;
}
else
{
if (n % (3 * ldx(2,j)) == ldx(2,j-1))
{
MoveHanoi(j,a,b);
break;
}
if (n % (3 * ldx(2,j)) == 3 * ldx(2,j-1))
{
MoveHanoi(j,b,c);
break;
}
if (n % (3 * ldx(2,j)) == 5 * ldx(2,j-1))
{
MoveHanoi(j,c,a);
break;
}
j++;
}
}
else j++;
}
n++;
}
}
我这个你试试。我调试的没问题