C語言 漢諾塔問題

     //凱魯嘎吉 - 博客園 http://www.cnblogs.com/kailugaji/  

    漢諾塔是由三根桿子A，B，C組成的。A桿上有n個(n>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿：每次只能移動一個圓盤；大盤不能疊在小盤上面。提示：可將圓盤臨時置於B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須尊循上述兩條規則。問：如何移？最少要移動多少次？

分析：

（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 }

結果為：