c程序设计 谭浩强 第02章课件.ppt

2.1　算法的概念 2.3　算法的特性 2.4　怎样表示一个算法 2.5　结构化程序设计方法 一个程序应包括以下两方面内容: (1) 对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构(data structure)。 (2) 对操作的描述。即操作步骤， 也就是算法(algorithm)。 数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。作为程序设计人员，必须认真考虑和设计数据结构和操作步骤(即算法)。因此，Pascal之父沃思(Nikiklaus Wirth)提出一个公式: 数据结构 + 算法 = 程序 实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示： 程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境 也就是说，以上4个方面是一个程序设计人员所应具备的知识。在设计一个程序时要综合运用这几方面的知识。 在这4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。显然，不了解算法就谈不上程序设计。 2.1 算 法 的 概 念 问题一：有两个杯子A和B，分别放有酒精和纯净水，试着将两个杯子中的液体进行互换。 问题二：有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有被吃掉的危险。请找出一种安全的渡河方案。 ①两个野人先过河，一个野人回来； ②再两个野人过河，一个野人回来； ③两个牧师过河，一个野人和一个牧师回来； ④两个牧师过河，一个野人回来； ⑤两个野人过河，一个野人回来； ⑥两个野人过河。 算法是指为解决一个问题而采取的方法和步骤。算法并不是问题的结果，而是解题的过程和策略。 又例：对有序表关键字序列{5，10，19，21，31，37，42，48，50，52}，查找k为50的记录。 解一：顺序查找，从第1个元素到最后1个元素，逐个进行比较，直至找到为止。共比较9次 解二：折半查找，算法步骤：step1 首先确定整个查找区间的中间位置，mid = （ left + right ）/ 2；step2 用待查关键字值与中间位置的关键字值进行比较：若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。Step3 对确定的缩小区域再按二分公式，重复上述步骤；最后? 得到结果：要么，查找成功，要么，查找失败。 上例共比较3次 对同一个问题，可以有不同的解题方法和步骤，即不同算法。 如何判断一个算法（程序）的优劣？时空复杂度（时间复杂度、空间复杂度）。 一般来说，希望采用简单的和运算步骤少的方法。 如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是正确的。 因此 ，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。 计算机算法可分为两类： 数值算法: 数值运算的目的是求数值解，如求方根、求定积分等。研究深入，算法成熟，“数学程序库”。 非数值算法: 最常见的是用于事务管理领域，如排序和检索（查找）。参考已有类似算法，重新设计。 时间复杂度的转换 时间复杂度 运行算法所需要的时间 以语句的执行次数来代替时间 以语句执行次数的数量值来代替执行的次数(通常用数量级来表示) 2.3 算法的特性 1.有穷性 一个算法应包含有限的操作步骤，而不能是无限的。一个算法必须保证执行有限步之后结束； 2.确定性 算法的每一步骤必须有确切的定义； 3.有零个或多个输入 所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。 4. 有一个或多个输出 算法的目的是为了求解，“解” 就是输出。没有输出的算法是没有意义的。 5. 有效性 算法中的每一个步骤都应当能有效地执行，并得到确定的结果。 2.4 怎样表示一个算法 常用的有自然语言、传统流程图、结构化流程图、伪代码、PAD图等。 2.4.1 用自然语言表示算法 通俗易懂，但文字冗长， 容易出现“歧义性”。自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。 此外，用自然语言描述包含分支和循环的算法，不很方便。 因此，除了很简单的问题以外，一般不用自然语言描述算法。 2.4.2 用流程图表示算法 流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。美国国家标准化协会ANSI(Ameri