用穷举法解决问题.ppt_第1页
用穷举法解决问题.ppt_第2页
用穷举法解决问题.ppt_第3页
用穷举法解决问题.ppt_第4页
用穷举法解决问题.ppt_第5页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

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

文档简介

1、阅读下面程序，分析执行过程，说出程序功能,For I=100 to 999 A=int(I/100) B=int(I/10) mod 10 C=I mod 10 If a3+b3+c3=I then print I Next I,求出100到999之间的所有水仙花数,3.2 用穷举法解决问题,一、什么是穷举法,穷举法又称枚举法、列举法，它将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题将最终得以解决。,方法一： For I=100 to 999 A=int(I/100) B=int(I/10) mod 10 C=I mod 10 If a3+b

2、3+c3=I then print I Next I,方法二： For a=1 to 9 for b=0 to 9 for c=0 to 9 if a3+b3+c3=a*100+b*10+c then print a*100+b*10+c endif next c next b next a,二、用穷举法解决问题的步骤,1、确定问题解可能搜索的范围：用循环或嵌套来实现） 2、写出符合问题解的条件：用if语句实现 3、尽可能地缩小搜索的范围，减少程序运行时间，提高程序的执行效率。,例：公元前5世纪，我国数学家张丘建在算经一书中提出了一个“百钱买百鸡问题”。问题如下：鸡翁一值钱5，鸡母一值钱3，鸡

3、雏三值钱1。百钱买百鸡，问鸡翁、鸡母和鸡雏各几何？,分析：,穷举的对象：,穷举的范围：,判断式：,鸡翁、鸡母、鸡雏,0 X 100 0 Y 100 0 Z 100,x +y+z=100 且 5*x+3*y+z/3=100,思考：如何提高算法的效率？,1、减少循环的次数，通过缩小穷举范围,0 a 100 / 5 0 b 100 / 3 0 c 100,2、减少循环嵌套的层数,0 a 100 / 5 0 b 100 / 3 c = 100 a b,例3：生活中的问题 某同学用自己的QQ号登录，可他记不清密码了，你能帮他找回密码吗？他的密码是一个5位数，678，其中百位和十位上的数字他不记得了，但他还记得该数能够被78整除，也能被67整除。你能帮他设计一个算法求出该密码吗？,(1)判断下列两题能否用穷举算法解决，为什么？,在一个直角三角形中，三条边a、b、c的长度都为整数，且一条直角边a的长度已确定，斜边c的长度不能超过某数I，找出满足条件的所有直角三角形。 使用一根长度为L厘米的铁丝，制作一个面积为S的矩形框，要求，计算出满足这种条件的矩形的高h和宽w。 孙子算经中有许多有趣的数学题，“鸡兔同笼”问题就是一个典型的例子。原题是：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”,四、穷举算法的优点与缺点 ：,优点：算法简单,缺点：运行时所花费的时间长。,三、穷举算法适

人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

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

最新文档

评论

0/150

提交评论