第5章 程序设计基础解析.ppt

螺旋模型 1988年由TRW公司的B.Boehm提出，将瀑布模型和演化模型结合，并强调了其他模型都忽略了的风险分析。 并发模型 并发模型也称并发工程，它表达了在软件项目任一阶段的活动之间存在的并发性。 基于构件的开发模型 基于构件的开发（CBD）模型（如图5.18所示）融合了螺旋模型的许多特征，本质上是演化型的，要求软件创建迭代过程，但是基于构件的开发模型是利用预先封装好的软件构件来构造应用的。 小 结 程序设计的基本方法 程序设计语言 算法的表示方法 常用的算法 软件工程 软件生存周期 * 每章首页幻灯片 * * 内容幻灯片 * 内容幻灯片 * 内容幻灯片 * 内容幻灯片 * 内容幻灯片 * 内容幻灯片 * * * * 自然语言 自然语言描述方法的缺点： 自言语言的歧异性容易导致算法执行的不确定性。 自然语言的语句一般太长，从而导致了用自然语言描述的算法太长。 由于自然语言表示的串行性，因此，当一个算法中循环和分支较多时就很难清晰地表示出来。 自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。 程序流程图 程序流程图符号 程序流程图 以求解sum=1+2+3+4+5……+（n-1）+n为例来介绍算法的流程图描述方法 N-S流程图 N-S流程图简称N-S图，也被称为盒图。N-S图是在1973年，由美国学者I.Nassi 和 B.Shneiderman提出来的，并分别取两人名字的首字母来进行命名。N-S图是在程序流程图的基础上去掉流程线，将全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框的一种算法表示方法。即由一些基本的框组成的一个大框。 N-S流程图 N-S流程图的三大结构 顺序结构 选择结构 循环结构 N-S流程图 写出求sum=1+2+3+4+5……+（n-1）+n的 N-S图的描述方法 伪代码 用流程图或N-S图来描述算法虽然形象直观，但在算法设计过程中使用起来并不十分方便，特别是当算法稍微复杂一点时，不易修改。 在实际的算法设计中，常常使用自然语言或计算机语言或类计算机语言来描述。 这里的类计算机语言是一种非计算机语言，借用了一些高级语言的某些成分，没有加入严格的规则，而且不能够被计算机所接受，称其为“伪代码”。 伪代码 写出求sum=1+2+3+4+5……+（n-1）+n的 伪代码的描述方法 (1) 算法开始； (2) 输入 n 的值； (3) i ← 1； (4) sum ← 0； (5) do while i=n (6) { sum ← sum + i； (7) 　i ← i + 1；} (8) 输出 sum 的值； (9) 算法结束； 5.2.3 常用算法介绍 1.枚举法 2.递推法 3.求最大值、最小值问题 4.交换两个变量的值 5.排序算法 6.查找算法 枚举法又称为穷举法 基本思想：根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况均通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。 特点：算法简单，容易理解，运算量大 1.枚举法 1.枚举法 应用：百钱买百鸡问题 假定公鸡每只5元，母鸡每只3元，小鸡3只1元。现有100元钱要求买100只鸡，问共有几种购鸡方案？ 问题分析：根据题目，设公鸡、母鸡、小鸡各为x，y，z只，列出方程为： x+y+z=100 5x+3y+z/3=100 巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是一种重要的算法设计策略： ①穷举法几乎可以通用于任何领域的问题求解，可能是唯一一种解决所有问题的一般性方法 ②即使效率低下，仍可用穷举法求解一些小规模的问题实例； ③如果解决的问题实例不多，而穷举法可用一种可接受的速度对问题求解，那么花时间去设计一个更高效地算法是得不偿失的。 1.枚举法 [思考题]举例说明生活中的穷举法应用。 递推法又称为迭代法 基本思想：利用问题本身所具有的某种递推关系求解问题。从初值出发，归纳出新值与旧值间存在的关系，从而把一个复杂的计算过程转换为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。 2.递推法 2.递推法 基本思想：采用如同打擂台的方法。在n个数中，先假设第一个数为最大值，称为擂主，依次同第2，3，……，n个数据逐一比较，一旦某个数大，马上替换擂主；所有值比较完，最大值也就获得。求最小值问题则先假设第一个数为最小值。 3.求最大值、最小值问题 3.求最大值、最小值问题 应用：对输入的若干个学生成绩，求出最高分和最低分。 max=min=a[0]； 用max依次与后续的成绩进行对比，若比max大则将相应值赋值给max； 用min依次与后续的成绩进行对比，若比mi