發明河內塔 ---- 愛德華盧卡斯 ( EdouardLucas ) 的 ” 一生 ” 盧卡斯曾就讀於 法 國高等師 範學校 ， 他 曾在巴黎天文台 工作，後來在巴黎 成為數學教授， 他 也曾在 軍隊。 盧卡斯曾就讀於 法 國高等師 範學校 ， 他 曾在巴黎天文台 工作，後來在巴黎 成為數學教授，

Presentation on theme: "發明河內塔 ---- 愛德華盧卡斯 ( EdouardLucas ) 的 ” 一生 ” 盧卡斯曾就讀於 法 國高等師 範學校 ， 他 曾在巴黎天文台 工作，後來在巴黎 成為數學教授， 他 也曾在 軍隊。 盧卡斯曾就讀於 法 國高等師 範學校 ， 他 曾在巴黎天文台 工作，後來在巴黎 成為數學教授，"— Presentation transcript:

1

2 發明河內塔 ---- 愛德華盧卡斯 ( EdouardLucas ) 的 ” 一生 ” 盧卡斯曾就讀於 法 國高等師 範學校 ， 他 曾在巴黎天文台 工作，後來在巴黎 成為數學教授， 他 也曾在 軍隊。 盧卡斯曾就讀於 法 國高等師 範學校 ， 他 曾在巴黎天文台 工作，後來在巴黎 成為數學教授， 他 也曾在 軍隊。 http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm

3 意外的死亡 在年度代表大會的宴會 上， avancement 協會 ，當時被服務員掉下的 一些陶器和一塊鋼板切 割破盧卡斯的臉頰。 幾天後引起嚴重的皮膚 炎症 --- 敗血症。 在年度代表大會的宴會 上， avancement 協會 ，當時被服務員掉下的 一些陶器和一塊鋼板切 割破盧卡斯的臉頰。 幾天後引起嚴重的皮膚 炎症 --- 敗血症。 盧卡斯在 49 歲時就死 了。 盧卡斯在 49 歲時就死 了。 http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm

4 為何叫 --- 河內塔 ?? 盧卡斯從小就對數 學很有興趣，發明 了 河內塔 --- 是他根 據市場的綽號 “ 北路 克勞斯去暹羅 “ ，和 ” 盧卡斯德亞眠 ” 的字 謎 取的。 盧卡斯從小就對數 學很有興趣，發明 了 河內塔 --- 是他根 據市場的綽號 “ 北路 克勞斯去暹羅 “ ，和 ” 盧卡斯德亞眠 ” 的字 謎 取的。 http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm

5 河內塔之起源 河內之塔是法國人 M.Claus(Lucas) 於 1883 年從泰國 帶至法國的，河內為越戰時北越 的首都。 河內之塔是法國人 M.Claus(Lucas) 於 1883 年從泰國 帶至法國的，河內為越戰時北越 的首都。 http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm

6 法國數學家 Edouard Lucas 說 ，創世紀時 Benares 有一座波 羅教塔，由三支鑽石棒所支撐 ，神在第一根棒上放置 64 個 由上至下依由小至大排列的金 盤。 法國數學家 Edouard Lucas 說 ，創世紀時 Benares 有一座波 羅教塔，由三支鑽石棒所支撐 ，神在第一根棒上放置 64 個 由上至下依由小至大排列的金 盤。 http://zh.wikipedia.org/wiki/%E6%B1%89%E8%AF%BA%E5%A1%94

7 並命令僧侶將所有的金盤從第 一根石棒移至第三根石棒，且 搬運過程中遵守大盤子在小盤 子之下的原則，若每日僅搬一 個盤子，則當盤子全數搬運完 畢之時，而也就是世界末日來 臨之時。 並命令僧侶將所有的金盤從第 一根石棒移至第三根石棒，且 搬運過程中遵守大盤子在小盤 子之下的原則，若每日僅搬一 個盤子，則當盤子全數搬運完 畢之時，而也就是世界末日來 臨之時。 http://zh.wikipedia.org/wiki/%E6%B1%89%E8%AF%BA%E5%A1%94

8 河內塔 --- 解法 如果柱子標為 ABC ，要由 A 搬 至 C 。在只有一個盤子時，就 將它直接搬至 C ，當有兩個盤 子，就將 B 當作輔助柱。 如果柱子標為 ABC ，要由 A 搬 至 C 。在只有一個盤子時，就 將它直接搬至 C ，當有兩個盤 子，就將 B 當作輔助柱。 http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm

9 如果盤數超過 2 個，將第三個以下 的盤子遮起來，就很簡單了。 如果盤數超過 2 個，將第三個以下 的盤子遮起來，就很簡單了。 每次處理兩個盤子，也就是： A>B 、 A>C 、 B>C 三個步驟，被遮住的 部份，就是進入遞迴的處理。 每次處理兩個盤子，也就是： A>B 、 A>C 、 B>C 三個步驟，被遮住的 部份，就是進入遞迴的處理。 http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm

10 什麼是遞迴 ?? 1=1 1=1 1+2=3 1+2=3 1+2+2 =7 1+2+2 =7 1+2 +2 =15 1+2 +2 =15 1+2 +2 +2 =31 1+2 +2 +2 =31 1+2 +2 +2 …+2 = 1+2 +2 +2 …+2 = 2 2 3 2 3 4...... 234 n-1 http://www.jfvs.tpc.edu.tw/jfvs/%E6%95%99%E5%AD%B8%E7%B5%84/%E5%B0%88%E9%A1%8C%E5%A0%B1%E5%91%8A/93%E6%95%B8%E5%AD%B8%E7%A7%91/%E5%86%8D%E4%BF%AE%E6%AD%A3%E7%89%88.doc

