河内塔问题国中版1682KB课件

你知道河內塔怎麼來的嗎？1883年，一位法國的數學家在一份雜誌上介紹了一個相當吸引人的難題，這個遊戲名為「河內塔」，它來自古印度神廟中的一段故事(也有人說是這個教授為增加遊戲的神秘色彩而捏造的)。你知道河內塔怎麼來的嗎？1883年，一位法國的數學家在一份關於河內塔的故事……在古老的印度有一座神廟，據說它是宇宙的中心。在廟中放了一塊上面插有三根長木釘的木板，在其中的一根木釘，從上至下被放置了64片直徑由小至大的圓環形金屬片。古印度教的天神指示祂的僧侶們將64片金屬片移至另一根木釘。關於河內塔的故事……在古老的印度有一座神廟，據說它是宇宙的中河內塔的規定……在每次的移動中，只能搬移一片金屬片，並且在過程中必須保持金屬片由上至下是直徑由小至大的次序，使直徑較小的被放在上層。直到有一天，僧侶們能將64片金屬片依規則從指定的木釘上全部移動至另一根木釘上，那麼，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界。河內塔的規定……在每次的移動中，只能搬移一片金屬片，並且在過ABC111讓我們來搬搬看……請問要把Ａ柱上的盤子１搬到Ｃ柱上，最少需要幾次呢？ABC111讓我們來搬搬看……請問要把Ａ柱上的盤子１搬到Ｃ柱實際最少次數……1層河內塔時，直接把盤子從Ａ搬到Ｃ，次數為1次。ABC11實際最少次數……1層河內塔時，直接把盤子從Ａ搬到Ｃ，次數為1記得要符合一次搬一個，上面盤子要先搬的原則，請把Ａ柱上的盤子都搬至Ｃ柱，最少需要幾次呢？ABC2211212121多了一層有什麼差別？記得要符合一次搬一個，上面盤子要先搬的原則，請把Ａ柱上的盤子二層河內塔（n=2）時……(1)移動盤子1從木樁A到木樁B。

(2)移動盤子2從木樁A到木樁C。

(3)移動盤子1從木樁B到木樁C。最少次數規律推導……至少共３次(同理AB亦為3次)ABC21121二層河內塔（n=2）時……最少次數規律推導……至少共３次(同ABC3332121321321321321321211三層河內塔搬移……請你來搬搬看，把Ａ柱上的盤子都搬至Ｃ柱，並計算搬動的次數……ABC3332121321321321321321211三層三層最少次數推導……三層河內塔（n=3）時……(1)1：AC

(2)2：AB

(3)1：CB

(4)3：AC

(5)1：BA

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

(2)移動盤子2從木樁A到木樁C。

(3)移動盤子1從木樁B到木樁C。最少次數規律推導……至少共３次(同理AB亦為3次)ABC21121二層河內塔（n=2）時……最少次數規律推導……至少共３次(同ABC3332121321321321321321211三層河內塔搬移……請你來搬搬看，把Ａ柱上的盤子都搬至Ｃ柱，並計算搬動的次數……ABC3332121321321321321321211三層三層最少次數推導……三層河內塔（n=3）時……(1)1：AC

(2)2：AB

(3)1：CB

(4)3：AC

(5)1：BA

(6)2：BC(7)1：AC至少共７次ABC3221131211三層最少次數推導……三層河內塔（n=3）時……至少共７次AB河內塔最少次數規律推導……二層、三層河內塔比較……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河內塔最少次數規律推導……三層、四層河內塔比較……至少共１５河內塔次數規律推導……248河內塔次數規律推導……248432ABC4321河內塔搬動方式推導……先試試四層的河內塔，觀察其規律……4321432143214321432143214321443432132121甲：乙：1432ABC4321河內塔搬動方式推導……先試試四層的河內塔河內塔搬動方式推導……由上述的規律得知，欲完成k+1層河內塔，需將前k層自A移至B，再將第k+1層自A移至C，再將前k層自B移至C。ABCk+1k+1k……1k……1k……1河內塔搬動方式推導……由上述的規律得知，欲完成k+1層河內塔河內塔搬動方式推導……以n=5為例……ABC54321河內塔搬動方式推導……以n=5為例……ABC54321河內塔搬動方式推導……以n=5為例……第5個要搬至C，先將1-4個搬至B；ABC5432143215河內塔搬動方式推導……以n=5為例……ABC54321432河內塔搬動方式推導……以n=5為例……第5個要搬至C，先將1-4個搬至B；第4個要搬至B，先將1-3個搬至C；5ABC45321321河內塔搬動方式推導……以n=5為例……5ABC4532132河內塔搬動方式推導……以n=5為例……第5個要搬至C，先將1-4個搬至B；第4個要搬至B，先將1-3個搬至C；第3個要搬至C，先將1-2個搬至B；ABC453212121河內塔搬動方式推導……以n=5為例……ABC45321212河內塔搬動方式推導……以n=5為例……第5個要搬至C，先將1-4個搬至B；第4個要搬至B，先將1-3個搬至C；第3個要搬至C，先將1-2個搬至B；第2個要搬至B，先將第1個搬至C。由圖可知當要移動個數為奇數，編號奇數的盤子移動至目標柱，編號偶數的盤子移動至中繼柱。ABC453211河內塔搬動方式推導……以n=5為例……由圖可知當要移動個數為河內塔搬動方式推導……若固定由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-2……1k-1k-2……1kk-2……1……11河內塔搬動方式推導……若固定由A開始搬起……ABCkk-1k河內塔搬動方式推導……我們將圖形依序操作並統計次數：將第1個搬至C，再將第2個搬至B；將1-2個搬至B，再將第3個搬至C；將1-3個搬至C，再將第4個搬至B；將1-4個搬至B，再將第5個搬至C；最後再將1-4個搬至CABC54321121321432154321河內塔搬動方式推導……我們將圖形依序操作並統計次數：ABC5河內塔搬動方式一般化k為奇數時，將1搬至C，2搬至B；

1+2搬至B，3搬至C；

1+2+3搬至C，4搬