漢諾塔問題的非遞歸新解法-

1、漢諾塔問題的非遞歸算法計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)11-1 班張春穎(組長37 號劉丹(組員22 號漢諾塔問題的非遞歸新解法計(jì)11-1 張春穎37號劉丹22號摘要:漢諾塔問題是計(jì)算機(jī)算法設(shè)計(jì)中經(jīng)常被大家引用來說明遞歸算法的一個(gè)經(jīng)典問題,長期以來,很多人一直認(rèn)為這個(gè)問題只能用遞歸方法求解,從討論漢諾塔問題的幾個(gè)基本特性入手,通過分析和歸納總結(jié),提出了一種全新的解決漢諾塔問題的簡潔而又高效的非遞歸解法,并用具體的實(shí)例對其進(jìn)行了驗(yàn)證。關(guān)鍵詞:漢諾塔;非遞歸;對稱性;形式不變性一.漢諾塔問題及其特性漢諾塔問題可以一般地表述為:有3根針A,B,C,在A針上有n個(gè)大小互不相同的盤子,大盤在下,小盤在上,現(xiàn)在要將

2、這n個(gè)盤子全部移到C針上,規(guī)則是:每次只能移一個(gè)盤子,任何時(shí)候在每根針上都要保持大盤在下面小盤在上;移動過程可以利用針 B.請問該怎么移?漢諾塔問題是一個(gè)古典的數(shù)學(xué)問題,一般的參考文獻(xiàn)中都認(rèn)為漢諾塔問題是一個(gè)只能用遞歸方法解決的問題。漢諾塔問題具有遞歸性,但并不是說它就只能用遞歸方法來解決,為了尋求其非遞歸新解法,下面先來討論一下漢諾塔問題的幾個(gè)基本特性。1.漢諾塔問題的遞歸性將這n個(gè)盤子由小到大依次編號為:1,2,3,.N.為了將這n個(gè)盤子按照規(guī)則從針A 移動到針C.可以分3步走:第1步:將前n-1個(gè)盤子按照規(guī)則從針A移動到針B;第2步:將第n個(gè)盤子直接從針A移動到針C;第3步:將前n-1個(gè)

3、盤子按照規(guī)則從針B移動到針C;這樣一來,n個(gè)盤子的漢諾塔問題就轉(zhuǎn)化成了n-1個(gè)盤子的漢諾塔問題,而它們之間只是盤子的數(shù)目以及起點(diǎn)和終點(diǎn)有別而已。而n-1個(gè)盤子的漢諾塔問題又可以進(jìn)一步地轉(zhuǎn)化成n-2個(gè)盤子的漢諾塔問題。如此轉(zhuǎn)化下去,最終結(jié)果是:n個(gè)盤子的漢諾塔問題轉(zhuǎn)化成了一序列1個(gè)盤子的漢諾塔問題。2漢諾塔問題的對稱性由上述分析可見,n個(gè)盤子的漢諾塔問題可以轉(zhuǎn)化為兩個(gè)n-1個(gè)盤子的漢諾塔問題和一個(gè)1個(gè)盤子的漢諾塔問題,并且這1個(gè)盤子的漢諾塔問題正好處于那兩個(gè)n-1個(gè)盤子的漢諾塔問題的中間,因此,解決n個(gè)盤子的漢諾塔問題所需要的最少操作步數(shù)應(yīng)該是奇數(shù),而且所有操作步的操作對象按照順序應(yīng)該是中心對稱

4、的,對稱中心就是N號盤。3.漢諾塔問題的形式不變性一般地,設(shè)X,Y,Z為3根針,S為將n個(gè)盤子按照給定的規(guī)則從針X移到針Y所需的所有操作步的集合,如果用A,B,C的任意一個(gè)全排列K1,K2,K3去對應(yīng)替換S中的X,Y,Z:K1替換X,K2替換Y,K3替換Z,則得到的是將n個(gè)盤子按照同樣的規(guī)則從針K1移到K2所需的所有操作步集合。4.漢諾塔問題的輪換性設(shè)S為將n個(gè)盤子按照給定的規(guī)則從針A移到針B所需的所有操作步的集合,按照形式不變性,如果將S中的A全部換成B,B全部換成C,C全部換成A,則得到的是將N個(gè)盤子按照同樣的規(guī)則從針B移到針C所需的所有操作步的集合。同樣,如果將S中的A全部換成C,C全部

5、換成A,B保持不變,則得到的是將n個(gè)盤子按照同樣的規(guī)則從針C移到針B所需的所有操作步的集合。5.遞歸算法如下Void hanoi(int n,char x,char y,char z上按/將塔座x上按直徑由小到大且自上而下編號為1至nde 個(gè)圓盤按規(guī)則搬到塔/座z上,y可用作輔助塔座。搬動操作move(x,n,z可定義為(c是初值為0的 /全局變量,對搬動計(jì)數(shù);12 if(n=13 move(x,1,z;4 else5 hanoi(n-1,x,z,y;6 move(x,n,z;7 hanoi(n-1,y,x,z;8 9 但是遞歸看似簡潔,但是遞歸算法解題的運(yùn)行,效率較低,在遞歸調(diào)用的過程中系統(tǒng)

6、為每層的返回點(diǎn)、局部量等開辟了棧來存儲遞歸次數(shù)過多容易造成棧溢出,漢諾塔問題會多次用到遞歸,所以會發(fā)生棧溢出二.非遞歸解法的幾個(gè)基本問題根據(jù)遞歸性,我們很容易寫出漢諾塔問題的遞歸解,關(guān)于這一點(diǎn),很多高級語言的教科書都有涉及,下面我們專門來討論其非遞歸解問題。為了找到其非遞歸解,我們需要而且只需要解決下列3個(gè)問題:(1至少需要多少步操作?(2每一步的操作對象是誰?(3每一步操作的起點(diǎn)和終點(diǎn)又是誰?1.操作步數(shù)問題設(shè)將n個(gè)盤子按照規(guī)則從第1根針移動到第3根針?biāo)枰淖钌俨僮鞑綌?shù)為An,則根據(jù)漢諾塔問題的遞歸性和對稱性,數(shù)列An滿足:A1=1,而當(dāng)n>=2時(shí)有An=2An_1+1 由An=2A

7、n_1+1可得:An+1=2(An_1+1 這說明數(shù)列(An+1是以2為公比而以A1+1即2為首項(xiàng)的等比例數(shù),所以:An+1=2*2n-1(n>=1 即: An=2n-1(n>=1所以,解決n個(gè)盤子的漢諾塔問題至少需要2n-1步操作。2.每步的操作對象問題根據(jù)漢諾塔問題的對稱性和遞歸性,在n個(gè)盤子的漢諾塔問題所需要的2n-1步操作中,處于中心位置的那一步的操作對象是N號盤,前一半操作和后一半操作的操作對象關(guān)于中心位置對稱,因此只要確定出前一半操作的操作對象,那么后一半操作的操作對象也就隨之確定了,而前一半操作又是解決前n-1個(gè)盤子的漢諾塔問題的,因此處于這一半的中心位置的那一步的操

8、作對象就應(yīng)該是N-1號盤,如此繼續(xù)下去,每一步的操作對象都可以確定下來,下面給出n=1,2,3,4,5時(shí),每一步的操作對象:1個(gè)盤:12個(gè)盤:1 2 13個(gè)盤:1 2 1 3 1 2 14個(gè)盤:1 2 1 3 1 2 1 4 1 2 1 3 1 2 15個(gè)盤:1 2 1 3 1 2 1 4 1 2 1 3 1 2 151 2 1 3 1 2 1 4 1 2 1 3 1 2 13.每步的起點(diǎn)和終點(diǎn)問題根據(jù)漢諾塔問題的對稱性和遞歸性,在n個(gè)盤子的漢諾塔問題所需要的2n-1步操作中,處于中心位置的那一步的操作對象N號盤,起點(diǎn)是針A,終點(diǎn)是針C;前一半操作是將前n-1個(gè)盤子從針A移到針B的。因此,處于

9、這一半的中心位置的那一步的操作對象是N-1號盤,起點(diǎn)是針A,終點(diǎn)是針B;后一半操作是將前n-1個(gè)盤子從針B移到針C的。因此,處于這一半的中心位置的那一步的操作對象是N-1號盤,起點(diǎn)是針B,終點(diǎn)是針C,按照這種方式,從中心位置開始,逐漸向兩端擴(kuò)展,最終能夠確定所有操作步的起點(diǎn)和終點(diǎn)。至此,前面提出的3個(gè)問題都得到了解決,可直接按照上述思想來設(shè)計(jì)漢諾塔問題的非遞歸算法卻不是一件很容易的事情,且算法的效率也不太理想。三.漢諾塔問題的幾個(gè)基本理論任何遞歸問題都可以很容易地通過函數(shù)的遞歸調(diào)用來求解,但其效率卻比較底下,比較而言,遞歸問題的的、非遞歸解法實(shí)現(xiàn)起來要困難一些,但其執(zhí)行效率卻比較高。那么,有沒

10、有既容易實(shí)現(xiàn)而且效率又較高的非遞歸解法呢?答案是肯定的,那就是遞推!事實(shí)上,根據(jù)前面所述的分析,我們可以得到以下幾個(gè)結(jié)論:(1解決n個(gè)盤子的漢諾塔問題所需要的最少操作步數(shù)為2n-1;(2在解決n個(gè)盤子的漢諾塔問題所需要的2n-1步操作中,處于中心位置的第2n-1步的操作對象是N號盤,且操作的起點(diǎn)是針A,終點(diǎn)是針C;(3在解決n個(gè)盤子的漢諾塔問題所需要的2n-1步操作中,除了中心點(diǎn)之外的前一半操作可以由解決n-1個(gè)盤子的漢諾塔問題所需要的2n-1-1步操作得到:將解決n-1個(gè)盤子的漢諾塔問題所需要的2n-1-1步操作中的B換成C,C換成B,而A保持不變。(4在解決n個(gè)盤子的漢諾塔問題所需要的2n

11、-1步操作中,除了中心點(diǎn)之外的后一半操作可以由前一半操作得到,將前一半操作中的A換成B,B換成C,C換成A.至此,漢諾塔問題的遞歸算法就產(chǎn)生了,其實(shí),遞歸遞推只是同一類問題的兩種不同求解策略而已。因此,任何遞歸問題都可以采用遞推方法求解,只不過難易程度有別而已。四.遞推算法下面用C語言給出利用上述4點(diǎn)結(jié)論的非遞歸解法的計(jì)算機(jī)算法遞推算法。重要數(shù)據(jù)結(jié)構(gòu):S2n行3列的二維數(shù)組,存放所有的操作步。其中,第i行(i=1,2,3,.表示第i步,而且Si1表示操作的起點(diǎn),Si2表示操作的終點(diǎn),算法如下:for(K=1;K<=N;K+for(X=1,M=1,M<=K-1,M+X=X*2;SX0

12、=K;SX1=A;SX2=C;for(L=1;L<=X-1;L+if (SL1=BSL1=C;else if (SL1=CSL1=Bif(SL2=BSL2=C;else if(SL2=CSL2=B;for(L=X+1;L<=2*X-1;L+SL0=SL-X0;if(SL-X1=A (SL-X1=B;else if(SL-X1=B (SL1=C;else SL1=A;if(SL-X2=A SL2=B;else if(SL-X2=B SL2=C;else SL2=A;實(shí)際上,為解決n個(gè)盤子的漢諾塔問題,數(shù)組S只需要2n-1行即可;先求出n-1個(gè)盤子的漢諾塔問題的解,然后根據(jù)S的內(nèi)容輸出n個(gè)盤子的漢諾塔問題的解,這樣,空間開銷句降低了一半,時(shí)間開銷也有所改善。五.結(jié)語目前,已經(jīng)見諸文章的解決漢諾塔問題的非遞歸算法為數(shù)不多而且多數(shù)都是利用二叉樹甚至是三叉樹做為邏輯數(shù)據(jù)結(jié)構(gòu)并通過樹的構(gòu)造和遍歷來實(shí)現(xiàn)的.這類算法雖然思想基礎(chǔ)較簡單