[工学]计算机科学导论第5讲_新.pptVIP

第5讲 算法 2010 主要内容 2 一．算法概念 二．算法结构 三、算法表示（流程图、伪代码、N-S图等） 四．基本算法（计数，累加，值交换，求最大（小）值，穷举、迭代、递推、递归） 一、 算法的概念 1 算法的定义 为解决问题而采取的方法和步骤。（非正式） 算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。（正式） 3 4 2. 算法的分类 计算机算法可分为两大类： 数值运算算法： 求解数值 非数值运算算法： 事务管理 例1: 数值计算问题：结构静力分析计算需要解线性代数方程组。 例2: 非数值计算问题：计算机对弈 算法—对弈的规则和策略 模型—棋盘及棋盘的格局 3.算法的基本特征 有穷性：任何算法都会在有限步后终止； 确定性：算法的每一步都有唯一的含义； 有效性：算法的每一步都可以被执行； 有输入：可以有多个输入，也可能没有输入； 有输出：算法至少有一个输出结果。 5 6 4.算法设计的原则 正确性：对于一切合法的输入数据都能得出满足要求的结果。 可读性：算法应该易理解，便于交流。 健壮性：当输入非法数据时，算法应恰当地作出反应或进行相应处理。 高效率与低存储量需求：算法执行时间较少，算法执行所需存储空间较小。 定义动作 确定一系列的步骤，每一步都只完成一个动作。 精化 剔除重复的步骤； 不同的步骤完成的动作可能相同，但它们产生的结果不能相同。 泛化 使算法对尽可能多的具体问题具有适应性。 7 5.如何设计一个算法 8 例1：从一组正整数中找到最大的数。 （正整数个数＝2，3，… N） 例如, 12, 8; 12, 8, 13; 12, 8, 13, 9; 12, 8, 13, 9, 11, ….. 方法1： 第一步: 比较第一个数和第二个数; 第二步: 比较第一个数和第三个数; 第三步: 比较第二个数和第三个数; 方法2： 第一步：将最大值置为第一个数； 第二步：将第二个数和最大值进行比较，如果第二个数大于最大值，将最大值置为第二个数，反之保持最大值不变。 第三步：将第三个数和最大值进行比较，如果第三个数大于最大值，将最大值置为第三个数，反之保持最大值原值不变。 9 第二、三步程序功能相同，程序描述语言相似 和第二、三步不同 方法3： 第零步：将最大值置为零； 第一步：如果当前数大于最大值，那么将最大值置为当前数，否则保留原最大值； 第二步：重复第一步直至所有数全比较完。 10 二、 算法的三种基本结构 任何算法（或程序）都由三种基本结构组成： 顺序结构 判断（选择）结构 循环结构 任何算法都是上述三种结构的组合。 11 1. 顺序结构 12 2. 选择结构 13 3. 循环结构 14 三种基本结构的特点： 一个入口 一个出口 不出现死循环和死语句 15 16 17 18 用顺序结构描述将华氏温度F转换成摄氏温度C的流程。 算法： C=5/9*（F-32） 4. 顺序结构设计 顺序结构中，按语句的自然顺序依次执行。 19 已知三角形的3条边边长，求三角形面积。用顺序结构描述求三角形面积的流程。 20 用顺序结构描述两个值（a=1, b=2）交换的流程 1 2 b c a 1 2 1 1 2 a b 1 1 21 选择结构（分支结构），根据选择结构中判断的结果，选择执行相应的语句。 5. 选择结构及其程序设计 例 用选择结构描述求两个数中的最大值的流程 22 例 用选择结构描述检查某年是否闰年的流程。 N年为闰年满足下列条件之一： 1.N能被400整除 2.N能被4整除，但不能被100整除 23 用选择结构描述检查某成绩级别的流程。 成绩N的级别： A级--N≥90 B级—90N≥80 C级—80N≥60 D级—N60 24 循环结构：当循环控制条件为真时反复执行循环体中的语句，直到循环控制条件为假时为止。 累加器 计数器 用循环结构描述求10个学生成绩之和的流程 用T累计10个学生的成绩（K），用I记录累加的次数（I=1,2,…,10） 6.循环结构及其程序设计 25 例 用循环结构描述求10到100之间所有不能被3整除的整数的流程 对10到100之间所有数逐一验证，凡满足“不能被3整除”的整数即可输出。 26 I=1，输出1 J=1，输出1 J=2，输出2 I=2，输出2 J=1，输出1 J=2，输出2 I=3，输出3 J=1，输出1 J=2，输出2 27 例 打印边长为 m 的正方型 要求：从键盘输入 m 值，输出 m 行每行 m 个*号。 例：输入 m=4，输出的图形如下： * * * *