Question

(有趣的漢諾塔問(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)多少次？

Answer 1

答案：
解析：

用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)臨．