河內(nèi)塔問(wèn)題國(guó)中版1682KB課件

1、你知道河內(nèi)塔怎麼來(lái)的嗎？ 1883年，一位法國(guó)的數(shù)學(xué)家在一份雜誌上介紹了一個(gè)相當(dāng)吸引人的難題，這個(gè)遊戲名為河內(nèi)塔，它來(lái)自古印度神廟中的一段故事(也有人說(shuō)是這個(gè)教授為增加遊戲的神秘色彩而捏造的)。 關(guān)於河內(nèi)塔的故事在古老的印度有一座神廟，據(jù)說(shuō)它是宇宙的中心。在廟中放了一塊上面插有三根長(zhǎng)木釘?shù)哪景?，在其中的一根木釘，從上至下被放置?4片直徑由小至大的圓環(huán)形金屬片。古印度教的天神指示祂的僧侶們將64片金屬片移至另一根木釘。河內(nèi)塔的規(guī)定在每次的移動(dòng)中，只能搬移一片金屬片，並且在過(guò)程中必須保持金屬片由上至下是直徑由小至大的次序，使直徑較小的被放在上層。直到有一天，僧侶們能將64片金屬片依規(guī)則從指定的木

2、釘上全部移動(dòng)至另一根木釘上，那麼，世界末日即隨之來(lái)到，世間的一切終將被毀滅，萬(wàn)物都將至極樂(lè)世界。ABC111讓我們來(lái)搬搬看請(qǐng)問(wèn)要把柱上的盤(pán)子搬到柱上，最少需要幾次呢？實(shí)際最少次數(shù)1層河內(nèi)塔時(shí)，直接把盤(pán)子從搬到，次數(shù)為1次。ABC11記得要符合一次搬一個(gè)，上面盤(pán)子要先搬的原則，請(qǐng)把柱上的盤(pán)子都搬至柱，最少需要幾次呢？ABC2211212121多了一層有什麼差別？二層河內(nèi)塔（n=2）時(shí)(1)移動(dòng)盤(pán)子1從木樁A到木樁B。(2)移動(dòng)盤(pán)子2從木樁A到木樁C。(3)移動(dòng)盤(pán)子1從木樁B到木樁C。 最少次數(shù)規(guī)律推導(dǎo)至少共次(同理AB亦為3次)ABC21121ABC33321213213213213213212

3、11三層河內(nèi)塔搬移請(qǐng)你來(lái)搬搬看，把柱上的盤(pán)子都搬至柱，並計(jì)算搬動(dòng)的次數(shù)三層最少次數(shù)推導(dǎo)三層河內(nèi)塔（n=3）時(shí)(1) 1：AC(2) 2：AB(3) 1：CB(4) 3：AC(5) 1：BA(6) 2：BC(7) 1：AC 至少共次ABC3221131211河內(nèi)塔最少次數(shù)規(guī)律推導(dǎo)二層、三層河內(nèi)塔比較1+2:AB共3次3:AC共1次1+2:BC共3次至少共次ABC33212121河內(nèi)塔最少次數(shù)規(guī)律推導(dǎo)三層、四層河內(nèi)塔比較1+2+3:AB共7次4:AC共1次1+2+3:BC共7次至少共次ABC44321321321河內(nèi)塔次數(shù)規(guī)律推導(dǎo)總次數(shù)規(guī)律推導(dǎo)一般式1層河內(nèi)塔次2-121-12層河內(nèi)塔次4-122

4、-13層河內(nèi)塔次8-123-14層河內(nèi)塔次16-124-1k層河內(nèi)塔2k-1248432ABC4321河內(nèi)塔搬動(dòng)方式推導(dǎo)先試試四層的河內(nèi)塔，觀察其規(guī)律4321432143214321432143214321443432132121甲：乙：1432123443212344321234河內(nèi)塔搬動(dòng)方式推導(dǎo)由上述的規(guī)律得知，欲完成k+1層河內(nèi)塔，需將前k層自A移至B，再將第k+1層自A移至C，再將前k層自B移至C。ABCk+1k+1k1k1k1河內(nèi)塔搬動(dòng)方式推導(dǎo)以n=5為例ABC54321河內(nèi)塔搬動(dòng)方式推導(dǎo)以n=5為例第5個(gè)要搬至C，先將1-4個(gè)搬至B；ABC5432143215河內(nèi)塔搬動(dòng)方式推導(dǎo)以n

