握住科學鑰匙 打開科學之門

首頁 > 正文

手机最快报码开奖结果: 漢諾塔游戲:遞歸經典問題

2019-08-10 07:08  來源: 新華網

大乐透19048开奖号码 www.zbrxk.com 漢諾塔游戲,是非常著名的智力趣味題,在很多算法書籍和智力競賽中都有涉及。

漢諾塔游戲的基本規則是:在一塊板子上,有三根編號分別為A、B、C的桿,在A桿上按自下而上、由大到小的順序放置著64個(或其他數目)圓盤,每次只能移動一個圓盤,并且在移動過程中三根桿上都始終保持大盤在下、小盤在上的狀態,操作過程中圓盤可以在A、B、C任意一桿上,要如何把A桿上的圓盤全部移到C桿上?

以3個圓盤為例:將3個圓盤按由小到大的順序分別記作P1、P2、P3。按照規則將三個圓盤從A桿移至C桿,則需以下步驟:(1)先將P1移至C桿,再將P2移至B桿,然后將P1移至B桿,此時P1和P2均在B桿上(需3步);(2)將P3移至C桿(需1步);(3)將P1移至A桿,將P2移至C桿,最后將P1移至C桿(需3步)。

在此過程中,要將P3移至C桿,先將C桿當作中介,將P1移至C桿;再將P1、P2先移至B桿,借用B桿做中介;再將P2移至C桿時,又先將P1移至A桿,借用了A桿做中介。(總共7步完成)

以此為例,如何完成其他數量圓盤的移動操作呢?

當n=1時,只需將編號為1的圓盤從A柱直接移至C柱上即可。

當n=2時,利用B柱作為輔助柱,先將圓盤1移至B柱,再將圓盤2由A柱直接移至C柱,然后再將圓盤1由B柱移至C柱。

當n=3時,同樣利用B柱作為輔助柱,依照上述原則,先設法將圓盤1、2移至B柱,待圓盤3由A柱移至C柱后,再依照上述原則設法將圓盤1、2移至C柱。

......

依此類推,當n>1時,需利用B柱作為輔助柱,先設法將壓在編號為n的圓盤上的n-1個圓盤從A柱(依照上述原則)移至C柱,待編號為n的圓盤從A柱移至C柱后,再將B柱上的n-1個圓盤(依照上述原則)移至C柱。

游戲的移動操作很簡單,但是如何將64個圓盤從一根桿子上移到另一根桿子上,并且始終保持上小下大的順序,一共需要移動多少次才是讓人頭疼的問題。游戲過程中不難發現:不管把哪一個圓盤移到另一根桿子上,移動的次數都要比移動上面一個增加一倍。這樣,移動第1個只需1次,第2個需2次,第3個需4次……第64個需263次。

奇妙的漢諾塔游戲所含有的數學知識飽含著人類的智慧。

本作品為“科普中國-科學原理一點通”原創,轉載時務請注明出處。

?

作者: 鄭玉婷   [責任編輯: 童植]