• 所有问题

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

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

    举报该问题
    推荐答案   2013-11-27
    #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();
    }
    温馨提示：答案为网友推荐，仅供参考
    其他回答
    第1个回答  2013-11-27
    汉诺塔问题的非递归非堆栈算法（一）
    ＃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;
    }
    }
    第2个回答  2013-11-27
    #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;}
    第3个回答  2013-11-27
    我是自在风舞的朋友，他补充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;}
    第4个回答  2013-11-27
    #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++;
    }
    }
    我这个你试试。我调试的没问题
    相似回答
    大家正在搜
    相关问题
    谁能解释一下C语言汉诺塔问题
    哪个高人给个非递归解决汉诺塔问题的，最好有解释，要纯C语言的...
    用C语言编程序解决汉诺塔问题
    c语言题目求助！！！汉诺塔问题
    c语言：求解汉诺塔问题
    在编写C语言程序求解汉诺塔问题时怎样表示每一步是第几步？
    汉诺塔问题，大神来看看啊，用c语言
    C语言汉诺塔问题