精品資料（2021-2022年收藏）課程設(shè)計漢諾威塔

1、摘要：漢諾塔問題源于印度古老的一個傳說。相傳開天辟地的神勃拉瑪創(chuàng)造世界時在印度北部的佛教圣地的圣廟里，安放了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。值班僧侶按照法則日夜不停地搬運，當搬運完成時世界將在一聲霹靂中毀滅。傳說固然只是傳說，這個古老的故事到今天又引申出一連串的包括統(tǒng)籌、管理等等數(shù)學(xué)問題。在現(xiàn)實生活中，任何一個人都不可能直接寫出移動盤子的每一個具體步驟。比較經(jīng)典的使用遞歸算法也是在這方面做了大量研究得出的

2、一種相對優(yōu)化的算法方案。本文主要從圖形學(xué)的角度對這個問題作了一些簡單的探討。整個程序采用了自頂向下，逐步細化的設(shè)計方法。主要分為三個模塊：圖形環(huán)境初始化、問題求解、以及過程動畫演示。程序能夠處理用戶輸入的不同初始值使需要搬動的盤子數(shù)初始化。初始化圖形采用點陣方式直接寫屏。關(guān)鍵詞 漢諾塔，遞歸思想 函數(shù)調(diào)用，演示目錄背景知識31設(shè)計目的和要求4 1.1設(shè)計要求4 1.2設(shè)計要求42 系統(tǒng)設(shè)計5 2.1漢諾威塔問題5 2.2設(shè)計思路5 2.3算法分析63 流程及程序設(shè)計10 3.1流程圖10 3.2模塊及功能114 詳細設(shè)計135 系統(tǒng)實現(xiàn)305 系統(tǒng)實現(xiàn)306 小結(jié)347 參考文獻35背景知識：

3、漢諾塔（又稱河內(nèi)塔）問題來自中東地區(qū)一個古老的傳說：開天辟地的神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。解答結(jié)果請自己運行計算，程序見尾部。面對龐大的數(shù)字(移動圓片的次數(shù))18446744073709551615，看來，眾僧們耗盡畢生精力也不可能完成金片的移動。后來，這個傳說就演變?yōu)闈h諾塔游戲。19世紀的法國大數(shù)學(xué)家魯卡曾經(jīng)研究過這個問題，他正確地指出，要完成這個任務(wù)，僧侶們搬動金盤的總次數(shù)

4、（把1個金盤從某個塔柱轉(zhuǎn)移到另1個塔柱叫做1次）為：18，446，744，073，709，551，615次。假設(shè)僧侶們個個身強力壯，每天24小時不知疲倦地不停工作，而且動作敏捷快速，1秒鐘就能移動1個金盤，那么，完成這個任務(wù)也得花5800億年！1 設(shè)計目的和要求1.1設(shè)計目的隨著計算機技術(shù)以及外圍設(shè)備的發(fā)展，計算機在輔助設(shè)計制造，計算機教育，計算機信息化應(yīng)用中，圖形的作用和魅力愈加顯現(xiàn)。如何運用計算機技術(shù)、運用算法編程來優(yōu)化解決低階漢諾威塔問題對我們學(xué)生來說具有可實現(xiàn)和可操作性。本次課程設(shè)計的目的就是利用所學(xué)習(xí)到得算法知識和編程語言知識來解決、實現(xiàn)低階漢諾威塔問題。1.2設(shè)計要求1.2.1功能

5、要求 能夠?qū)崿F(xiàn)按用戶需要對輸入的不同盤子數(shù)量進行處理。 能夠?qū)崿F(xiàn)根據(jù)輸入條件，給出完整的解決方案。 能夠?qū)崿F(xiàn)每一個搬運步驟的演示。1.2.2環(huán)境要求 能夠在windows操作系統(tǒng)下正常運行。有友好的界面用戶能接受的簡單的操作。2.系統(tǒng)設(shè)計2.1漢諾威塔問題n階漢諾威塔問題：有三個柱子A, B, C。A柱子上疊放有n個盤子，每個盤子都比它下面的盤子要小一點，可以從上到下用1, 2, ., n編號。要求借助柱子C，把柱子A上的所有的盤子移動到柱子B上。移動條件為：1、一次只能移一個盤子；2、移動過程中大盤子不能放在小盤子上，只能小盤子放在大盤子上如3階漢諾塔的移動：AC,AB,CB,AC,BA,B