11 遞迴的定義 一個數列 ，如果給定前幾 項 ( 如： a 1 、 a 2 、 a 3 ) 的值，稱 為，初始條件。一般項 a n 可用前 相鄰數項： a n-1, a n-2, …… 來表示 ，稱為 --- 遞迴關係 。 一個數列 ，如果給定前幾 項 ( 如： a 1 、 a 2 、 a 3 ) 的值，稱 為，初始條件。一般項 a n 可用前 相鄰數項： a n-1, a n-2, …… 來表示 ，稱為 --- 遞迴關係 。 http://www.jfvs.tpc.edu.tw/jfvs/%E6%95%99%E5%AD%B8%E7%B5%84/%E5%B0%88%E9%A1%8C%E5%A0%B1%E5%91%8A/93%E6%95%B8%E5%AD%B8%E7%A7%91/%E5%86%8D%E4%BF%AE%E6%AD%A3%E7%89%88.doc

12 以傳說中 ---64 根棒子為例 已遞迴直接推 已遞迴直接推 http://www.jfvs.tpc.edu.tw/jfvs/%E6%95%99%E5%AD%B8%E7%B5%84/%E5%B0%88%E9%A1%8C%E5%A0%B1%E5%91%8A/93%E6%95%B8%E5%AD%B8%E7%A7 %91/%E5%86%8D%E4%BF%AE%E6%AD%A3%E7%89%88.doc

13 令 與原式比較，得： 原式化為： http://www.jfvs.tpc.edu.tw/jfvs/%E6%95%99%E5%AD%B8%E7%B5%84/%E5%B0%88%E9%A1%8C%E5%A0%B1%E5%91%8 A/93%E6%95%B8%E5%AD%B8%E7%A7%91/%E5%86%8D%E4%BF%AE%E6%AD%A3%E7%89%88.doc

14 http://www.jfvs.tpc.edu.tw/jfvs/%E6%95%99%E5%AD%B8%E7%B5%84/%E5%B0%88%E9%A1%8C%E5%A0%B1%E5%91%8A/93%E6%95%B8%E5%AD%B8%E7%A7%91/%E5%86%8D%E4%BF%AE%E6%AD%A3%E7%89%88.doc

15 公比： 故 http://www.jfvs.tpc.edu.tw/jfvs/%E6%95%99%E5%AD%B8%E7%B5%84/%E5%B0%88%E9%A1%8C%E5%A0%B1%E5%91%8A/93%E6%95%B8%E5%AD%B8%E7%A7%91/%E5%86%8D%E4%BF%AE%E6%AD%A3%E7%89%88.doc

16 結論 : 事實上，若有 n 個盤子， 則移動完畢所需之次數 為 2^n - 1 事實上，若有 n 個盤子， 則移動完畢所需之次數 為 2^n - 1 http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm

17 所以 --- 河內塔問題需要 2 -1 次的 搬動，也就是說： 64 片的 金屬片至少需經過 18,446,744,073,709,551,6 15 次的搬移才能完成。 河內塔問題需要 2 -1 次的 搬動，也就是說： 64 片的 金屬片至少需經過 18,446,744,073,709,551,6 15 次的搬移才能完成。64 http://tw.knowledge.yahoo.com/question/question?qid=1011033004446

18 假如一位僧侶每秒可以 移動一片金屬片，日以 繼夜不眠不休地工作， 大概也要花上 584,942,417 年，約 5850 億年的時間，這 是非常非常遙遠的事。 假如一位僧侶每秒可以 移動一片金屬片，日以 繼夜不眠不休地工作， 大概也要花上 584,942,417 年，約 5850 億年的時間，這 是非常非常遙遠的事。 http://tw.knowledge.yahoo.com/question/question?qid=1011033004446

19 科學家估計地球約已 存在 20 億年，並沒有 一種生物可以活得這 麼久，且以太陽系壽 命約 200 億年而言， 移完 64 片的金屬片， 地球乃至太陽系或許 早已不存在。 科學家估計地球約已 存在 20 億年，並沒有 一種生物可以活得這 麼久，且以太陽系壽 命約 200 億年而言， 移完 64 片的金屬片， 地球乃至太陽系或許 早已不存在。 http://tw.knowledge.yahoo.com/question/question?qid=1011033004446

20 河內塔相關影片 --- http://www.youtube.com/watch?v= gadQDCRr7U8&feature=player_emb edded#at=112 http://www.youtube.com/watch?v= gadQDCRr7U8&feature=player_emb edded#at=112 http://www.youtube.com/watch?v= gadQDCRr7U8&feature=player_emb edded#at=112 http://www.youtube.com/watch?v= gadQDCRr7U8&feature=player_emb edded#at=112 http://www.youtube.com/watch?v= b_Ttds3dx0Q http://www.youtube.com/watch?v= b_Ttds3dx0Q http://www.youtube.com/watch?v= b_Ttds3dx0Q http://www.youtube.com/watch?v= b_Ttds3dx0Q

21 動畫 No.1Tower of Hanoi(2-D) http://www.youtube.com/watch?v= x38rLnXKP-Y http://www.youtube.com/watch?v= x38rLnXKP-Y No.2ower of Hanoi(3-D) http://www.youtube.com/watc h?v=a0IEQ_5e5iE&feature=rel ated http://www.youtube.com/watc h?v=a0IEQ_5e5iE&feature=rel ated

22