软件工程 第1章 算法 大字黑体 1版

《软件工程 第1章 算法 大字黑体 1版》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、软件工程第1章算法大字黑体1版本文由insmile001贡献ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。计算机软件技术基础计算机软件技术基础第1章算法第1章算法1.1算法的基本概念1.2算法的表示1.3算法的设计与评价1.1算法的基本概念1.1.1什么是算法1.1.2算法的基本特性什么是算法公元前300年左右出现的著名的年左右出现的著名的公元前欧几里德算法，欧几里德算法，就描述了求解两个整数的最大公因子的解题步骤。数的最大公因子的解题步骤。要求解的问题描述为：给定两个正整数m的问题描述为：“给定两个正整

2、数和n(m>n)，求它们的最大公因子，，求它们的最大公因子，即能同时整除m和的最大整数的最大整数”即能同时整除和n的最大整数”。什么是算法欧几里德当时给出的算法如下：欧几里德当时给出的算法如下：⑴以n除m，并令所得余数为r除，并令所得余数为必有r

3、的方法和步骤。这里的方法和步骤是一组严格定义了运算顺序规则；顺序的定义了运算顺序的规则；每一个规则都是可行可行的且是明确明确的都是可行的，且是明确的；按此顺序将在有限次数下终止。将在有限次数下终止。有限次数下终止算法的定义有关算法（Algorithm）有关算法（Algorithm）一词的定义不少，但其内涵基本上是一致的。不少，但其内涵基本上是一致的。最为著名的定义是计算机科学家DKunth在其名的定义是计算机科学家D.E.Kunth在其巨著《计算机程序的艺术》（ArtofProgram）ComputerProgram）第一卷中所做的有关描述。

4、非形式化的定义是描述。其非形式化的定义是：一个算法，就是一个有穷规则的集合，一个算法，就是一个有穷规则的集合，其中之规则定义了一个解决某一特定类型问题的运算序列。问题的运算序列。数据结构的创始人——克努思克努思数据结构的创始人1938年出生，25岁毕业年出生，岁毕业年出生于加州理工学院数学系，于加州理工学院数学系，博士毕业后留校任教，博士毕业后留校任教，28岁任副教授。30岁时，岁任副教授。岁岁任副教授加盟斯坦福大学计算机任教授。岁起，系，任教授。从31岁起，岁起开始出版他的历史性经典巨著：典巨著：数据结构的创始人——克努思克努思数据结构的创

5、始人TheArtofComputerProgramming他计划共写7卷，然而出他计划共写卷版三卷之后，已震惊世界，版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖此时，图灵奖，最高荣誉图灵奖，此时，他年仅36岁他年仅岁。1.1算法的基本概念1.1.1什么是算法1.1.2算法的基本特性算法的5个基本特性算法的个基本特性1.有穷性：一个算法必须在执行有穷步之后有穷性：一个算法必须在执行有穷步之后有穷性有穷步结束，且每一步都可以在有穷时间内完成。有穷时间内完成结束，且每一步都可以在有穷时间内完成。确定性：2.确定性：一个算法中每一条指

6、令必须有确确定性一个算法中每一条指令必须有确切的含义，不会产生二义性二义性。切的含义，不会产生二义性。3.可行性：一个算法是可行的，即算法中描可行性：可行的可行性一个算法是可行述的操作都可通过已经实现的基本运算执行述的操作都可通过已经实现的基本运算执行有限次来实现。有限次来实现。4.输入：一个算法有零个或多个输入。输入：输入一个算法有零个或多个输入。5.输出：一个算法有一个或多个输出。输出：输出一个算法有一个或多个输出。第1章算法与程序1.11.21.3算法的基本概念算法的表示算法的设计与评价1.2算法的表示1.2.11.2.21.2.31.

7、2.41.2.5自然语言表示流程图表示N—S图表示图表示伪代码表示程序语言表示自然语言表示自然语言即人们日常使用的语言，如汉自然语言即人们日常使用的语言，人们日常使用的语言英语等，人们比较容易接受和理解。语、英语等，人们比较容易接受和理解。前面的欧几里德算法就是用自然语言描述然而，自然语言也有许多缺点：的。然而，自然语言也有许多缺点：存在歧义性存在歧义性冗长，描述不够简洁冗长，描述不够简洁描述分支、选择和循环时不直观描述分支、选择和循环时不直观与程序设计语言的差别大，不易转换与程序设计语言的差别大，1.2算法的表示1.2.11.2.21.2.

8、31.2.41.2.5自然语言表示流程图表示N—S图表示图表示伪代码表示程序语言表示流程图表示流程图是描述算法的图形工具，它采用流程图是描述算法的图形工具，图形工具