合肥工业大学程序设计基础课件第02章 算法设计基础.ppt

第2章 算法设计基础 2.1 算法的描述 2.2 结构化算法设计初步 2.3 算法的计算复杂性 2.4 常用算法设计策略 2.1 算法的描述 2.1.1 自然语言方式 2.1.2 伪代码方式 2.1.3 程序流程图方式 2.1.4 N/S盒图方式 2.1.5 PAD图方式 2.1.1 自然语言方式 [例2.1] 算法描述示例，1.1.1中排序算法的自然语言描述。 2.1.3 程序流程图方式 算法由若干张流程图描述，每张流程图由结点和有向边构成，该图描述了算法中所进行的操作以及这些操作执行的逻辑顺序。 流程图的常用结点及控制结构描述如下 ： 2.1.4 N/S盒图方式 2.1.5 PAD图方式 PAD图结点与控制结构描述 2.1.5 PAD图方式 算法2.2的PAD图描述 2.2 结构化算法设计初步 2.2.1 算法描述 2.2.2 算法设计 2.2.1 算法描述 1. 结构化算法的流程图 2.2.1 算法描述 1. 结构化算法的流程图 2.2.1 算法描述 2. 结构化算法的PAD图 2.2.2 算法设计 2.2.2 算法设计 1. 主体结构设计 2.2.2 算法设计 2. 顺序结构设计 2.2.2 算法设计 3. 选择结构设计------双分支结构 2.2.2 算法设计 3. 选择结构设计------多分支结构 2.2.2 算法设计 3. 选择结构设计------多分支结构 2.2.2 算法设计 3. 循环结构设计 2.3 算法的计算复杂性 基本概念 2.3 算法的计算复杂性 [例2.9] 分析算法时间复杂性：将一个字符串倒序。 2.4 常用算法设计策略 2.4.1 分治法 2.4.2 递归技术 2.4.3 贪心法* 2.4.4 回溯法* 2.4.1 分治法 二进制乘法： 2.4.1 分治法 分治法计算二进制数乘法 2.4.2 递归技术 一种以有限方式描述规模任意大问题的方法 * * 学习目的： ① 掌握算法的流程图和PAD图描述方式； ② 初步掌握结构化算法设计； ③ 能够进行简单的算法复杂性分析； ④ 初步了解分治与递归。 算法的描述方式很多，不同描述风格适用于不同场合，在面向对象技术出现之前，人们倾向于在算法的描述中对未来程序的层次结构进行一定程度的控制，而不仅仅是描述具体的数据处理过程。本节介绍算法的常见描述方法。 2.1.2 伪代码方式 预先规定了描述规则和关键词，以接近某程序设计语言的风格描述算法。同时具有易理解和趋于形式化的优点。 端点符 处理 判断 预定义功能 连接符 条件 处理1 处理2 选择结构 循环结构 或 是 条件 否 处理 do-while 条件 处理 否 是 repeat-until 处理1 处理2 顺序结构 结束 x=a[j] a[j]=a[k] a[k]=x 是{交换两个元素} 否 i != k k=j 是 否 a[j] a[k] for j=i+1 to n step 1 {查找第 i 个数据后面的最小元素} k=i for i=1 to n-1 step 1 读n个数到数组a[n] 开始 算法2.2的N/S盒图描述 b 选择结构 d 循环结构 c 多选择结构 a 顺序结构 P1 P2 C P1 P2 Pn L1 L2 X=… Ln P A 或 while c until c P1 P2 输入输出 重复 子算法 定义 选择 语句标号 处理 i ！= k k←i i←1；i=n-1；i←i+1 x←a[j]；a[j] ←a[k]；a[k] ←x j←1；j=n；j←j+1 k←j a[j]a[k] a[n] 算法开始 算法结束 将组成算法的多个操作按照不同的层次组织在一起，每一组代表一种复杂的相对独立的复合操作，各复合操作的内部亦可进行层次划分，从而形成整个算法的嵌套层次结构。 每一组操作具有惟一的入口和惟一的出口，即一端进一端出。这样的操作组置于其他操作中时，算法的执行顺序必定是从前一组操作的出口到本组操作的入口，经过本组内部的运算，到达本组操作的惟一出口。 各组之间利用顺序、选择和循环等三种控制结构在不同组之间进行连接，从而形成更高层次的算法结构。 结点与控制结构 功能结点 判定结点（分支结点） 连接结点 顺序结构 分支结构 循环结构 C B A c1 blk5 c2 true c4 true blk3 blk4 blk2 c3 true blk1 true ... do { if(c2) 则 if(c4)