软件技术基础第02章课件.ppt

《软件技术基础第02章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章算法理论2.1算法的基本概念2.2算法的基本特征2.3算法的基本要素2.4算法描述*2.5算法的设计2.6算法评价2.7一个完整的算法表示2.8几点说明1计算机软件的主体是程序与数据，而它们的理论支撑分别是算法理论与数据理论，其中数据理论又可分为数据基础与数据结构两部分基础算法理论数据理论数据基础数据结构针对程序针对数据2算法和数据结构是计算机科学的核心尼克劳斯.沃思（Niklaus.Wirth）指出：程序=算法+数据结构本章重点讨论算法，接下两章讨论数据及数据结构32.1算法的基本概念1、算法的定义算法是一类问

2、题的一种求解方法，该方法可用一组有序的计算步骤或过程表示计算机算法即指导计算机执行的算法，只有给出算法后计算机才能（按算法）执行尼克劳斯.沃思指出“计算机科学就是研究算法的学问”。因此，目前算法已成为计算机学科与软件的核心理论42.1算法的基本概念例：abc三个数中有两个相等，求其中不等的那个数算法输入：3个数a、b、c算法输出：3个数中不相等的那个数算法过程：1)比较a与b，若a=b则不相等的数为c，算法结束；若ab则继续2)比较a与c，若a=c则不相等的数为b，算法结束；否则不相等的数为a，算法结束52.1算法的

3、基本概念从上述例子可以看出：(1)算法是一种偷懒的方法。人只要设计算法并将它用计算机所熟悉的语言告诉计算机，计算机即可按算法要求求解并获得结果(2)算法不是程序，算法高于程序。算法给出计算的宏观步骤与过程，不给出程序中一些微观部分的描述。这样有利于对算法作必要讨论和对具体编程指导(3)算法是程序的框架与灵魂，而程序是算法的实现。编写程序时首先设计算法，它给出程序的框架；接着对算法作必要的理论讨论，包括算法正确性及效率；然后根据算法设计程序；最终在计算机上执行获得结果62.1算法的基本概念2、算法的正确性一个算法对每个输

4、入都能输出符合要求的结果并最终停止，则称它是正确的一个算法所给出的输出结果不符合预期要求或算法不会停止，则称它是不正确的正确的算法总是能停止的，因此能否停止是衡量算法正确性的一个重要标志，它称为算法的停机问题，在算法理论研究中有重要作用72.1算法的基本概念3、算法的分析与设计一个好的算法的标准：执行时间短，占用存储小算法分析：时间效率分析，又称时间复杂度分析空间效率分析，又称空间复杂度分析算法设计：为获得一个好的算法，需对它设计，目前有一些常用的成熟设计方案可参考，同时还有一些成熟的设计思想可使用。但真正的设计方案还

5、须由使用者根据具体情况确定82.2算法的基本特征算法的基本特征(1)可行性：算法中的所有计算都是可以实现的(2)确定性：算法的每个步骤都必须明确定义和严格规定，不允许出现多义性(3)有穷性：算法必须在有限个步骤内执行完毕(4)输入：每个算法可以有0~n个数据作为其输入(5)输出：每个算法必须有1~n个数据作为其输出，没有输出的算法相当于“什么都没有做”92.3算法的基本要素1、算法的两个基本要素第一个基本要素：操作、指令或运算等若干个计算单元第二个基本要素：用于控制计算“过程”的一些控制单元102.3算法的基本要素2、

6、算法的操作或运算（为算法基本计算单位）(1)算术运算：加、减、乘、除、指数、对数等(2)逻辑运算：“与”、“或”、“非”、“等价”等(3)比较操作：“大于”、“小于”、“等于”、“大于等于”、“小于等于”、“不等于”等(4)传输操作：“输入”、“输出”、“赋值”等112.3算法的基本要素3、算法的控制（用于控制操作和运算之间的执行顺序）(1)顺序控制：一般情况下操作按算法书写次序执行(2)选择控制：根据判断条件作两选一或多选一的控制(3)循环控制：用于操作(或运算)多次反复执行的控制122.4算法描述算法描述分为形式化

7、、半形式化、非形式化描述1、形式化描述即类语言描述，又称为“伪程序”或“伪代码”类语言：指以某种程序设计语言为主体，以其基本操作和控制为主要架构，但屏蔽其具体实现细节与语法规则的语言。目前常用类语言有类C，类C++等类语言描述的优点：它离真正可执行程序很近，只要对伪程序作一定细化与加工即可成为能执行的“真程序”132.4算法描述类C语言写的算法表示：g(a,b,c){if（a=b）xc；elseif（a=c）xb；elsexa；}142.4算法描述关于类C语言的一些规定1)算术运算：沿用数学中的表示法2)逻辑运算

8、：用and（且）、or（或）、not（非）等表示3)关系运算：用＞、＜、=、≠、≥、≤等表示4)赋值运算：ab5)算法输入：表示为算法的参数g(a,b,c)6)中间输入：read变量1,变量2,…7)算法输出：return表达式8)条件语句：if,if-else9)开关语句：switch10)循环语句：for,while,do-