6、C,AC2.2設(shè)計思路ABC圖2.1 漢諾塔對于一個類似的這樣的問題，任何一個人都不可能直接寫出移動盤子的每一個具體步驟?？梢岳眠@樣的統(tǒng)籌管理的辦法求解：我們假設(shè)把該任務(wù)交給一個僧人，為了方便敘述，將他編號為64。僧人自然會這樣想：假如有另外一個僧人能有辦法將63個盤子從一個座移到另一個座，那么問題就解決了，此時僧人64只需這樣做：1. 命令僧人63將63個盤子從A座移到C座2. 自己將最底下的最大的一個盤子從A座移到C座3. 再命令僧人63將63個盤子從B座移到C座為了解決將63個盤子從A座移到B座的問題，僧人63又想：如果能再有一個僧人62能將62個盤子移動到另一座，我就能將63個盤子從

7、A座移動到B座。他是這樣做的：1. 命令僧人62將62個盤子從A移動到C2. 自己將一個盤子從A座移動到B座3. 再命令僧人62將62個盤子移到B座再進行一次遞歸。如此“層層下放”，直到后來找到第2個僧人，讓他完成將2個盤子從一個座移到另一個座，進行到此，問題就解決了。最后找到第1個僧人，讓他完成將一個盤子從一個座移動到另一個座，至此，全部工作已經(jīng)完成，都是可以執(zhí)行的。按照如此的思路設(shè)計遞歸算法，很容易得出盤子的移動方案。2.3算法分析設(shè)A上有n個盤子。 當n=1時，則將圓盤從A直接移動到C。 當n大于等于2時，移動的過程可分解為三個步驟： 第一步 把A上的n-i個圓盤移到B上； 第二步 把A

8、上的一個圓盤移到C上； 第三步 把B上的n-i個圓盤移到C上；其中第一步和第三步是類同的。 為了更清楚地描述算法，用圖示法描述如下：將N個盤子從A桿上借助C桿移動到B桿上。這樣移動N個盤子的工作就可以按照以下過程進行：第一次調(diào)用遞歸 將一個盤子從A移動到B上；第二次調(diào)用遞歸重復(fù)以上過程，直到將全部的盤子移動到位時為止。由遞歸算法我們可以得到遞推關(guān)系：M(n)=2M(n-1)+1 當n>1時M(n)=1 當n=1時下面用歸納法證明n階漢諾威塔問題，可以用n層二叉樹描述，而且它的解就是該二叉樹的中序遍歷序列。用一個四元組(n,A,B,C)表示把n個盤子從A搬到C,中間可以借助B的n階漢諾威塔

9、問題。其中A、B、C的地位是相對的，第一個表示起始位置，最后一個表示終止位置，中間表示過渡位置。例如(n,A,B,C)表示把n個盤子從B搬到C，中間可以借助A的n階漢諾威塔問題。用一個三元組(n),A,B)表示把第n個盤子從A直接搬到B。假設(shè)有兩個盤子，要把兩個盤子從A搬到C，即(2,A,B,C),就必須先把第1個盤子從A搬到B，即(1),A,B),再把第2個盤子從A直接搬到C，即(2),A,C),最后把第1個盤子從B直接搬到C，即(1),B,C),序列(1),A,B),(2),A,C),(1),B,C)正好是以(2,A,B,C)為根，以(1,A,C,B)和(1,B,A,C)為左右孩子的二叉樹

10、的中序遍歷序列(訪問結(jié)點時，去掉過渡位置，盤子數(shù)加括號)(見圖1)，其中雙親結(jié)點與左孩子的關(guān)系是，盤子個數(shù)減1，過渡位置和終止位置交換，與右孩子的關(guān)系是，盤子個數(shù)減1，起始位置和過渡位置交換。假如有n個盤子時，結(jié)論成立?，F(xiàn)在假設(shè)有n+1個盤子。要把n+1個盤子從A搬到C，即(n+1,A,B,C)，必須先把前n個盤子從A搬到C，即(n+1),A,C)，最后把前n個盤子從B搬到C，即(n,A,B,C)。序列(n,A,C,B),(n+1),A,C),(n,B,A,C)正好是以(n+1,A,B,C)為根，以(n,A,C,B)和(n,B,A,C)為左右孩子的二叉樹的中序遍歷順序(中序遍歷左子樹，訪問根結(jié)

11、點，中序遍歷右子樹)(見圖2)。而左右子樹都是n階漢諾威塔問題，結(jié)論也成立。到此證明完畢。（圖1） 2階漢諾威塔問題狀態(tài)樹（圖2） n階和3階漢諾威塔問題狀態(tài)樹3.流程及程序設(shè)計3.1流程圖：（如下圖所示）開始定義結(jié)構(gòu)體數(shù)組M存放盤號和塔座高度程序初始化輸入要演示的盤塊數(shù)nn<1|n>10n=10繪制塔座和盤塊調(diào)用遞歸函數(shù)hanoi( )n= =1?調(diào)用move( )函數(shù)將盤塊從A移到C將前n-1個盤塊從A移到B再將A的第n個盤塊移到C最后將B上的n-1個盤移到C結(jié) 束有上述流程圖得出實現(xiàn)遞歸函數(shù)過程的流程圖設(shè)計如下圖所示：開 始n= =1?將盤塊從A座移到C座將前n-1個盤塊從A

