(有趣的漢諾塔問(wèn)題)一塊黃銅平板上裝著三根金剛石細(xì)柱,其中一根細(xì)柱上套著64個(gè)大小不等的環(huán)形金盤(pán),大的在下,小的在上,如圖所示.這些盤(pán)子可每次一個(gè)地從一根柱子轉(zhuǎn)移到另一根柱子,但不允許較大盤(pán)子放在較小的盤(pán)子的上面,若把這64個(gè)金盤(pán)從一根柱子全部移到另一根柱子上,至少須移動(dòng)多少次?

答案:
解析:

  用an表示將n個(gè)盤(pán)子從一根柱子移到另一根柱子上至少須移動(dòng)的次數(shù).顯然a0=0,a1=1,a2=3.

  對(duì)于n個(gè)盤(pán)子,可看成先把柱子A的n-1個(gè)盤(pán)子看成一個(gè)整體,套到柱子C上,此時(shí).需要a次,再把A中底下的大盤(pán)移到B柱,然后再把C中的n-1個(gè)盤(pán)子移到B柱,此時(shí)需要1+a次.所以有an=2a+1.

  由數(shù)列知識(shí)可得an=2n-1.

  回到原問(wèn)題上來(lái),則至少移動(dòng)264-1次.如果是一個(gè)人用手工移動(dòng),幾輩子也不可能完成這個(gè)任務(wù),也就大可不必?fù)?dān)心世界末日的來(lái)臨.


練習(xí)冊(cè)系列答案
相關(guān)習(xí)題

同步練習(xí)冊(cè)答案