漢諾塔問(wèn)題是指：一塊板上有三根針 A、B、C。A 針上套有 64 個(gè)大小不等的圓盤，按照大的在下、小的在上的順序排列，要把這 64 個(gè)圓盤從 A 針移動(dòng)到 C 針上，每次只能移動(dòng)一個(gè)圓盤，移動(dòng)過(guò)程可以借助 B 針。但在任何時(shí)候，任何針上的圓盤都必須保持大盤在下，小盤在上。從鍵盤輸入需移動(dòng)的圓盤個(gè)數(shù)，給出移動(dòng)的過(guò)程。

算法思想
對(duì)于漢諾塔問(wèn)題，當(dāng)只移動(dòng)一個(gè)圓盤時(shí)，直接將圓盤從 A 針移動(dòng)到 C 針。若移動(dòng)的圓盤為 n(n>1)，則分成幾步走：把 (n-1) 個(gè)圓盤從 A 針移動(dòng)到 B 針（借助 C 針）；A 針上的最后一個(gè)圓盤移動(dòng)到 C 針；B 針上的 (n-1) 個(gè)圓盤移動(dòng)到 C 針（借助 A 針）。每做一遍，移動(dòng)的圓盤少一個(gè)，逐次遞減，最后當(dāng) n 為 1 時(shí)，完成整個(gè)移動(dòng)過(guò)程。

因此，解決漢諾塔問(wèn)題可設(shè)計(jì)一個(gè)遞歸函數(shù)，利用遞歸實(shí)現(xiàn)圓盤的整個(gè)移動(dòng)過(guò)程，問(wèn)題的解決過(guò)程是對(duì)實(shí)際操作的模擬。

程序代碼

#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---%c\n",k,n,getone,putone);
    if(k++%3==0)
        printf("\n");
    return 0;
}
調(diào)試運(yùn)行結(jié)果
當(dāng)移動(dòng)圓盤個(gè)數(shù)為 3 時(shí)，具體移動(dòng)步驟如下所示：
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
總結(jié)
本實(shí)例中定義的 hanoi() 函數(shù)是一個(gè)遞歸函數(shù)，它有四個(gè)形參"n""x""y""z"。"n" 是移動(dòng)的圓盤個(gè)數(shù)，"x""y""z" 分別表示三根針，其功能是把 x 上的 n 個(gè)圓盤移動(dòng)到 z 上。當(dāng) n=1 時(shí)，直接把 x 上的圓盤移到 z 上，輸出"x---Z"。當(dāng) n!=1 時(shí)，則遞歸調(diào)用 hanoi() 函數(shù)，把 (n-1) 個(gè)圓盤從 x 移到 y，輸出"x—-z"；再遞歸調(diào)用 hanoi() 函數(shù)，把 (n-1) 個(gè)圓盤從 y 移到 z。在遞歸調(diào)用函數(shù)的過(guò)程中"n=n-1"，n 的值逐次遞減，最后 n=1，終止遞歸調(diào)用，逐層返回，移動(dòng)過(guò)程結(jié)束。