12、座移到B座再將A座的第n個盤塊移到C座最后將B座上的n-1個盤塊移到C座結(jié) 束3.2模塊及其功能介紹首先定義兩個類: Tower類（棧）Hanoi類（包含三個Tower類對象組成），程序中大部份功能函數(shù)封裝在這兩個類中（包括：遞歸算法Hanoi:Move()、圖形顯示函數(shù)Hanoi:Outlin()、移動演示函數(shù)Hanoi:MoveShow() 等 ）塔的盤子是字符串由（'=',' '）組成的另外還有一些函數(shù)：Push函數(shù)的功能是放入盤子， pop函數(shù)的功能是取出盤子重要函數(shù)的分析：void Move(int n,int A,int B,int C)遞歸 （這里

13、的A，B，C是相對的，不等同外面定義的A塔，B塔，C塔）if(n=1)/遞歸的終止條件move(A,C);/將A塔上的最后一個盤子盤子直接移動到C塔 elseMove(n-1,A,C,B);/將A塔上的n-1個盤子通過C塔移動到B塔 move(A,C);/將A塔上的最后一個盤子盤子直接移動到C塔 Move(n-1,B,A,C);/將B塔上的n-1個盤子通過A塔移動到C塔4.系統(tǒng)詳細設(shè)計：#include<iostream>#include<string>using namespace std;#include <stdlib.h>#define MAX 10

14、000struct Stackstring data;Stack *next;class Tower int floor; int broad;public:Stack *top; int Top; Tower(int store) floor=store; if(floor<6)broad=4+2*floor;else broad=2+2*floor;Top=0;string bro; for(int i=0;i<broad/2;i+) bro=bro+""Stack *temp=new Stack;temp->data=bro;temp->nex

15、t=top;top=temp; string OutFloor(int i)Stack *toptemp=top;for(int j=0;j<Top-i;j+)toptemp=toptemp->next;return toptemp->data; void push(string disc) Stack *temp=new Stack; temp->data=disc;temp->next=top;top=temp;Top+; string pop() Stack *temp;string x; if(top=NULL) return NULL;else x=to

16、p->data;temp=top;top=top->next;free(temp);Top-; return x; string disc(int space) string dis; for(int i=0;i<space;i+) dis=dis+' ' for(int j=space;i<broad-space;i+) dis=dis+'=' for(int k=broad-space;k<broad;k+) dis=dis+' ' return dis; ;class Hanoi int Store;int b

17、road; Tower *A;Tower *B;Tower *C; int step;int STEPMAX; void move(int A,int C) step+; STEPstep=A*10+C; void Move(int n,int A,int B,int C)if(n=1)move(A,C); elseMove(n-1,A,C,B); move(A,C); Move(n-1,B,A,C);public: Hanoi(int store) Store=store;if(Store<6)broad=4+2*Store;else broad=2+2*Store; A=new To

