新漢諾塔課程設(shè)計(jì)(編輯修改稿)
2025-02-12 07:36 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 2的2次方減1 3個(gè)圓盤(pán)的時(shí)候 2的3次方減1 4個(gè)圓盤(pán)的時(shí)候 2的4次方減1 5個(gè)圓盤(pán)的時(shí)候 2的5次方減1 ........n個(gè)圓盤(pán)的時(shí)候 2的n次方減1假設(shè)有n片，移動(dòng)次數(shù)是f(n).顯然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不難證明f(n)=2^n1。n=64時(shí)， f(64)= 2^641=18446744073709551615 假如每秒鐘一次，共需多長(zhǎng)時(shí)間呢？一個(gè)平年365天有 31536000 秒，閏年366天有31622400秒，平均每年31556952秒，計(jì)算一下， 18446744073709551615/31556952=，這表明移完這些金片需要5845億年以上，而地球存在至今不過(guò)45億年，太陽(yáng)系的預(yù)期壽命據(jù)說(shuō)也就是數(shù)百億年。真的過(guò)了5845億年，不說(shuō)太陽(yáng)系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經(jīng)灰飛煙滅?！ ∫簿褪钦f(shuō)，n=64的時(shí)候是（2的64次方減1）次。因此，如果移動(dòng)一個(gè)圓盤(pán)需要1秒的話，宇宙的壽命=2的64次方減1（秒）用一年=60秒x60分x24小時(shí)x365天來(lái)算的話，大約有5800億年吧。據(jù)說(shuō)，現(xiàn)在的宇宙年齡大約是150億年，還差得遠(yuǎn)呢。言而總之，漢諾塔問(wèn)題在數(shù)學(xué)界有很高的研究?jī)r(jià)值，而且至今還在被一些數(shù)學(xué)家們所研究也是我們所喜歡玩的一種益智游戲，它可以幫助開(kāi)發(fā)智力，激發(fā)我們的思維。對(duì)漢諾塔還可以有進(jìn)一步的研究。4. 問(wèn)題分析：對(duì)于這樣一個(gè)問(wèn)題，任何人都不可能直接寫(xiě)出移動(dòng)盤(pán)子的每一步，但我們可以利用下面的方法來(lái)解決：設(shè)移動(dòng)盤(pán)子數(shù)為n，為了將這n個(gè)盤(pán)子從A桿移動(dòng)到C桿，可以做以下三步：（1）以C盤(pán)為中介，從A桿將1至n1號(hào)盤(pán)移至B桿；（2）將A桿中剩下的第n號(hào)盤(pán)移至C桿；（3）以A桿為中介，從B桿將1至n1號(hào)盤(pán)移至C桿；這樣，問(wèn)題解決了，但實(shí)際操作中，只有第二步可直接完成，而第一、三步又成為移動(dòng)的新問(wèn)題。以上操作的實(shí)質(zhì)是把移動(dòng)n個(gè)盤(pán)子的問(wèn)題轉(zhuǎn)化為移動(dòng)n1個(gè)盤(pán)。那一、三步如何解決？事實(shí)上，上述方法：設(shè)盤(pán)子數(shù)為n，n可為任意數(shù)，該法同樣適用于移動(dòng)n1個(gè)盤(pán)。因此，依據(jù)上法，可解決n1個(gè)盤(pán)子從A桿移到B桿（第一步）或從B桿移到C桿（第三步）問(wèn)題?，F(xiàn)在，問(wèn)題由移動(dòng)n個(gè)盤(pán)子的操作轉(zhuǎn)化為移動(dòng)n2個(gè)盤(pán)子的操作。依據(jù)該原理，層層遞推，即可將原問(wèn)題轉(zhuǎn)化為解決移動(dòng)nn3……2直到移動(dòng)1個(gè)盤(pán)的操作，而移動(dòng)一個(gè)盤(pán)的操作是可以直接完成的。至此，我們的任務(wù)算作是真正完成了。而這種由繁化簡(jiǎn)，用簡(jiǎn)單的問(wèn)題和已知的操作運(yùn)算來(lái)解決復(fù)雜問(wèn)題的方法，就是遞歸法。在計(jì)算機(jī)設(shè)計(jì)語(yǔ)言中，用遞歸法編寫(xiě)的程序就是遞歸程序。5. 概要設(shè)計(jì)如果盤(pán)子為1，則將這個(gè)盤(pán)子從塔座A移動(dòng)到塔座C；如果不為1，則采用遞歸思想。將塔座A的前n1個(gè)盤(pán)子借助C盤(pán)（即目的盤(pán)）移到塔座B，移后，此時(shí)C為空座，那我們就可以將塔座A的第n個(gè)盤(pán)子移到塔座C了。接下來(lái)就將塔座B的n1個(gè)盤(pán)子借助A移到塔座C，從而完成盤(pán)子的移動(dòng)。 實(shí)現(xiàn)方法通過(guò)數(shù)學(xué)函數(shù)的遞歸方法調(diào)用來(lái)實(shí)現(xiàn)。 主要模塊Main函數(shù)實(shí)現(xiàn)函數(shù)的調(diào)用，move函數(shù)實(shí)現(xiàn)輸出，hanoi函數(shù)調(diào)用move函數(shù)實(shí)現(xiàn)移動(dòng)和最終輸出。 模塊關(guān)系
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1