汉诺塔问题

时间: 1ms        内存:128M

描述:

汉诺塔问题是指:一块板上有三根针 A、B、C。A 针上套有 64 个大小不等的圆盘,按照大的在下、小的在上的顺序排列,要把这 64 个圆盘从 A 针移动到 C 针上,每次只能移动一个圆盘,移动过程可以借助 B 针。但在任何时候,任何针上的圆盘都必须保持大盘在下,小盘在上。从键盘输入需移动的圆盘个数,给出移动的过程。

对于汉诺塔问题,当只移动一个圆盘时,直接将圆盘从 A 针移动到 C 针。 

若移动的圆盘为 n(n>1),则分成几步走:把 (n-1) 个圆盘从 A 针移动到 B 针(借助 C 针);A 针上的最后一个圆盘移动到 C 针;B 针上的 (n-1) 个圆盘移动到 C 针(借助 A 针)。每做一遍,移动的圆盘少一个,逐次递减,最后当 n 为 1 时,完成整个移动过程。 

因此,解决汉诺塔问题可设计一个递归函数,利用递归实现圆盘的整个移动过程,问题的解决过程是对实际操作的模拟。 

主函数已给出: 

#include <stdio.h>
int main()
{
    int hanoi(int,char,char,char);
    int n,counter;
    scanf(“%d”,&n);
    counter=hanoi(n,’A’,’B’,’C’);
    return 0;
}


输入:

输入需移动的圆盘个数

输出:

移动的过程

示例输入:

3

示例输出:

  1 # A---C
  2 # A---B
  1 # C---B
  3 # A---C
  1 # B---A
  2 # B---C
  1 # A---C

提示:

参考答案(内存最优[1120]):

#include <stdio.h>
int main()
{
    int hanoi(int,char,char,char);
    int n,counter;
    scanf("%d",&n);
    counter=hanoi(n,'A','B','C');
    return 0;
}
int hanoi(int n,char x,char y,char z)
{
    int move(char,int,char);
    if(n==1)
        move(x,1,z);
    else
    {
        hanoi(n-1,x,z,y);
        move(x,n,z);
        hanoi(n-1,y,x,z);
    }
    return 0;
}
int move(char getone,int n,char putone)
{
    int k=1;
    printf("%3d # %c---%c\n",n,getone,putone);
    return 0;
}

参考答案(时间最优[2]):

#include <stdio.h>
int main()
{
    int hanoi(int,char,char,char);
    int n,counter;
    scanf("%d",&n);
    counter=hanoi(n,'A','B','C');
    return 0;
}
int hanoi(int n,char x,char y,char z)
{
    int move(char,int,char);
    if(n==1)
        move(x,1,z);
    else
    {
        hanoi(n-1,x,z,y);
        move(x,n,z);
        hanoi(n-1,y,x,z);
    }
    return 0;
}
int move(char getone,int n,char putone)
{
    int k=1;
    printf("%3d # %c---%c\n",n,getone,putone);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。