大学计算机导论第八章--算法-PPT课件.ppt

冒泡排序示例 插入排序 插入排序的基本思想 基本思路： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序，直到待排序数据元素全部插入完为止。即经过i-1遍处后,L[0..i-2]己排好序。第i遍处理仅将L[i-1]插入L[0..i-2]的适当位置p，原来p后的元素一一向右移动一个位置,使得L[0..i-1]又是排好序的序列。  插入排序示例 查找 4 12 36 14 62 91 8 22 7 81 77 10 所需查找的位置 给定目标值（62） 顺序查找 折半查找 * 第八章 算法 8.1算法定义 □一种逐步解决问题或完成任务的方法。 一种逐步解决问题或完成任务的方法 输入列表 输出列表 示例 12 8 13 9 11 将最大值置为第一个数 步骤1 如果第二个数大于最大值，将最大值置为第二个数 步骤2 如果第三个数大于最大值，将最大值置为第三个数 步骤3 如果第四个数大于最大值，将最大值置为第四个数 步骤4 如果第五个数大于最大值，将最大值置为第五个数 步骤5 寻找最大值 13 输出结果 示例 12 8 13 9 11 将最大值置为-∞ 如果当前数比最大值大，将最大值置为当前数 步骤0 步骤1 ● ● ● 如果当前数比最大值大，将最大值置为当前数 步骤5 寻找最大值 13 输出结果 细化 泛化 输入列表 将最大值置为-∞ 如果当前数大于最大值，将最大值置为当前数 重复下一步骤N次 最大值 寻找最大值 8.2三种结构 顺序结构、判断结构、循环结构 8.3 算法的表示 流程图 伪代码 流程图 为了便于交流，使用图形表示算法。我们常用的几种符号为： 输入输出框 处理框 判别框 流程线 1、计算c=a+b的算法 开始 输入a、b的值 c=a+b 输出c的值 结束 顺序 顺序结构的经典例题！ 交换两个变量的值 开始 输入a、b的值 c=a 输出a、b的值 结束 a=b b=c 判断 ——IF……语句 1、单分支结构 If 条件 then [语句] End If 条 件 语 句 否 是 2、双分支结构 If 条件 then [语句组1] Else [语句组2] End If 语句组1 语句组2 条 件 是 否 判断输入的自然数X的奇偶性。 提示：偶数除以2的余数为0，而奇数除以2的余数为1。 输入X Y=0 输出“X是偶数” 输出“X是奇数” 开始 结束 Y N Y=X除以2的余数 算法的表示流程图 动作1 动作2 ● ● ● 动作n a)顺序 测试 另一个动作序列 一个动作序列 假 真 b)判断 While条件 一个动作序列 真 假 c)循环 算法的表示伪代码 Action 1 Action 2 ● ● ● Action n a)顺序 If(condition) then action action … else action action … End if b)判断 while(condition) action action … End while c)循环 例1： 用伪代码写出一个求两个整数的和的算法. 算法：SumofTwo(first,second) 目的：求两整数之和 前提：给定两个整数(first,second) 后续：无 返回：和的值 { sum←first+second return sum } 例２： 用伪代码写出一个可以把成绩分成及格或不及格的算法。 算法：pass/Nopass(score) 目的：给定分数，创建及格、不及格等级 前提：给定要被改成等级的分数 后续：无 返回：等级 { If(score ≥60) grade ←”pass” Else grade ←”nopass” Return grade } 8.4 算法特征 算法的五个重要特性 确定性、能行性、输入、输出、有穷性 1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。 2）能行性： 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。 3）输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合。 4）输出 一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。 5）有穷性 一个算法总是在执行了有穷步的运算之后终止。 8.5 基本算法 求和 乘积 排序 查找 求和 置sum为0 是 是否有 更多的数字 将当前数 与sum相加 否 求和算法可分为三个逻辑部分