漢諾塔的遞歸算法
假設(shè)有3個分別命名為X、Y和Z的塔座，在塔座X上插有n個直徑大小各不相同、依小到大編號為1、2…n的圓盤。現(xiàn)要求將X軸上的n個圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動時必須遵守下列規(guī)則：
1、每次只能移動一個圓盤；
2、圓盤可以插在X、Y和Z中任一塔座上；
3、任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。
遞歸算法的思路：
當(dāng)n=1時，問題比較簡單，只要將編號為1的圓盤從塔座X直接移至塔座Z上即可。
當(dāng)n>1時，需利用塔座Y作輔助塔座，若能設(shè)法將壓在編號為n的圓盤之上的n-1個圓盤從塔座X移至塔座Y上，則可先將編號為n的圓盤從塔座X移至塔座Z上，然后再將塔座Y上的n-1個圓盤移至塔座Z上。而如何將n-1個圓盤從一個塔座移至另一個塔座的問題是一個和原問題具有相同特征屬性的問題，只是問題的規(guī)模小1，因此可以用同樣的方法求解。
//從src移動第m個圓盤到dest底座上
void move(char src, int m, char dest){
cout<<"the disk "<<m<<" is moved from src "
<<src<<" to dest "<<dest<<endl;
}
//漢諾塔解法，將n個圓盤由x盤移動到z盤，y盤為輔助盤
void hanoi(int n, char x, char y, char z){
if(n==1)move(x,1,z);
else{
hanoi(n-1, x,z,y);
move(x,n,z);
hanoi(n-1, y,x,z);
}
}
int main(){
hanoi(3,'x','y','z');
return 0;
}
結(jié)果：
the disk 1 is moved from src x to dest z
the disk 2 is moved from src x to dest y
the disk 1 is moved from src z to dest y
the disk 3 is moved from src x to dest z
the disk 1 is moved from src y to dest x
the disk 2 is moved from src y to dest z
the disk 1 is moved from src x to dest z
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
