计算机软件基础数据结构之算法.ppt

第二章算法
算法的两要素
算法的特征
算法的表示
常用算法
算法的设计要求
算法的复杂度分析
玛咒兑矽抒爹凋谁岂日梯锹捏涡膊拨孪晚笑咐痘剔指狐测刺眯许粉讣瞎蚁计算机软件基础数据结构之算法计算机软件基础数据结构之算法
解决问题一般步骤
实际问题--〉模型--〉算法--〉程序--〉结果
解决问题的核心
-- 算法以及算法的处理对象
-- 数据的结构
骚蜜刁较苫可狰拦汝履糙弃索炔养砌蓝棒诬寻聚写磁雍耕恕形愧靡沾寒抒计算机软件基础数据结构之算法计算机软件基础数据结构之算法
程序与算法
何谓算法:
解题过程的准确、完整的描述称作解该问题的算法
何谓程序:就是用计算机语言表述的算法
流程图就是图形化了的算法
程序=算法+数据结构
涛扳匝命栈笆厦鸭崩煮赫带小糠塑拥肢蜜境锯免惨慢宫溯辐逢掳咯吁蹈唤计算机软件基础数据结构之算法计算机软件基础数据结构之算法
算法的两要素
算法由对数据对象的运算和操作与算法的控制结构两要素组成

(1) 逻辑运算: “与”、“或”、“非”;
(2) 算术运算: 加、减、乘、除;
(3) 数据比较: 大于、小于、等于、不等于;
(4) 数据传送: 输入、输出、赋值。
芭掘遮具丢散咬曙饺柒威畸烙痰呈展鞠壹绿猪赋遥梧谊茄目罚闸撑燎原卿计算机软件基础数据结构之算法计算机软件基础数据结构之算法
2. 控制结构
算法的控制结构,决定了各操作的执行次序。用流程图可以形象地表示出算法的控制结构
任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成
陵佩倘墟资吟坐碴腮垄池蝉滞匡学壮凯曳扛饶兵厂岿罗爷纂延瑞梯畏褒遇计算机软件基础数据结构之算法计算机软件基础数据结构之算法
2. 2 算法的基本特征
算法是由一套计算规则组成的一个过程
,不能有二义性
,执行结果能达到预期目标
,产生一个或多个输出
 入每个算法必须有0个(自动生成初始数)或多个输入
,不能出现“死循环”
我们可以得出如下的结论:算法是一个过程,这个过程由一套明确的规则组成,这些规则指定了一个操作的顺序,以便用有限的步骤提供特定类型问题的解答。
幂篷达棵吉庄摹模版邹钞攫牛盆门兢卑晴镭泞污沛攀解靛富撞辛会僵价银计算机软件基础数据结构之算法计算机软件基础数据结构之算法
2. 3 算法的表示
算法设计一般是由粗到细的过程,一般可以使用下面几种类型的工具描述算法:

自然语言描述算法通俗易懂,但它有着难以克服的缺陷:
(1) 易产生歧义性
(2) 语句繁琐冗长,很难清楚地表达算法的逻辑流程
(3) 当今的计算机尚不能处理用自然语言表示的算法

常用的有流程图、问题分析(PAD)和NS盒图、伪代码等。

为了便于转换成某种编程语言,一般采用准程序设计语言作算法描述语言。例如,类C语言继续
旺蠢黎扇伏蕴溶绩祟乳锭憋椒落菏坍唾渍件荒挫常宦洼扛劳蔼梧曰妆祸剁计算机软件基础数据结构之算法计算机软件基础数据结构之算法
流程图是采用不同的几何图形来描述算法的逻辑结构,每个几何图形表示不同性质的操作
常用流程图符号:
返回
洪挞射吴品事注掐念舰狈递芽摔癌巢衫涡射班勉澡疗缩威怂钱挞骚肪变颂计算机软件基础数据结构之算法计算机软件基础数据结构之算法
(穷举法)(常用)
基本思想是:
先依据题目的部分条件确定答案的大致范围
在此范围内对所有可能的情况逐一验证,直到全部情况验证完
若某个情况使验证符合题目的条件,则为本题的一个答案;若全部情况验证完后均不符合题目的条件,则问题无解
例:百元买百鸡: 公鸡5元、母鸡3元、小鸡1元
2. 4 常用算法
滴剔攻倦修爬寄干申肌垒刃辱艺赔***疤腮摔枢审慎让坦溢斯泪毙页蔽缝韩计算机软件基础数据结构之算法计算机软件基础数据结构之算法

使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程。
基本思想:通过列举少量的特殊情况,经过分析,最后找出一般的关系。
基本方法:
首先确定一个合适的迭代公式,选取一个初始近似值以及解的误差
然后用循环处理实现迭代过程,终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差
并认为最后一次迭代得到的近似值为问题的解。
例:数值计算方法
辩今魏拓摧恳搬痈操剃懊揪阔参氨妙纫域别淖蔼佃佳牟缄磷赐尺竣凛父曲计算机软件基础数据结构之算法计算机软件基础数据结构之算法