對漢諾塔(Hanoi)問題的算法探索與研究

引言

大約在19世紀末，在歐州的商店中出售了一種智力玩具,該玩具在一塊銅板上有3根桿，最左邊的桿上自上而下、由小到大順序串著由64個圓盤構(gòu)成的塔，其目的是將最左邊桿上的盤全部移到右邊的桿上，條件是一次只能移動一個盤，且不允許大盤放在小盤的上面。

1問題分析與算法設(shè)計

漢諾塔(Hanoi)問題是一個著名的問題。64個圓盤按從小到大的順序依次套在柱x上，如圖1所示。規(guī)定每次只能從一根柱子上搬動一個圓盤到另一根柱子上，且要求在搬動過程中不許大盤放在小盤上，且只有x、y、z三根柱子可供使用。

由于一次只能移動一個盤，且不允許大盤放在小盤上面,所以64個盤的移動次數(shù)是1844674407370955615。

這是一個天文數(shù)字，若1us可計算(并不輸出)一次移動,那么也需要幾乎一百萬年。我們僅能找出問題的解決方法并解決較小N值時的漢諾塔問題，但很難用計算機解決64層的漢諾塔問題。

針對具體問題，我們必須找出移動盤子的正確算法。首先考慮x桿下面的盤子而非桿上最上面的盤子，于是任務(wù)變成:

將上面的63個盤子移到y(tǒng)桿上；

將x桿上剩下的盤子移到z桿上；

將y桿上的全部盤子移到z桿上。

將這個過程繼續(xù)下去，就是要先完成移動63個盤子、62個盤子、61個盤子……的工作。為了更清楚地描述算法，可以定義一個函數(shù)movedisc(n,a,b,c)。該函數(shù)的功能是：將N個盤子從x桿上借助z桿移動到y(tǒng)桿上。這樣，移動N個盤子的工作就可以按照以下過程進行:

movedisc(n-1,x,y,z)；

將一個盤子從x移到y(tǒng)上；

movedisc(n-1,z,y,x)；

重復(fù)以上過程，直到將全部的盤子移動到位時為止。

2漢諾塔問題算法

下面是基于三種語言的漢諾塔算法實現(xiàn)程序。

(1)基于C語言的漢諾塔的算法實現(xiàn)程序如下：

voidhanoi(intn,charx,chary,charz)

{

if(n==1)

move(x,1,z);

else{

hanoi(n-1,x,z,y);

move(x,n,z);

hanoi(n-1,y,x,z);

}

}

⑵基于C++的漢諾塔的算法實現(xiàn)程序如下：

voidMove(inti,charx,chary)

{

fout?"把"《i?"號從"《x?"挪動到”《y?endl;

}

voidHannoi(intn,charx,chary,charz)

{

if(n==1)

Move(1,x,z),

else

{

Hannoi(n-1,x,z,y);Move(n,x,z);

Hannoi(n-1,y,x,z);

}

}

intmain()

{

fout<<"下面是7層漢諾塔的解法:"<<endl;Hannoi(7,'x','y','z');

fout.close();

cout<<"輸出完畢！”《endl;return0;

}

(3)基于Java的漢諾塔的算法實現(xiàn)程序如下：publicclassHanoiTower{

staticintnDisks=3;

publicstaticvoidmain(String[]args){hanoiTower(nDisks,'x','y','z');

}

publicstaticvoidhanoiTower(inttopN,charsrc,charinter,chardest){

if(topN==1)

System.out.println("Disk1from"+src+"to"+dest);

else{

//srctointerhanoiTower(topN-1,src,dest,inter);

//movebottom

System.out.println("Disk"+topN+"from"+src+"to"+dest);

//intertodesthanoiTower(topN-1,inter,src,dest);

}

}

}

3用組合數(shù)學的思想來分析漢諾塔問題的算法

漢諾塔問題也是組合數(shù)學中著名的問題，用組合數(shù)學的思想分析如圖2所示。

2基于組合數(shù)

假設(shè)/=1,但=3,對于任何nN3,那么:可以作如下設(shè)計:

第一步，將套在柱x的上部的n—1個盤按要求移到柱y上，共搬動了次；

第二步，將柱x上的最大一個盤移到柱z上，只要搬動1次;

第三步，再從柱y將n-1個盤按要求移到柱z上，也要用an-1次。

則由加法法則，{an}滿足：

3結(jié)語

漢諾塔問題是一個古老的數(shù)學問題，本文給出了四種不同的的經(jīng)典算法，這幾種算法的優(yōu)點是邏輯清晰、易于理解、可讀性好、算法語句少，有助于讀者更好地對漢諾塔問題進行分析和探究。

20211022_6172dcded1f07__對漢諾塔