漢諾塔問題的遞歸求解

漢諾塔問題的C++實現

#include<iostream>

using namespace std;

char A,B,C;

int main()

{

int n;

void hano(int,char,char,char);

cout<<"請輸入A座上的盤子數目：";

cin>>n;

hano(n,A,B,C);

return 0;

}

void print(char A,char C)

{

cout<<A<<"--"<<C<<endl;

}

void hanoi(int n,char A,char B,char C)

{

if(n==1)

print(A,C);

else

{

hanoi(n-1,A,C,B);

print(A,C);

hanoi(n-1,B,A,C);

}

}

說明：

　　 規模為n的漢諾塔問題可以寫成兩個規模為n-1的漢諾塔問題的和。也就是說若用H(n)表示規模為n的漢諾塔問題的解的話，則H(n)= 2H(n-1)+1。最後加的1就是printf("%d->%d
",a,c);的含義。

以上就是漢諾塔問題的數學模型，比較抽象。

就以Hanoi(4,1,2,3)舉例來說：1、2、3分別代表可以存放盤子的底座的編號，4表示剛開始時第1個底座有4個盤子，a、b、c分別代表：問題開始時的原來存放盤子的底座、臨時底座、問題結束時盤子存放的底座。那麼怎麼將第1個底座上4個盤子移動到第3個底座上呢？

按照上面的模型，分成三步：

（1）將第1個底座的最上面的3個盤子移動到第2個底座上；

（2）將第1個底座上剩下的1個盤子直接放到第3個底座上；

（3）將第2個底座上的3個盤子移動到第三個底座上；

上面三個過程實際上就對應到你的Hanoi(...)函數的中的三個語句。

第(1)、(3)步就是相當於原來問題的兩個變形。可以把第(1)步理解為：將n-1個盤子從第1個底座搬到第2個底座的漢諾塔問題，這樣問題有3個變化的地方和1個不變的地方：盤子總數減少了1、要將盤子移動到的目標底座變成了第2個底座了、臨時底座變成了第3個底座了、問題的本質上還是漢諾塔問題，這個不變很重要，它是問題可以遞歸求解的關鍵，也就是說可以用不同的參數來調用同一個函數來解決。對應到Hanoi(...)函數的4個參數中的3個變化。

完成了前面兩步後，顯然問題並沒有解決，所以才有第(3)步，也就是第二個遞歸。同樣的道理第(3)步可以理解為：將n-1個盤子從第2個底座搬到第三個底座的漢諾塔問題了。只不過與第一個遞歸不同的是：原來的第2個底座相當於原來的第1個底座、原來的第1個底座相當於現在的第2個底座了。

補充：對於初學者來說，求解漢諾塔問題的方法其實很簡單，但是求解的細節卻很繞人，1、2、3與a、b、c的關係就不太好理解。個人認為搞清楚形式參數與實際參數的關係會對理解程序代碼有幫助。直觀的來看，123就是實際參數，abc就是形式參數。由前面內容可以看出，其實123和abc的意義在每一層遞歸調用中的含義是不同的，但就Hanoi(int n,int

a,int b,int c)而言，每次調用它都是把當前要移動的盤子總數傳給n、盤子初始位置傳給a、目標位置傳給c。進入Hanoi函數內部以後，問題被分解為「三步走」這樣abc的具體含義在遞歸調用時就變化了。

推薦閱讀：