引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2漢諾塔問題算法

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

(1)基于C語言的漢諾塔的算法實(shí)現(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++的漢諾塔的算法實(shí)現(xiàn)程序如下：

voidMove(inti,charx,chary)

{

fout?"把"《i?"號(hào)從"《x?"挪動(dòng)到”《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的漢諾塔的算法實(shí)現(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ù)學(xué)的思想來分析漢諾塔問題的算法

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

2基于組合數(shù)

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

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

第二步，將柱x上的最大一個(gè)盤移到柱z上，只要搬動(dòng)1次;

第三步，再?gòu)闹鵼將n-1個(gè)盤按要求移到柱z上，也要用an-1次。

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

3結(jié)語

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

20211022_6172dcded1f07__對(duì)漢諾塔