《RAPTOR流程图算法设计教程》课件ch9.pptx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《《RAPTOR流程图算法设计教程》课件ch9.pptx》由用户(momomo)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- RAPTOR流程图算法设计教程 RAPTOR 流程图 算法 设计 教程 课件 ch9
- 资源描述:
-
1、第9章 基本算法设计学习目标学习目标 掌握枚举、递推和递归算法的基本思想 熟练运用枚举、递推和递归算法设计程序,解决实际问题目录目录 9.1 枚举算法枚举算法 9.2 递推算法递推算法 9.3 递归算法递归算法9.1 9.1 枚举算法枚举算法9.1.1 9.1.1 枚举概述枚举概述9.1.29.1.2枚举枚举算法应用举例算法应用举例9.1.1 9.1.1 枚举枚举概述概述 枚举法是计算机求解问题最常用的方法之一,也是最简单、最直接的统计计数方法。枚举的枚举的概念概念 举法又称为穷举法、列举法;基本思想是逐一列出该问题可能涉及的所有情形,并根据问题的条件对各解进行逐个检验,从中挑选出符合条件的解
2、,舍弃不符合条件的解9.1.1 9.1.1 枚举概述枚举概述 枚举法的特点算法设计比较简单,只需要一一列举问题涉及的所有情形,一般规模的许多实际应用问题都可以使用枚举法求解9.1.1 9.1.1 枚举概述枚举概述 利用枚举法求解问题的利用枚举法求解问题的步骤步骤 确定枚举对象,根据问题的实际情况,确定哪个量为枚举对象;确定枚举范围,根据问题的实际情况,确定枚举对象的枚举范围,设计枚举循环;确定筛选条件,根据问题要求,确定对解的筛选条件;设计枚举程序,运行和调试,对结果进行分析、讨论。9.1.1 9.1.1 枚举概述枚举概述 枚举法枚举法实现实现 使用循环结构实现,在循环体中,根据求解的具体条件
3、,应用选择结构进行筛选,确定问题的解。9.1 9.1 枚举算法枚举算法9.1.1 9.1.1 枚举概述枚举概述9.1.29.1.2枚举枚举算法应用举例算法应用举例9.1.2 9.1.2 枚举算法应用枚举算法应用举例举例【例9-1】涂抹单据问题一张单据上有一个5位数组成的编号,万位数是1,百位数是8,个位数是9,千位数和十位数已经变得模糊不清。但知道这个5位数是67和59的倍数。请找出所有满足这些条件的5位数并输出。其算法可以表示如下:Step1:对枚举变量thousands赋初值为0;Step2:判断thousands9是否成立,若成立,则程序运行结束,否则转去执行Step3;Step3:对枚
4、举变量tens赋初值为0;Step4:判断tens9是否成立,若成立,则转去执行Step7,否则转去执行Step5;Step5:计算单据编号number的值number10809+thousands*1000+tens*10,如果(number mod 67=0)and(number mod 59=0),则输出这个5位数;Step6:取枚举变量tens的下一个值tenstens+1,转去执行Step5;Step7:取枚举变量thousands的下一个值thousandsthousands+1,返回Step4。【例9-2】鸡兔同笼问题一个笼子里关了鸡和兔子(鸡有2只脚,兔子有4只脚,没有例外)。
5、已知鸡和兔子的总数量为19,总腿数为44。请问鸡和兔子的数目分别是多少。问题分析:这道题目很显然可以用枚举法来解答,枚举对象为鸡、兔的数量,将它们分别设为chick、rabbit。下面就要确定枚举对象的枚举范围和筛选条件。依据题意,鸡、兔的数量均小于19,即chick、rabbit的枚举范围均为019。枚举对象应同时满足以下两个筛选条件:鸡和兔的总数量为19;鸡和兔的总腿数为44。则上述用关系表达式表示如下:(chick+rabbit=19)and(2*chick+4*rabbit=44)该问题涉及chick、rabbit两个变量的枚举,需要使用二重循环实现。其算法表示如下:Step1:对枚举
6、变量chick赋初值chick0;Step2:判断chick19是否成立,如果不成立,则转去执行Step3,否则程序运行结束;Step3:对枚举变量rabbit赋初值rabbit0;Step4:判断rabbit19是否成立,如果不成立,则转去执行Step5,否则,转去执行Step7;Step5:判断枚举变量chick、rabbit的取值是否满足筛选条件,若满足则输出chick、rabbit的值,否则执行Step6;Step6:取枚举变量rabbit的下一个值rabbitrabbit+1,转去执行Step4;Step7:取枚举变量chick的下一个值chickchick+1,转去执行Step2。
7、目录目录 9.1 枚举算法枚举算法 9.2 递推算法递推算法 9.3 递归算法递归算法9.2 9.2 递推算法递推算法在自然界中,所有事物都随着时间的推移呈现出微妙的变化。许多现象的变化是有规律可循的,这种规律往往呈现出前因后果的关系,即某些现象的变化和紧靠它前面的一个或一些结果密切相关。递推的思想正是体现了这一变化规律。9.2 9.2 递推算法递推算法9.2.1 9.2.1 递推概述递推概述9.2.29.2.2递推递推算法应用举例算法应用举例9.2.1 9.2.1 递推概述递推概述 递推算递推算法法 递推方法是一种简便高效的常见数学方法,它是利用问题本身所具有的一种递推关系求解问题的方法。9
8、.2.1 9.2.1 递推概述递推概述9.2.1 9.2.1 递推概述递推概述 递递推推方法方法递推方法正是利用问题本身所具有的递推关系进行求解的一种方法,利用递推方法求解问题的关键是确定问题的递推关系,即相邻数据项之间的关系。9.2.1 9.2.1 递推概述递推概述 递推求解递推求解步骤步骤 确定递推变量 建立递推关系 确定初始(边界)条件,即确定递推变量的初始(边界)值。对递推过程进行控制9.2.1 9.2.1 递推概述递推概述 递推方式递推方式 利用递推方法对问题求解,通常分为顺推和逆推两种。顺推算法 顺推是从前向后推,利用已知或已求得的第1,2,i-1项的解,推出第i的解,直到求得第n
展开阅读全文