河内塔(Tower of Hanoi).ppt_第1页
河内塔(Tower of Hanoi).ppt_第2页
河内塔(Tower of Hanoi).ppt_第3页
河内塔(Tower of Hanoi).ppt_第4页
河内塔(Tower of Hanoi).ppt_第5页
免费预览已结束，剩余1页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、數學遊戲一河內塔(Tower of Hanoi),河內塔 (Tower of Hanoi),法國數學家Edouard Lucas 在1883年所提出 傳說在古老的印度，有一座神廟，據說它是宇宙的中心。在廟宇中放置了一塊上面插有三根長木樁的木板，在其中的一根木樁上，從上至下被放置了64片直徑由小至大的盤子。古印度教的天神指示祂的僧侶們將64片的盤子移至三根木樁中的其中一根上。它們可以根據底下的規則由一個位置搬移到另外一個位置： 一次只能移動一個盤子。 大盤子永遠不能放在小盤子的上面。 這一疊盤子可以藉由另外一根木樁移到另外一個位置。 直到有一天，僧侶們能將64片的盤子依規則從指定的木樁上全部移動

2、至另一根木樁上，那麼，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界！,河內塔 (Tower of Hanoi),移動盤子1從木樁A到木樁B 移動盤子2從木樁A到木樁C 移動盤子1從木樁B到木樁C 總共需要 3 = 22-1次,N = 2,1.,2.,3.,A,B,C,河內塔 (Tower of Hanoi),移動盤子1從木樁A到木樁C 移動盤子2從木樁A到木樁B 移動盤子1從木樁C到木樁B 移動盤子3從木樁A到木樁C 移動盤子1從木樁B到木樁A 移動盤子2從木樁B到木樁C 移動盤子1從木樁A到木樁C 總共需要 7 = 23-1次,N = 3,1.,2.,3.,4.,5.,6.,

3、7.,A,B,C,河內塔 (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 億年，這是非常非常遙遠的事，科

人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论