數學遊戲一 河內塔 (Tower of Hanoi)

Slides:



Advertisements
Similar presentations
更多精彩请点击这里访问 在迪拜的外来人口中,来自 202 个国家和地 区。中国人很多,奉行自由经济政策。近 20 多年来, 迪拜利用 “ 石油美元 ” 建成了一系 列现代化配套基础设施。凭借这些设施和优 越的地理位置,以及传统的转口贸易优势, 迪拜大力发展非石油产业,经济、社会发展.
Advertisements

主编:南湖小学 五( 2 )班 张敏君 铃草出版社 目录. 上一张结束下一张 哈利法塔 (迪拜) 佩特纳斯大厦 (吉隆坡) 地王大厦(深圳) 金茂大厦(上海) 帝国大厦(纽约) 中环广场(香港)
Big Ben.
MBBR工艺在污水处理厂 升级改造中的应用 青岛思普润水处理有限公司 2011年3月.
范 彬 博士 副研究员 住建部农村污水处理技术北方研究中心 中国科学院生态环境研究中心 二〇一一年七月
电子商务行业解决方案 农业银行电子商务行业解决方案是根据商户的电子商务支付结算需求以及所采用的电子商务模式,结合商户的行业特点定制而成的极具针对性电子商务产品服务。 农业银行电子商务行业解决方案可以有效地满足农林牧渔、能源矿产、生产制造、工程建筑、商贸批发、网购零售、交通运输、酒店旅游、 IT电信、基金保险、文体娱乐、公用事业等行业的个性化电子商务需求。
小水滴的旅行VCD 奇妙的水 第三單元 1. 小水滴的旅行 2. 水溶液的性質 吳端敏 Lucas 製.
第五章 高层建筑结构的其它设计方法 5-1 选择有效的房屋形式以控制侧移 5-2 楼屋盖结构 5-3 基础 5-4 国内外高层建筑实例.
電子白板應用軟體研習 主講人: 龔盟育
图书馆基础知识培训 盐城市图书馆
第三篇 建筑电气 14 建筑供配电与照明系统的安装、调试及验收 主 编:刘昌明 鲍东杰.
知识改变命 运 学习成就未来! 向各位问好 点击翻页.
高雄女中 林義強 John Lin.
算法设计与分析 李清勇 教授 办公室:第九教学楼北201.
新北市及人中學 數學科教師研習 PISA評量 ─ 數學領域介紹
一、人口增长对生态环境的影响 1.无论局部地区,还是全国乃至全球,人口的 都是有限的。 环境容纳量 人口众多 2.我国在发展中遇到的困难和问题,许多都与 有 直接关系。 自然资源 3.人口增长过快,还在消耗大量 的同时,加剧了.
耶穌受難日及復活節紀念 2009/04/12 復活節.
高中信息技术新课程探讨 算法与程序设计教学实践与探讨 江苏省新海高级中学  张丽.
第五章 经纪业务相关实务.
湖南生物机电职业技术学院 图书馆 年9月 2012级 新生入馆教育 湖南生物机电职业技术学院 图书馆 年9月.
安全管理培训 民用建筑施工现场安全管理要点.
力特光電科技 /03/03.
Just foods & Equipment Co.,Ltd
Univeristy of Kansas 2011级—Monica 王循
班級:系統四乙 學號: 學生:柯鈞智 陳偉倫 何韋霖
本章主要讨论处理机分配问题 调度策略考虑: ①周转时间 ②吞吐率 ③相应时间 ④设备利用率 研究的内容有:
课程:机械设计A 祝同学们在新学期学习进步!.
14-2电磁感应定律 一、电磁感应现象 1、电磁感应现象的发现 1831年11月24日,Faraday发现电磁感应现象
触电预防与急救 杜芳艳.
大數據與我 班級:電商一甲 姓名:紀汝欣 學號:4A
图书分类讲座 主讲人:张凤兰.
系统优化 涉及上市公司业务调整介绍 中国结算深圳分公司 发行人业务部
数学补充 附录1-微积分运算.
第7章 工程项目进度控制 7.1 工程项目进度控制工作内容 7.2 工程项目施工进度控制方法.
澳门房地产市场研究2012 Macao Real Estate Market Research 2012 珠海中原事业一部二组.
广州重点商圈巨型LED屏幕 Kenneth Liang 梁 裕 M
Lenovo LI2721s 产品介绍.
組員: 陳曉東(2), 張梓錕(3), 蔡浩維(5), 鍾智灝(7), 馮浩然(8)
物件導向程式設計 (Object-Oriented rogramming)
地球上最瘋狂的城市-迪拜 在迪拜的外來人口來自202個國家和地區。
資料結構簡介.
Chapter 6 Advanced Counting Techniques
油畫大師布格羅的油畫世界 2018年11月27日星期二 FM.
$428 深圳五星級南海酒店 2009玩轉夏日嘉年華 每位客人套票價:
RESTRART 重新开始 2018.
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
口腔颌面神经疾患 白 晓 峰 中国医科大学口腔医学院整形外科.
第11章 递归 张坤龙 天津大学计算机学院.
鄧姚文 資料結構 第一章:基本概念 鄧姚文
鄧姚文 資料結構 第五章:遞迴 鄧姚文
2011 邀请中国姐妹学校韩国语研修团项目 申请时间: ~5月 27日 / 项目地点: 汉阳大学 安山校区 / 项目时间: (星期日) ~ 7.22(星期五) 费用: 100万元(韩币/人 (包含项目 - 学费, 教材费, 宿舍费, 接机费用及所有文化体验活动项目费用)
第十二章 品牌老化與再生.
计算机问题求解 – 论题1-4 - 基本的算法结构 2018年10月09日.
第十二章 施工组织计划技术.
複 活 的 大 廈 在2011年9·11事件12年後,在被恐怖分子襲擊倒塌的原世貿中心舊址上,“世界貿易中心一號樓”(1 World Trade Center ,原名“自由塔”-Freedom Tower)拔地而起。大樓設計高度1776英尺(541.3米),象徵美國通過【獨立宣言】的1776年,屋頂高417米,與原世貿中心北塔等高。大樓造價近40億美元。
資料結構與C++程式設計進階 遞迴(Recursion) 講師:林業峻 CSIE, NTU 6/ 17, 2010.
LCD封裝技術 LCD顯示原理 當光通過液晶時 扭轉型液晶與偏光板組合的液晶顯示 當液晶兩端加上電壓時 當與固定方向的 微細溝槽板 接觸
指導老師:潘瀅方老師、林秋萍老師、賴心茹老師
黎明职业大学图书馆使用指南 1.图书馆概况 2.图书馆布局 3.图书馆提供的服务 4.反对不文明现象.
$658 星河灣酒店 每位客人套票價: GRAND HOLIDAY (INT’L) LTD. Licence no : 順德港
作业3、4、6、7 俞天灿.
淘汰與搜尋法 /5/9 演算法 _ 第四章.
课件编号:K 编制人员: 袁慧 大型及典型事故案例 ——触电事故 ——蓝巢管理学院职业安全教育培训课件.
北一女中 資訊選手培訓營 遞迴、河內塔與merge sort Nan.
GPS卫星定位原理及其应用 定位的观测量、观测方程及误差分析
學生:黃冠中、吳俊潭、蘇洳宣、徐曼綾 指導老師:袁淑芬老師
台南市中小學網路維運宣導事項 (無線網路、資安通報) 台南市教育網路中心
遞迴 Recursion.
 等差數列 等差數列: a , a + d , a + 2d , a + 3d , 通項:
雙曲線的應用 內容說明: 從雙曲線的定義中,了解雙曲線 在生活上的應用.
Presentation transcript:

數學遊戲一 河內塔 (Tower of Hanoi)

河內塔 (Tower of Hanoi) 法國數學家Edouard Lucas 在1883年所提出 傳說在古老的印度,有一座神廟,據說它是宇宙的中心。在廟宇中放置了一塊上面插有三根長木樁的木板,在其中的一根木樁上,從上至下被放置了64片直徑由小至大的盤子。古印度教的天神指示祂的僧侶們將64片的盤子移至三根木樁中的其中一根上。它們可以根據底下的規則由一個位置搬移到另外一個位置: 一次只能移動一個盤子。 大盤子永遠不能放在小盤子的上面。 這一疊盤子可以藉由另外一根木樁移到另外一個位置。 直到有一天,僧侶們能將64片的盤子依規則從指定的木樁上全部移動至另一根木樁上,那麼,世界末日即隨之來到,世間的一切終將被毀滅,萬物都將至極樂世界!

河內塔 (Tower of Hanoi) 移動盤子1從木樁A到木樁B 移動盤子2從木樁A到木樁C 移動盤子1從木樁B到木樁C 總共需要 3 = 22-1次 1. 2. 3.

河內塔 (Tower of Hanoi) N = 3 移動盤子1從木樁A到木樁C 移動盤子2從木樁A到木樁B 移動盤子1從木樁C到木樁B 1. N = 3 移動盤子1從木樁A到木樁C 移動盤子2從木樁A到木樁B 移動盤子1從木樁C到木樁B 移動盤子3從木樁A到木樁C 移動盤子1從木樁B到木樁A 移動盤子2從木樁B到木樁C 總共需要 7 = 23-1次 2. 3. 4. 5. 6. 7.

河內塔 (Tower of Hanoi) 規律(假設A是來源木樁, C是目的木樁, B是暫時存放的木樁) 先將1至(n-1)號盤子從A經由C搬至B 將第n號盤子由A搬至C 再將1至(n-1)號盤子從B經由A搬至C 亦即將搬n個盤子的動作分解成三大步 第一步  搬動n-1個盤子 第二步  搬動一個盤子(第n個) 第三步  搬動n-1個盤子

河內塔 (Tower of Hanoi) 最少搬動次數為何? 假設至少須 T(n) 次的移動來完成 最少的總移動次數T(n) = T(n-1) + 1 + T(n-1)  T(n) = 2n-1 搬動64個盤子需要的次數264-1 =18,446,744,073,709,551,615 ≒ 1.84x1019 若每秒搬一次,則總共需 584,942,417,355年,大約是5850 億年,這是非常非常遙遠的事,科學家估計地球約已存在2,000,000,000年,也沒有一種生物能活這麼久,所以我們大可放心的睡覺。