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

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

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

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

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

第3步可以分解為：
3．1將B上1個(gè)盤(pán)子從B移到A上；
3．2將B上1個(gè)盤(pán)子從B移到C上；
3．3將A上1個(gè)盤(pán)子從A移到C上。

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