漢諾塔問(wèn)題的非遞歸新解法

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

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

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

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