河內(nèi)塔問題

1、河內(nèi)塔問題河內(nèi)塔問題智力游戲智力游戲數(shù)學(xué)書上有一道河內(nèi)塔的問題，這是一個流傳很廣的游戲：1.有三根桿子A、B、C。A桿上有三個碟子。2.每次移動一個碟子，大碟子不能移在小碟子上面。3.把A桿上的三個碟子移到C桿上需要多少步？如果A桿上有四個、五個碟子各需要多少步？河內(nèi)塔問題的由來河內(nèi)塔問題的由來1883年，一位法國的數(shù)學(xué)家EdouardLucas教授在歐洲的一份雜志上介紹了一個相當(dāng)吸引人的難題──迷人的智力游戲。這個游戲名為河內(nèi)塔(To

2、werofHanoi)，它源自古印度神廟中的一段故事(也有人說是Lucas教授為增加此游戲之神秘色彩而捏造的)。傳說在古老的印度，有一座神廟，據(jù)說它是宇宙的中心。在廟宇中放置了一塊上面插有三根長木釘?shù)哪景澹谄渲械囊桓踞斏?，從上至下被放置?4片直徑由小至大的圓環(huán)形金屬片。古印度教的天神指示他的僧侶們將64片的金屬片移至三根木釘中的其中一根上。規(guī)定在每次的移動中，只能搬移一片金屬片，并且在過程中必須保持金屬片由上至下是直徑由小至大的次

3、序，也就是說不論在那一根木釘上，圓環(huán)形的金屬片都是直徑較小的被放在上層。直到有一天，僧侶們能將64片的金屬片依規(guī)則從指定的木釘上全部移動至另一根木釘上，那么，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界。我們先測算一下按上述規(guī)則移完這64片金屬盤所要花費的時間吧！要按上述規(guī)則移動這64片金屬片至少要幾次的搬移才能完成呢？設(shè)an表示當(dāng)金屬盤總共有n片時至少所需搬動的次數(shù)，則a1=1….….….恰好是211a2=3….….…

4、.恰好是221a3=7….….….恰好是231a4=15……….恰好是241a5=31……….恰好是251a6=63……….恰好是261于是我們得到一個遞歸的公式遞歸的公式：an=2n1，假如這位僧侶每秒搬移一次金屬盤的話，那么64片金屬盤至少需要經(jīng)過2641=18446744073709551615秒的搬移才能完成。按照這樣的規(guī)律即使他日以繼夜的不停地搬移金屬盤，也需要也需要584942417355584942417355年之久才可移

5、動完成年之久才可移動完成。即對這64個盤子的搬移大約需要1.84x10191.84x1019次的搬移，在每秒可搬移一次的情況下，大概需要58505850億年億年才可搬移完成！可能那時便到世界之末日了。這就是1883年法國的數(shù)學(xué)家EdouardLucas提出的河內(nèi)塔問題(TowerofHanoi)。也是一個非常(13)移動盤子l從木樁A到木樁B。(14)移動盤子2從木樁A到木樁C。(15)移動盤子1從木樁B到木樁C。因此，總共需移動241

6、=15次，次序為121312141213121。當(dāng)任意n個盤子需搬移時，我們可以歸納出一套規(guī)則。1.先將l~nl號盤子從(from)A經(jīng)由(by)B搬至(to)C。2.n:A→B(將n號盤子由A搬至B)。3.再將l~nl號盤子從C經(jīng)由A搬至B。我們把搬n個盤子的動作分解成三大步，第一和第三大步都是搬nl個盤子，第二大步則是搬1個盤子。至于搬n個盤子共需幾次搬動呢我們假設(shè)An為搬n個盤子所需搬動次數(shù)，An1則是搬nl個盤子所需搬動次數(shù)。終