欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言 汉诺塔问题

程序员文章站 2022-07-09 18:02:42
//凯鲁嘎吉 - 博客园 http://www.cnblogs.com/kailugaji/ 汉诺塔是由三根杆子A,B,C组成的。A杆上有n个(n>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:每次只能移动一个圆盘;大盘不能叠在小盘上面。提示:可将圆盘临时置于B杆,也可将 ......

     //凯鲁嘎吉 - 博客园 http://www.cnblogs.com/kailugaji/  

    汉诺塔是由三根杆子A,B,C组成的。A杆上有n个(n>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:每次只能移动一个圆盘;大盘不能叠在小盘上面。提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。问:如何移?最少要移动多少次?

C语言 汉诺塔问题

分析:

(1)将A上n-1个盘子借助C移动到B;

(2)将A剩下的一个盘子移动到C;

(3)将B上n-1个盘子借助A移动到C。

程序实现如下:

 1 #include<stdio.h>
 2 
 3 int sum=0;  //全局变量
 4 
 5 void move(char x,char y){
 6     printf("%c-->%c\n",x,y);
 7     sum=sum+1;
 8 }
 9 
10 int hanoi(int n,char a,char b,char c){
11     if(n==1){
12         move(a,c);
13     }
14 
15     else{
16         hanoi(n-1,a,c,b);
17         move(a,c); 
18         hanoi(n-1,b,a,c);
19     }
20 }
21 void main(){
22     int m;
23 
24     printf("Please input a number:");
25     scanf("%d",&m);
26 
27     printf("The step to moving %d disks:\n",m);
28     hanoi(m,'A','B','C');
29     printf("It need %d steps\n",sum);
30 }

结果为:

C语言 汉诺塔问题