103 算法案例【杨高】.ppt_第1页
103 算法案例【杨高】.ppt_第2页
103 算法案例【杨高】.ppt_第3页
103 算法案例【杨高】.ppt_第4页
103 算法案例【杨高】.ppt_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

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

文档简介

1、第十章算法初步,10.2.2 程序框图,10.3 算法案例,一、穷举算法,穷举算法是按照一定顺序，列举所有可能的情形，,并从中找出符合条件的解的过程.,例：找出自然数15中，三个不同的数的组合.,解：,例：求能使得 为完全平方数的所有,整数 .,解：设,一、穷举算法,穷举算法是按照一定顺序，列举所有可能的情形，,并从中找出符合条件的解的过程.,，则,由于,因此可以穷举得,二、递归算法,递归算法将当前的状态或计算转化为以前的状态,或计算的算法.,例： 每次只能走一个或两个台阶，问走到第十个,台阶有几种走法？,解：假设走到第 个台阶有 种走法，则,例：每张票50元，每人购一张，400人手持50元,

2、200人手持100元，若一开始没零找，问有多少种,不出现找不开钱的排队方式？,解：记 为 m 个人手持50元，n 个人手持,100元时排队总数.则有：,这样就可利用计算机求出符合条件的排队数.,三、贪心算法,贪心算法采用逐步构造最优解的方法，在每一阶段,都作出一个局部最优解，当然其整体上未必最优.,例:,有5件物品，背包的容量为100，,物品的重量和价值分别如下所示：,问：如何选择可使装入背包的物品价值最大？,(1)选择价值最大的；(2)选择重量最轻的；,(3)选择单位重量价值最大的.,四、分治算法,分治算法 为解决一个大的问题，可以把它分成多,个更小的问题，分别解决后再把解答组合起来，,即可

3、得到原问题的解答.,例:8块重量不同金块，如何比较可以较快的找出,重量最轻和最重的金块？, , , , , ,解：分成四组，两两比较，只需10次.,五、中国古代数学中的算法案例,1.“更相减损术”用两个正整数中较大的数减去,较小的数，一直操作下去直至产生一对相等的数，,这个数就是最大公约数.,更相减损之术又名等值算法.,例：,五、中国古代数学中的算法案例,2. 秦九韶算法 多项式计算的最先进算法之一.,共计9次乘法，5次加法,共计5次乘法，5次加法！,逐项求和法：,秦九韶算法：,例：,五、中国古代数学中的算法案例,3. “大衍求一术” 解决一次同余方程组的求解,例：“今有物不知其数，三三数之剩二，五五数,之剩三，七七数之剩二，问物几何？,解：分别找到15，21，70三个数，,它们被3，5，7中的两个数

人人文库> 全部分类> 应用文书 > 研究报告

温馨提示

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

最新文档

评论

0/150

提交评论