18、wer(store);for(int i=1;i<=Store;i+)A->push(A->disc(i); B=new Tower(store); C=new Tower(store);step=0;Move(Store,1,2,3); void OutStep()int StepTemp;cout<<"nt移動方法："<<endl;for(StepTemp=1;StepTemp<=step;StepTemp+)cout<<"nt"<<"第"<<St

19、epTemp<<"步："<<STEPStepTemp/10<<"->"<<STEPStepTemp%10<<"t"void Outlin() int i=Store; string space; for(int j=0;j<broad;j+) space=space+" " cout<<"nn"<<endl; while(i>=0) cout<<"t" if(A-

20、>Top>=i)cout<<A->OutFloor(i); else cout<<space; cout<<"t" if(B->Top>=i)cout<<B->OutFloor(i); else cout<<space; cout<<"t" if(C->Top>=i)cout<<C->OutFloor(i); else cout<<space; cout<<"n" i-; v

21、oid MoveShow() int Step=1;string ans; Outlin(); docout<<"nt第"<<Step<<"步："<<STEPStep/10<<"->"<<STEPStep%10<<endl; switch(STEPStep)case 12: B->push(A->pop();break; case 13: C->push(A->pop();break; case 21: A->pus

22、h(B->pop();break; case 23: C->push(B->pop();break; case 31: A->push(C->pop();break; case 32: B->push(C->pop(); Outlin(); if(Step<step)system("pause"); Step+;while(Step<=step);cout<<"n 演示完畢！(輸入任意字符退出)nn"cin>>ans;void GameMove()int from,go;Out

23、lin();docout<<"nt請輸入移動哪個塔（1，2，3）："cin>>from;while(from>3|from<1)cout<<"-_-!"cin>>from;cout<<"nt請輸入移到哪個塔（1，2，3）："cin>>go;while(go>3|go<1|go=from)cout<<"-_-!"cin>>go;int temp=from*10+go; switch(temp)cas

24、e 12:if(A->top->data<B->top->data)B->push(A->pop(); else cout<<"ERROR!"break; case 13:if(A->top->data<C->top->data)C->push(A->pop();else cout<<"ERROR!" break; case 21:if(B->top->data<A->top->data)A->push(B-&g

25、t;pop();else cout<<"ERROR!" break; case 23:if(B->top->data<C->top->data)C->push(B->pop();else cout<<"ERROR!" break; case 31:if(C->top->data<A->top->data)A->push(C->pop();else cout<<"ERROR!" break; case 32:if(C-

26、>top->data<B->top->data)B->push(C->pop();else cout<<"ERROR!" Outlin();while(C->Top!=Store);cout<<"你太強了！n"<<endl;system("pause");void Arithmetic();Hanoi *hanoi;void main() int cord1,cord2; do system("cls"); cout<<

27、"ttt 09醫(yī)學(xué)應(yīng)用3班 范國來（0907508307）n" cout<<"nttt 漢諾塔問題的動態(tài)演示 n"cout<<"nttt 1.建立漢諾塔n" cout<<"nttt 2.算法思想n" cout<<"nttt 3.結(jié)束程序n"cout<<"ttt - n" cout<<"ttt 請輸入你的選擇 (1,2,3)：" cin>>cord1;while(cord1&

28、gt;3|cord1<1)cout<<"-_-!"cin>>cord1; switch(cord1) case 1:int ans;cout<<"nttt 請輸入層數(shù)(1-10)："cin>>ans;if(ans<1) ans=1;if(ans>10) ans=10;hanoi=new Hanoi(ans);hanoi->Outlin();cout<<"n"<<endl;system("pause"); do syste

29、m("cls"); cout<<"nnnttt 漢諾塔 n" cout<<"nttt 1.開始演示n" cout<<"nttt 2.輸出步驟n"cout<<"nttt 3.游戲模式n" cout<<"nttt 4.返回主菜單n" cout<<"nttt 5.終止程序n" cout<<"ttt -n" cout<<"ttt 請輸入你的

30、選擇 (1,2,3,4,5)：" cin>>cord2;while(cord2>5|cord2<1)cout<<"-_-!" cin>>cord2; switch(cord2) case 1:system("cls");hanoi->MoveShow();delete hanoi;hanoi=new Hanoi(ans); break; case 2:system("cls");hanoi->OutStep();cout<<"n"&l

31、t;<endl;system("pause"); break;case 3:system("cls");hanoi->GameMove();delete hanoi;hanoi=new Hanoi(ans); break; case 4: break; case 5: exit(0); while(cord2<=5&&cord2!=4);delete hanoi;break; case 2:system("cls");Arithmetic(); break; case 3: exit(0); whil

32、e(cord1<=3); return;void Arithmetic()string ans;cout<<"nn"cout<<" 把N層塔看做兩部份：N-1,1(如圖所示) = | | "<<endl;cout<<" = n-1 n "<<endl;cout<<" = | | "<<endl;cout<<" = | "<<endl;cout<<" "

33、<<endl<<endl;cout<<" 1.把N-1部份移到B塔： "<<endl;cout<<" A B C "<<endl;cout<<" = "<<endl;cout<<" = "<<endl;cout<<" = = "<<endl;cout<<" "<<endl<<endl<<

34、endl;cout<<" 2.把最后一部份移到C塔： "<<endl;cout<<" A B C "<<endl;cout<<" = "<<endl;cout<<" = "<<endl;cout<<" = = "<<endl;cout<<" "<<endl<<endl;cout<<" 3.把N-1部份

35、移到C塔： "<<endl;cout<<" A B C "<<endl;cout<<" = "<<endl;cout<<" = "<<endl;cout<<" = "<<endl;cout<<" = "<<endl;cout<<" "<<endl<<endl;cout<<" 4.下面要做的就是通過1，2，3步結(jié)合遞歸思想，再分解N-1部分，直至N=1最簡情況"<<endl<<endl;cout<<" 補充：漢諾塔的實質(zhì)是棧都具有先進后出的性質(zhì)！"<<endl<<endl;cout<<"輸入任意字符退出"cin>>ans;5.系統(tǒng)實現(xiàn)：1.系統(tǒng)運行界面：（以9階塔為例）2.按任意鍵進入下一層界面：3.開始演示：按任意鍵直到演示完畢：4. 直接輸出搬運步驟：5. 漢諾威塔