1、你知道河內塔怎麼來的嗎？1883年，一位法國的數學家在一份雜誌上介紹了一個相當吸引人的難題，這個遊戲名為河內塔，它來自古印度神廟中的一段故事(也有人說是這個教授為增加遊戲的神秘色彩而捏造的)。關於河內塔的故事在古老的印度有一座神廟，據說它是宇宙的中心。在廟中放了一塊上面插有三根長木釘的木板，在其中的一根木釘，從上至下被放置了64片直徑由小至大的圓環形金屬片。古印度教的天神指示祂的僧侶們將64片金屬片移至另一根木釘。河內塔的規定在每次的移動中，只能搬移一片金屬片，並且在過程中必須保持金屬片由上至下是直徑由小至大的次序，使直徑較小的被放在上層。直到有一天，僧侶們能將64片金屬片依規則從指定的木釘上
2、全部移動至另一根木釘上，那麼，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界。ABC111讓我們來搬搬看請問要把柱上的盤子搬到柱上，最少需要幾次呢？實際最少次數1層河內塔時，直接把盤子從搬到，次數為1次。ABC11記得要符合一次搬一個，上面盤子要先搬的原則，請把柱上的盤子都搬至柱，最少需要幾次呢？ABC22 112 12 12 1多了一層有什麼差別？二層河內塔（n=2）時(1)移動盤子1從木樁A到木樁B。(2)移動盤子2從木樁A到木樁C。(3)移動盤子1從木樁B到木樁C。最少次數規律推導至少共次(同理AB亦為3次)ABC21121ABC333 2 1213 2 13 2 13 2
3、 13 2 13 2 12 11三層河內塔搬移請你來搬搬看，把柱上的盤子都搬至柱，並計算搬動的次數三層最少次數推導三層河內塔（n=3）時(1)1：AC(2)2：AB(3)1：CB(4)3：AC(5)1：BA(6)2：BC(7)1：AC 至少共次ABC322113 1211河內塔最少次數規律推導二層、三層河內塔比較1+2:AB共3次3:AC共1次1+2:BC共3次至少共次ABC33212121河內塔最少次數規律推導三層、四層河內塔比較1+2+3:AB共7次4:AC共1次1+2+3:BC共7次至少共次ABC44321321321河內塔次數規律推導總次數規律推導一般式1層河內塔次2-121-12層河
4、內塔次4-122-13層河內塔次8-123-14層河內塔次16-124-1k層河內塔2k-12484 3 2ABC4 3 2 1河內塔搬動方式推導 先試試四層的河內塔，觀察其規律4 3 2 14 3 2 14 3 2 14 3 2 14 3 2 14 3 2 14 3 2 144 34 3 2 13 2 12 1甲：甲：乙：乙：1432123443212344321234河內塔搬動方式推導由上述的規律得知，欲完成k+1層河內塔，需將前k層自A移至B，再將第k+1層自A移至C，再將前k層自B移至C。ABCk+1k+1k1k1k1河內塔搬動方式推導 以n=5為例ABC54321河內塔搬動方式推導
5、以n=5為例 第5個要搬至C，先將1-4個搬至B；ABC5432143215河內塔搬動方式推導 以n=5為例 第5個要搬至C，先將1-4個搬至B；第4個要搬至B，先將1-3個搬至C；5ABC45321321河內塔搬動方式推導 以n=5為例 第5個要搬至C，先將1-4個搬至B；第4個要搬至B，先將1-3個搬至C；第3個要搬至C，先將1-2個搬至B；ABC453212121河內塔搬動方式推導 以n=5為例 第5個要搬至C，先將1-4個搬至B；第4個要搬至B，先將1-3個搬至C；第3個要搬至C，先將1-2個搬至B；第2個要搬至B，先將第1個搬至C。由圖可知當要移動個數為奇數，編號奇數的盤子移動至目標
6、柱，編號偶數的盤子移動至中繼柱。ABC453211河內塔搬動方式推導 若固定由A開始搬起 欲完成n=k於C，需先完成n=k-1於B；欲完成n=k-1於B，需先完成n=k-2於C；故當k為奇數時，一開始必須搬1由A到C；而當k為偶數時，一開始必須搬1由A到B。ABCkk-1k-21k-1k-21kk-2111河內塔搬動方式推導 我們將圖形依序操作並統計次數：將第1個搬至C，再將第2個搬至B；將1-2個搬至B，再將第3個搬至C；將1-3個搬至C，再將第4個搬至B；將1-4個搬至B，再將第5個搬至C；最後再將1-4個搬至C五層河內塔次數統計次次次次次（層）次次（層）次次（層）共次(=)ABC5432
7、1121321432154321河內塔搬動方式一般化 k為奇數時，將1搬至C，2搬至B；1+2搬至B，3搬至C；1+2+3搬至C，4搬至B；1+2+k-1搬至B，k搬至C；1+2+k搬至C 奇數盤移至目標柱C，偶數盤移至中繼柱B 而k為偶數時則將奇數時的C、B互換即可。(中繼柱)(目標柱)k32k-111k-1k 3 121231232k-11河內塔結論歸納透過以上次數及方法的推導，我們可以得知這64個金盤若要全數搬至C柱，至少需要移動264-1次才會完成。而若每移動一次以1秒鐘計算，還要經過184467440737095551615天，大約是5850億年才能完成，透過現在普遍的電腦，每秒搬動
8、一百萬次的話，則尚需58.5萬年，故由此看來地球還算蠻安全的吧！河內塔推廣若現在的盤子由小至大非規則排列，則需分次移動並統計次數。ABC533323335881共次資料來源：九章出版社：河內塔 http:/.tw/toy/hanoi/hanoi.html高中電腦學習加油站：河內塔問題http:/content.edu.tw/senior/computer/ks_ks/book/algodata/algorithm/algo44.htm昌爸工作坊http:/www.mathland.idv.tw/清大數學子網頁 http:/steiner.math.nthu.edu.tw/ne01/jyt/game/Hanoi/Hanoi.htm北興國中科展園地 http:/www.psjh.cy.edu.tw/science/studauthor/91/river.htm
