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",&n);
    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---%cn",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，終止遞回呼叫，逐層返回，移動過程結束。