C语言汉诺塔问题，用C语言实现汉诺塔

汉诺塔问题是指：一块板上有三根针 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;

 printf( Input the number of diskes： 

 scanf( %d , 

 printf( /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)

 static int k=1;

 printf( %2d:%3d # %c---%c/n ,k,n,getone,putone);

 if(k++%3==0)

  printf( /n 

 return 0;

}

调试运行结果

当移动圆盘个数为 3 时，具体移动步骤如下所示：

Input the number of diskes：3

1:  1 # A C
2:  2 # A B
3:  1 # C B

4:  3 # A C
5:  1 # B A
6:  2 # B C

7:  1 # A C

本实例中定义的 hanoi() 函数是一个递归函数，它有四个形参 n x y z 。 n 是移动的圆盘个数， x y z 分别表示三根针，其功能是把 x 上的 n 个圆盘移动到 z 上。当 n=1 时，直接把 x 上的圆盘移到 z 上，输出 x Z 。当 n!=1 时，则递归调用 hanoi() 函数，把 (n-1) 个圆盘从 x 移到 y，输出 x -z ；再递归调用 hanoi() 函数，把 (n-1) 个圆盘从 y 移到 z。在递归调用函数的过程中 n=n-1 ，n 的值逐次递减，最后 n=1，终止递归调用，逐层返回，移动过程结束。

21176.html