武汉理工大学：《软件技术基础》课程教学资源（PPT课件）第2章 算法

第二章算法 2.1算法的两要素 2.2算法的特征 2.3算法的表示 2.4常用算法 2.5算法的设计要求 2.6算法的复杂度分析

第二章 算法 2.1 算法的两要素 2.2 算法的特征 2.3 算法的表示 2.4 常用算法 2.5 算法的设计要求 2.6 算法的复杂度分析

解决问题一般步骡 实际问题-〉模型-〉算法-〉程序〉结果 解决问题的核心 算法以及算法的处理对象 数据的结构

解决问题一般步骤 实际问题--〉模型--〉算法--〉程序--〉结果 解决问题的核心 -- 算法以及算法的处理对象 -- 数据的结构

程序与算法 何谓算法: 解题过程的准确、完整的描述称作解该问题的 算法 何谓程序:就是用计算机语言表述的算法 口流程图就是图形化了的算法 程序=算法+数据结构

程序与算法 何谓算法： 解题过程的准确、完整的描述称作解该问题的 算法 何谓程序：就是用计算机语言表述的算法 流程图就是图形化了的算法 程序＝算法＋数据结构

2.1算法的两要素 算法由对数据对象的运算和操作与算法的控制结构 两要素组成 1.算法中对数据的运算和操作 (1)逻辑运算:“与”、“或”、“非”; (2)算术运算:加、减、乘、除; (3)数据比较:大于、小于、等于、不等于; (4)数据传送:输入、输出、赋值

2.1 算法的两要素 算法由对数据对象的运算和操作与算法的控制结构 两要素组成 1.算法中对数据的运算和操作 (1) 逻辑运算： “与”、“或”、“非”； (2) 算术运算： 加、减、乘、除； (3) 数据比较： 大于、小于、等于、不等于； (4) 数据传送： 输入、输出、赋值

2控制结构 算法的控制结构,决定了各操作的执行次序。用 流程图可以形象地表示出算法的控制结构 任何复杂的算法都可以用顺序、选择、循环三种 控制结构组合而成 S1 F S2 S1 S2 B S3 (d)

2. 控制结构 算法的控制结构，决定了各操作的执行次序。用 流程图 可以形象地表示出算法的控制结构 任何复杂的算法都可以用顺序、选择、循环三种 控制结构组合而成 S 1 S 2 B S 1 S 2 B S (a) (b) (c) S 3 F T B F T (d) S

2.2算法的基本特征 算法是由一套计算规则组成的一个过程 1.确定性算法中每一个指令须有明确的含义,不能有二义性 2.可行性算法中描述的操作都可实现执行结果能达到预期目标 3.输出每种算法必须有确定的结果,产生一个或多个输出 4.输入每个算法必须有0个(自动生成初始数)或多个输入 5.有穷性解答必须在有限步内得到,不能出现“死循环” 我们可以得出如下的结论:算法是一个过程,这个过程由一套明 确的规则组成,这些规则指定了一个操作的顺序,以便用有限 的步骤提供特定类型问题的解答

2. 2 算法的基本特征 算法是由一套计算规则组成的一个过程 1.确定性 算法中每一个指令须有明确的含义，不能有二义性 2.可行性 算法中描述的操作都可实现,执行结果能达到预期目标 3.输 出 每种算法必须有确定的结果，产生一个或多个输出 4.输 入 每个算法必须有0个（自动生成初始数）或多个输入 5.有穷性 解答必须在有限步内得到,不能出现“死循环” 我们可以得出如下的结论：算法是一个过程，这个过程由一套明 确的规则组成，这些规则指定了一个操作的顺序，以便用有限 的步骤提供特定类型问题的解答

2.3算法的表示 算法设计一般是由粗到细的过程,一般可以使用下面 几种类型的工具描述算法: 1.自然语言 自然语言描述算法通俗易懂,但它有着难以克服的缺陷: (1)易产生歧义性 (2)语句繁琐冗长,很难清楚地表达算法的逻辑流程 (3)当今的计算机尚不能处理用自然语言表示的算法 2.专用工具 常用的有流程图、问题分析(PAD)和NS盒图、伪代码等。 3.算法描述语言 为了便于转换成某种编程语言,一般采用准程序设计语 言作算法描述语言。例如,类C语言继续

2. 3 算法的表示 算法设计一般是由粗到细的过程，一般可以使用下面 几种类型的工具描述算法: 1.自然语言 自然语言描述算法通俗易懂，但它有着难以克服的缺陷： (1) 易产生歧义性 (2) 语句繁琐冗长，很难清楚地表达算法的逻辑流程 (3) 当今的计算机尚不能处理用自然语言表示的算法 2.专用工具 常用的有流程图、问题分析(PAD)和NS盒图、伪代码等。 3.算法描述语言 为了便于转换成某种编程语言，一般采用准程序设计语 言作算法描述语言。例如，类C语言继续

流程图是采用不同的几何图形来描述算法的逻辑结 构,每个几何图形表示不同性质的操作 常用流程图符号: 开始 输入a,b N>10 true 结束 fa (a)起止框、连接框 (b)输入输出框 (c)判断框 N为正整数 (d)处理框 (e)注释框 (f)流向线 返回

流程图 是采用不同的几何图形来描述算法的逻辑结 构，每个几何图形表示不同性质的操作 开始 结束 (a) 起止框、连接框 (b) 输入输出框 A A 输入a,b N>10 (c) 判断框 true false (d) 处理框 i+1→i (e) 注释框 (f) 流向线 N为正整数 常用流程图符号： 返回

2.4常用算法 1.枚举法(穷举法)(常用) 基本思想是: 先依据题目的部分条件确定答案的大致范围 在此范围内对所有可能的情况逐一验证,直到全部 情况验证完 若某个情况使验证符合题目的条件,则为本题的 个答案;若全部情况验证完后均不符合题目的条件, 则问题无解 例:百元买百鸡:公鸡5元、母鸡3元、小鸡1元

1.枚举法（穷举法）（常用） 基本思想是： 先依据题目的部分条件确定答案的大致范围 在此范围内对所有可能的情况逐一验证，直到全部 情况验证完 若某个情况使验证符合题目的条件，则为本题的一 个答案；若全部情况验证完后均不符合题目的条件， 则问题无解 例：百元买百鸡： 公鸡5元、母鸡3元、小鸡1元 2. 4 常用算法

2.迭代法 使一个复杂问题的求解过程转化为相对简单的迭代 算式的重复执行过程。 基本思想:通过列举少量的特殊情况,经过分析, 最后找出一般的关系。 基本方法: 首先确定一个合适的迭代公式,选取一个初始近似值以 及解的误差 然后用循环处理实现迭代过程,终止循环过程的条件是 前后两次得到的近似值之差的绝对值小于或等于预先给 定的误差 并认为最后一次迭代得到的近似值为问题的解。 例:数值计算方法

2.迭代法 使一个复杂问题的求解过程转化为相对简单的迭代 算式的重复执行过程。 基本思想：通过列举少量的特殊情况，经过分析， 最后找出一般的关系。 基本方法： 首先确定一个合适的迭代公式，选取一个初始近似值以 及解的误差 然后用循环处理实现迭代过程，终止循环过程的条件是 前后两次得到的近似值之差的绝对值小于或等于预先给 定的误差 并认为最后一次迭代得到的近似值为问题的解。 例：数值计算方法