2016-第1章.ppt

问题：什么是算法（algorithm）？ 从一个通俗简单的例子谈起。 解一个小学四则运算式：5+(7-1)÷3 = ? 大家知道,运算规则是： （1）先计算括号里面的式子，再计算括号外面的式子 我们得到式子：5+6÷3 = ？ （2）先乘除，后加减 我们得到式子：5+2 = ？，再得到：5+2=7 结果为： 5+(7-1)÷3 = 7 我们概括上述计算过程，那么什么是算法？ 第1讲 算法概述 √算法定义 算法（algorithm）就是解决特定问题时，按照某种机械步骤一定可以 得到问题结果的处理过程。当问题有解时，给出问题的结果，无解时给 出无解的结论。 √计算机算法（简单概念）： 算法（algorithm）是计算机解决问题的过程。 第1讲 算法概述 例如：计算机求解5+(7-1)÷3 = ? 的过程可以描述为： x1=7-1 x2=x1/3 x3=5+x2 print y 问题输入 有解 算法 无解 给出结果 无解结论 √计算机算法定义（严格定义） 算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序 列。一个算法具有下列重要特征： （1）有穷性：一个算法必须在执行有穷步之后结束，即构成算法的步骤是 有限的，且每一步都可在有穷时间内完成。 （2）确定性：算法中每一条指令必须有确切的含义，并且，在任何条 件下，算法只有唯一的一条执行路径，即对于相同的输 入只能有相同的输出。 （3）可行性：算法中描述的操作都是可以通过已经实现的基本运算执 行有限次来实现的。 （4）输入：算法有0个或多个输入 （5）输出：算法有1个或多个输出 第1讲 算法概述 √ 算法3要素：操作(运算)，控制结构(规则)，数据结构 （1）操作 算数运算：+，-,*,/,^ 关系运算：,,=,=, =, ≠ 逻辑运算：and, or, not,…… 数据传送：输入，输出，赋值,…… （2)控制结构 算法的控制结构给出了算法的框架，决定了操作步骤之间的逻辑次序. 共三种结构：顺序结构， 分支结构（选择），循环结构 第1讲 算法概述 （3）数据结构 算法操作的对象是数据，数据之间的逻辑关系、存贮方式和处理 方式就是数据的结构。 √算法的基本性质 目的性， 分步性（多步性），有序性，有限性（步骤有限） 操作性（对对象执行操作） √算法的基本特征 有穷性（步骤个数和执行时间有限），确定性（算法在任何情况下只有 一条执行路径）， 可行性(通过基本操作能完成算法描述的所有操作)，算法 有0个或多个输入，1个或多个输出。 第1讲 算法概述 √算法设计基本方法 结构化方法 面向对象方法 √算法设计需要考虑的几个方面 （1）正确性（Correctness) （2）时间效率: 算法执行时间 （3）空间效率: 算法执行过程中所需的最大存储空间 第1讲 算法概述 （4）可读性(Readability) （5）健壮性(Robustness 最重要或优先考虑 √算法描述方法 自然语言描述方法 流程图方法 盒图方法 PAD图方法 伪代码方法 程序设计语言方法 为了学习算法分析方法，本课程教学中我们采用伪代码方法 第1讲 算法概述 √算法实现的软件工具 【数值计算软件】： matlab mathematics,maple,…… 【运筹学（规划算法）】： lingo,lindo,…… 【统计分析】： SAS,SPSS 【网络有哪些信誉好的足球投注网站引擎】 【程序设计语言】C语言，VB语言，…… 第1讲 算法概述 √算法设计的重要性 一些有趣的例子：对计算机人来说， 例1. 问题能解决吗？ 假设某一负责人交给你一个很难的任务，几天后询问你问题解决了没有。可能 会发生如下图这样的情况： 问：“交给你的问题，解 决方案设计出来了吗？” 答：“我找不到一个有效 的算法来解决它，没能 完成任务。” 第1讲 算法设计 问：“交给你的问题，解决方案设计出来了吗？