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

1、漢諾塔問題的非遞歸算法漢諾塔問題的非遞歸算法計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)學(xué)院計111班張春穎（組長）張春穎（組長）37號劉丹（組員）丹（組員）22號4.4.漢諾塔問題的輪換性漢諾塔問題的輪換性設(shè)S為將n個盤子按照給定的規(guī)則從針A移到針B所需的所有操作步的集合，按照形式不變性，如果將S中的A全部換成BB全部換成C，C全部換成A則得到的是將N個盤子按照同樣的規(guī)則從針B移到針C所需的所有操作步的集合。同樣，如果將S中的A全部換成C，C

2、全部換成A，B保持不變，則得到的是將n個盤子按照同樣的規(guī)則從針C移到針B所需的所有操作步的集合。5.5.遞歸算法如下遞歸算法如下Voidhanoi(intnxyz)上按將塔座x上按直徑由小到大且自上而下編號為1至nde個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。搬動操作move(xnz)可定義為（c是初值為0的全局變量，對搬動計數(shù)）；12if(n==1)3move(x1z)4else5hanoi(n1xzy)6move(xnz)7han

3、oi(n1yxz)89但是遞歸看似簡潔，但是遞歸算法解題的運行，效率較低，在遞歸調(diào)用的過程中系統(tǒng)為每層的返回點、局部量等開辟了棧來存儲遞歸次數(shù)過多容易造成棧溢出，漢諾塔問題會多次用到遞歸，所以會發(fā)生棧溢出2非遞歸解法的幾個基本問題非遞歸解法的幾個基本問題根據(jù)遞歸性，我們很容易寫出漢諾塔問題的遞歸解，關(guān)于這一點，很多高級語言的教科書都有涉及，下面我們專門來討論其非遞歸解問題。為了找到其非遞歸解，我們需要而且只需要解決下列3個問題：（1）至

4、少需要多少步操作？（2）每一步的操作對象是誰？（3）每一步操作的起點和終點又是誰1.1.操作步數(shù)問題操作步數(shù)問題設(shè)將n個盤子按照規(guī)則從第1根針移動到第3根針?biāo)枰淖钌俨僮鞑綌?shù)為An則根據(jù)漢諾塔問題的遞歸性和對稱性，數(shù)列An滿足：A1=1，而當(dāng)n=2時有An=2An_11由An=2An_11可得：An1=2(An_11)這說明數(shù)列（An1）是以2為公比而以A11即2為首項的等比例數(shù)，所以：An1=22^n1(n=1)即：An=2^n1(