5、=5為例第5個(gè)要搬至C，先將1-4個(gè)搬至B；第4個(gè)要搬至B，先將1-3個(gè)搬至C；5ABC45321321河內(nèi)塔搬動(dòng)方式推導(dǎo)以n=5為例第5個(gè)要搬至C，先將1-4個(gè)搬至B；第4個(gè)要搬至B，先將1-3個(gè)搬至C；第3個(gè)要搬至C，先將1-2個(gè)搬至B；ABC453212121河內(nèi)塔搬動(dòng)方式推導(dǎo)以n=5為例第5個(gè)要搬至C，先將1-4個(gè)搬至B；第4個(gè)要搬至B，先將1-3個(gè)搬至C；第3個(gè)要搬至C，先將1-2個(gè)搬至B；第2個(gè)要搬至B，先將第1個(gè)搬至C。由圖可知當(dāng)要移動(dòng)個(gè)數(shù)為奇數(shù)，編號(hào)奇數(shù)的盤(pán)子移動(dòng)至目標(biāo)柱，編號(hào)偶數(shù)的盤(pán)子移動(dòng)至中繼柱。ABC453211河內(nèi)塔搬動(dòng)方式推導(dǎo)若固定由A開(kāi)始搬起欲完成n=k於C，需先完

6、成n=k-1於B；欲完成n=k-1於B，需先完成n=k-2於C；故當(dāng)k為奇數(shù)時(shí)，一開(kāi)始必須搬1由A到C；而當(dāng)k為偶數(shù)時(shí)，一開(kāi)始必須搬1由A到B。ABCkk-1k-21k-1k-21kk-2111河內(nèi)塔搬動(dòng)方式推導(dǎo)我們將圖形依序操作並統(tǒng)計(jì)次數(shù)：將第1個(gè)搬至C，再將第2個(gè)搬至B；將1-2個(gè)搬至B，再將第3個(gè)搬至C；將1-3個(gè)搬至C，再將第4個(gè)搬至B；將1-4個(gè)搬至B，再將第5個(gè)搬至C；最後再將1-4個(gè)搬至C五層河內(nèi)塔次數(shù)統(tǒng)計(jì)次次次次次（層）次次（層）次次（層）共次(=)ABC54321121321432154321河內(nèi)塔搬動(dòng)方式一般化k為奇數(shù)時(shí)，將1搬至C，2搬至B；1+2搬至B，3搬至C；1+2

7、+3搬至C，4搬至B；1+2+k-1搬至B，k搬至C；1+2+k搬至C奇數(shù)盤(pán)移至目標(biāo)柱C，偶數(shù)盤(pán)移至中繼柱B而k為偶數(shù)時(shí)則將奇數(shù)時(shí)的C、B互換即可。(中繼柱)(目標(biāo)柱)k32k-111k-1k3121231232k-11河內(nèi)塔結(jié)論歸納透過(guò)以上次數(shù)及方法的推導(dǎo)，我們可以得知這64個(gè)金盤(pán)若要全數(shù)搬至C柱，至少需要移動(dòng)264-1次才會(huì)完成。而若每移動(dòng)一次以1秒鐘計(jì)算，還要經(jīng)過(guò)184467440737095551615天，大約是5850億年才能完成，透過(guò)現(xiàn)在普遍的電腦，每秒搬動(dòng)一百萬(wàn)次的話，則尚需58.5萬(wàn)年，故由此看來(lái)地球還算蠻安全的吧！河內(nèi)塔推廣若現(xiàn)在的盤(pán)子由小至大非規(guī)則排列，則需分次移動(dòng)並統(tǒng)計(jì)次數(shù)。ABC533323335881共次資料來(lái)源：九章出版社：河內(nèi)塔.tw/toy/hanoi/hanoi.html高中電腦學(xué)習(xí)加油站：河內(nèi)塔問(wèn)題.tw/senior/computer/ks_ks/book/algodata/algorithm/algo44.