例8.9   Hanoi(漢諾)塔問題。這是一個古典的數(shù)學(xué)

問題，是一個只有用遞歸方法(而不可能用其他方法)解決的問題。問題是這樣的：古代有一個梵塔，塔內(nèi)有3個座A、B、C，開始時A座上有64個盤子，盤子大小不等，大的在下，小的在上(圖7.13)。有一個老和尚想把這64個盤子從A座移到C座，但每次只允許移動一個盤，且在移動過程中在3個座上都始終保持大盤在下，小盤在上。在移動過程中可以利用B座，要求編程序打印出移動的步驟。

可以肯定地說：任何一個人(包括“天才”) 都不可能直接寫出移動盤子的每一個具體步驟。請讀者試驗一下按上面的規(guī)律將5個盤子從A座移到C座，能否直接寫出每一步驟?老和尚自然會這樣想：假如有另外一個和尚能有辦法將63個盤子從一個座移到另一座。那么，問題就解決了。此時老和尚只需這樣做：
(1) 命令第2個和尚將63個盤子從A座移到B座；
(2) 自己將1個盤子(最底下的、最大的盤子)從A座移到C座；
(3) 再命令第2個和尚將63個盤子從B座移到C座。
      至此，全部任務(wù)完成了。這就是遞歸方法。但是，有一個問題實際上未解決：第2個和尚怎樣才能將63個盤子從A座移到B座?為了解決將63個盤子從A座移到B座，第2個和尚又想：如果有人能將62個盤子從一個座移到另一座，我就能將63個盤子從A座移到B座，他是這樣做的：
(1) 命令第3個和尚將62個盤子從A座移到C座；
(2)  自己將1個盤子從A座移到B座；
(3) 再命令第3個和尚將62個盤子從C座移到B座。
    再進行一次遞歸。如此“層層下放”， 直到后來找到第63個和尚，讓他完成將2個盤子從一個座移到另一座，進行到此，問題就接近解決了。最后找到第64個和尚，讓他完成將1個盤子從一個座移到另一座，至此，全部工作都已落實，都是可以執(zhí)行的。可以看出，遞歸的結(jié)束條件是最后一個和尚只需移一個盤子。否則遞歸還要繼續(xù)進行下去。

應(yīng)當(dāng)說明，只有第64個和尚的任務(wù)完成后，第63個和尚的任務(wù)才能完成。只有第2到第64個和尚任務(wù)完成后，第1個和尚的任務(wù)才能完成。這是一個典型的遞歸的問題。為使問題簡化，我們先分析將A座上3個盤子移到C座上的過程：
(1) 將A座上2個盤子移到B座上(借助C)；
(2) 將A座上1個盤子移到C座上；
(3) 將B座上2個盤子移到C座上(借助A)。

其中第2步可以直接實現(xiàn)。第1步又可用遞歸方法分解為：
1．1將A上1個盤子從A移到C；
1．2將A上1個盤子從A移到B；
1．3將C上1個盤子從C移到B。

第3步可以分解為：
3．1將B上1個盤子從B移到A上；
3．2將B上1個盤子從B移到C上；
3．3將A上1個盤子從A移到C上。

將以上綜合起來，可得到移動3個盤子的步驟為
A→C，A→B，C→B，A→C，B→A，B→C，A→C。
共經(jīng)歷7步。由此可推出：移動n個盤子要經(jīng)歷2n-1步。如移4個盤子經(jīng)歷15步，移5個盤子經(jīng)歷31步，移64個盤子經(jīng)歷264-1步。
　　由上面的分析可知：將n個盤子從A座移到C座可以分解為以下3個步驟：
(1) 將A上n-1個盤借助C座先移到B座上。
(2) 把A座上剩下的一個盤移到C座上。
(3) 將n-1個盤從B座借助于A座移到C座上。
　　上面第1步和第3步，都是把n-1個盤從一個座移到另一個座上，采取的辦法是一樣的，只是座的名字不同而已。為使之一般化，可以將第1步和第3步表示為：
“將“one” 座上n-1個盤移到“two” 座(借助“three” 座)。只是在第①步和第③步中，one、two、three和A、B、C的對應(yīng)關(guān)系不同。對第①步，對應(yīng)關(guān)系是one——A，two——B，three——C。對第③步，是：one——B，two——C，three——A。
因此，可以把上面3個步驟分成兩類操作：
(1) 將n-1個盤從一個座移到另一個座上(n>1)。這就是大和尚讓小和尚做的工作，它是一個遞歸的過程，即和尚將任務(wù)層層下放，直到第64個和尚為止。
(2) 將1個盤子從一個座上移到另一座上。這是大和尚自己做的工作。
　　下面編寫程序。分別用兩個函數(shù)實現(xiàn)以上的兩類操作，用hanoi函數(shù)實現(xiàn)上面第1類操作(即模擬小和尚的任務(wù))，用move函數(shù)實現(xiàn)上面第2類操作(模擬大和尚自己移
盤)，函數(shù)調(diào)用hanoi(n，one，two，three)表示“將n個盤子從“one” 座移到“three” 座的過程(借助“two”針”)。函數(shù)調(diào)用move(x，y)表示將1個盤子從x 座移到y(tǒng) 座的過程。x和y是代表A、B、C座之一，根據(jù)每次不同情況分別取A、B、C代入。
　　程序如下：
void move(char x，char y)
      ｛
      　printf("%c-->%c\n"，x，y)；
        ｝
       void hanoi(int n，char one，char two，char three)
/*將n個盤從one座借助two座，移到three座