初中九年级信息技术汉诺塔问题递归算法_第1页
初中九年级信息技术汉诺塔问题递归算法_第2页
初中九年级信息技术汉诺塔问题递归算法_第3页
初中九年级信息技术汉诺塔问题递归算法_第4页
初中九年级信息技术汉诺塔问题递归算法_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

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

文档简介

汉诺塔问题-递归算法在印度的一个古老传说中，大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上由大到小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下往上由大到小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。传说从创世纪到现在，婆罗门还在那里移动着圆盘呢！我们现在用计算机帮助婆罗门，看看64片圆盘要移动多少次。议一议我们还是先用手工计算的方法来看看小规模时需要的次数，填写下表，你看出什么规律了吗？盘子个数1234……移动个数13715学一学假设三根柱子分别叫做A，B，C，盘子由小到大标记为1，2，3……起始状态所有的盘子从上到下由小到大放在A柱子上，终止状态是所有的盘子由小到大放在C柱子上。当问题规模比较大时，我们一般考虑从小规模开始找规律：1.n=l时，1号盘子在A柱子上，直接移到C柱子；2.n=2时，1，2号盘子在A柱子上，很容易看出，先将1号盘子移到B柱子上中转一下，再将2号盘子直接移到C柱子，然后将B柱子上的1号盘子移过来；3.n=3时也可以仿效n=2，先设法将1，2号盘子移动到B柱子上（可能不止一步），再将3号盘子直接移到C柱子，然后将B柱子上的1，2号盘子移过来（可能不止一步）；4.n=4时也可以仿效n=3，先将1，2，3号盘子移动到B柱子上（可能不止一步），再将4号盘子直接移到C柱子，然后将B柱子上的1，2，3号盘子移过来（可能不止一步）；5.我们发现规律，n个盘子的话可以分三步走：（1）n-1个盘子从A柱子经过C柱子移到B柱子上；（2）将第n个盘子直接从A柱子移到C柱子；（3）再将前面那n-1个盘子从B柱子经过A柱子移到C柱子上。看得出，我们将n个盘子的问题转化成了两次n-1个盘子的移动和中间一个单盘移动，这种将大问题转化为规模缩小了的同类问题的子问题来求解的方法我们一般称为递归。汉诺塔问题的python程序：程序第二行是程序的出口，当n=1的时候直接移动并程序结束，否则，分成7步：1.han（n-1，A，C，B）先将n-1个盘子想办法从A通过C移到B上面来等候；（怎么移动，递归）2.printA+→+C最后一个n号盘子直接移动；3.han（n-1，B，A，C）将刚才在B上的那n-1个盘子从B通过A移动到C。（怎么移动，递归）han（4，‘A’，‘B’，‘C’）的执行过程如图所示：做一做1.运行刚才的程序看看n=5时候程序是怎么执行的。2.64个盘子要移动多少次？假设1秒钟移动一次，需要多少时间？想一想生活中的递归的例子：1.两面镜子平行相

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论