經典算法系列---hanoi塔問題

河内之塔(Towers of Hanoi)是法國人M.Claus(Lucas)于1883年從泰國帶至法國的，河内為越戰時

北越的首都，即現在的胡志明市； 1883年法國數學家 Edouard Lucas曾提及這個故事，據說創世

紀時Benares有一座波羅教塔，是由三支鑽石棒（Pag）所支撐，開始時神在第一根棒上放置64

個由上至下依由小至大排列的金盤（Disc），并指令僧侶将所有的金盤從第一根石棒移至第三根

石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當盤子全數搬

運完畢之時，此塔将毀損，而也就是世界末日來臨之時。

事實上，若有n個盤子，則移動完畢所需之次數為2^n - 1，是以當盤數為64時，則

所需次數為：2^64- 1 = 18446744073709551615為5.05390248594782e+16年，也就是約5000世 紀 ，

如果對這數字沒什幺概念，就假設每秒鐘搬一個盤子好了，也要約5850億年左右。

有一個hanoi塔的網頁遊戲可以玩一下，對了解算法有好處：http://www.4399.com/flash/109504_1.htm

算法分析：

1)n=1時
h(1,A,B,C)  A-->C

2)n=2時 
h(2,A,B,C)
{
	h(1,A,C,B)  A-->B
        frintf(将2由A-->C);
        h(1,B,A,C)  B-->C
}

3) n=3時
h(3,A,B,C)
{
	h(2,A,C,B)
	{
		h(1,A,B,C)  A-->C
		frintf(将2由A-->B);
		h(1,C,A,B)  C-->B
	}
	frintf(将3由A-->C);
	h(2,B,A,C)
	{
		h(1,B,C,A)  B-->A
		frintf(将2由B-->C);
		h(1,A,B,C)  A-->C
	}
} 

4)n=n時
h(n,A,B,C)
{
	h(n-1,A,C,B)
	{
		......
	}
	printf(将n由A-->C)
	h(n-1,B,A,C)
	{
		......
	}
}
           

由上面的分析可以看出：

當n > 1時，我們分三個階段：

1：将A塔座上的n-1個圓盤按照規定移至到B塔座

2：将編号為n的圓盤由A座移至C座

3：利用A塔座，将B塔座上的n-1個圓盤按規定移至到C塔座

如何将n-1個圓盤由一個塔座移至到另一個塔座是一個和原問題有相同特征屬性的問題，隻是問題的規模小些，我們可以用同樣的方法求解，即用到遞歸函數

c語言實作：

#include<stdio.h>

void hanoi(int n,char A,char B,char C)
{
    if(n==1)
    {
        printf("Move sheet %d from %c to %c\n",n,A,C);
    }
    else
    {
        hanoi(n-1,A,C,B);
        printf("Move sheet %d from %c to %c\n",n,A,C);
        hanoi(n-1,B,A,C);
    }
}
int main()
{
    int n;
    printf("請輸入盤數：");
    scanf("%d",&n);
    hanoi(n,'A','B','C');
    return 0;
}