第1章 算法与程序课件.pptVIP

算法与数据结构 第1章 算法与程序 第1章 算法与程序 1.1 算法的基本概念 1.1.1 什么是算法 1.1.2 算法的基本特性 什么是算法 早在公元前300年左右出现的著名的欧几里德算法，就描述了求解两个整数的最大公因子的解题步骤。要求解的问题描述为：“给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大整数”。欧几里德当时给出的算法如下： ⑴ 以n除m，并令所得余数为r（必有rn）； ⑵ 若r=0，输出结果n，算法结束；否则继续步骤⑶； ⑶ 令m=n和n=r，返回步骤⑴继续进行。 什么是算法（续） 由此，我们可以得出这样的结论，算法就是求解问题的方法和步骤。这里的方法和步骤是一组严格定义了运算顺序的规则；每一个规则都是有效的，且是明确的；按此顺序将在有限次数下终止。 有关算法（Algorithm）一词的定义不少，但其内涵基本上是一致的。最为著名的定义是计算机科学家D.E.Kunth在其巨著《计算机程序的艺术》（ Art of Computer Program）第一卷中所做的有关描述。其非形式化的定义是： 一个算法，就是一个有穷规则的集合，其中之规则定义了一个解决某一特定类型问题的运算序列。 什么是算法（续） 算法的形式化定义如下所述： 算法是一个四元组，即（Q，I，Ω，F）。 其中： Q是一个包含子集I和Ω的集合，它表示计算的状态； I表示计算的输入集合； Ω表示计算的输出集合； F表示计算的规则，它是由Q至它自身的函数，且具有自反性，即对任何一个元素q∈ Q，有F(q)=q。 什么是算法（续） 一个算法是对于任何的输入元素x，都在有穷步骤内终止的一个计算方法。 在算法的形式化定义中，对任何一个元素x∈I，x均满足性质 x0=x，xk+1=F(xk)，（k≥0） 该性质表示任何一个输入元素x均为一个计算序列，即x0，x1，x2，…，xk；该序列在第k步结束计算。 1.1 算法的基本概念 1.1.1 什么是算法 1.1.2 算法的基本特性 算法的基本特性 输入（Input） 输出（Output） 确定性（Definiteness） 有穷性（Finiteness） 有效性（Effectiveness） 第1章 算法与程序 1.1 算法的基本概念 1.2 算法的表示 1.3 算法的设计与评价 1.4 算法与程序 1.2 算法的表示 1.2.1 自然语言表示 1.2.2 流程图表示 1.2.3 N—S图表示 1.2.4 伪代码表示 1.2.5 程序语言表示 自然语言表示 自然语言即人们日常使用的语言，如汉语、英语、日语、法语、德语等等。使用自然语言描述算法，人们比较容易接受和理解。如前面的欧几里德算法就是用自然语言描述的。然而，自然语言也具有许多缺点，在使用自然语言描述算法时一定要引起注意： 自然语言存在着歧义性，容易导致算法的不确定性； 自然语言容易冗长，使得描述不够简洁； 自然语言的表示形式是顺序的，描述分支选择和转移时不够直观； 自然语言与计算机程序设计语言的差别较大，不易转换为程序。 1.2 算法的表示 1.2.1 自然语言表示 1.2.2 流程图表示 1.2.3 N—S图表示 1.2.4 伪代码表示 1.2.5 程序语言表示 流程图表示 流程图是描述算法的图形工具，它采用如下所示的一组图形符号来表示算法： 流程图表示举例 欧几里德算法的流程图描述如图1-1所示 流程图表示（续） 同自然语言相比，用流程图描述算法直观，可以一目了然；算法步骤间用流程线连接，次序关系清楚，容易理解；可以很方便地表示顺序、选择和循环结构，不依赖于任何计算机和计算机程序设计语言，有利于不同环境下的程序设计。但是，流程图也还存在一些缺点，诸如： 不易于表示算法的层次结构； 不易于表示数据结构和模块调用关系等重要信息； 容易使人过早地考虑算法的控制流程，而忽视算法的全局结构； 用流程线代表控制流，控制转移随意性较大。若对流程线的使用不加限制，随着求解问题规模和复杂度的增加，流程图会变得很复杂，使人难以阅读、理解和修改，从而使算法的可靠性难以保证。 1.2 算法的表示 1.2.1 自然语言表示 1.2.2 流程图表示 1.2.3 N—S图表示 1.2.4 伪代码表示 1.2.5 程序语言表示 N—S图表示 为了克服传统流程图的缺点，1973年美国学者纳斯（I.Nassi）和施内德曼（B.Shneiderman）提出了一种表示算法的较好工具——N-S图。 它独立于任何计算机和计算机语言，又能很方便地转换为