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

2.1 算法的概念 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法,第2章 程序的灵魂算法,一个程序应包括以下两方面内容: (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(American National Standard Institute)规定了一些常用的流程图符号(见图2.3)。 图2.3中菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立来决定如何执行其后的哪一个操作。它有一个入口，两个出口。见图2.4。 连接点(小圆圈)是用于将画在不同地方的流程线连接起来。如图2.5中有两个以为标志的连接点，它表示这两个点是互相连接在一起的, 实际上它们是同一个点。用连接点，可以避免流程线的交叉或过长，使流程图清晰。,图 2.3,图 2.4 图 2.5,需要提醒的是流程线不要忘记画箭头，因为它是反映流程的执行先后次序的。 用流程图表示算法直观形象，比较清楚地显示出各个框之间的逻辑关系。 但是占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不方便。 在结构化程序设计方法推广之后，许多书刊已用 N-S结构化流程图代替这种传统的流程图。但是每一个程序编制人员都应当熟练掌握传统流程图。,2.4.3 三种基本结构和改进的流程图 1. 传统流程图的弊端 传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律。这种情况如图2.13所示。 这种算法难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。如果我们写出的算法能限制流程的无规律任意转向，阅读起来就很方便。,图2.13,为了解决这个问题，人们设想，规定出几种基本结构，然后按一定规律将各个基本结构顺序排列起来组成一个算法结构(如同用一些基本预制构件来搭成房屋一样) 。,2. 三种基本结构 1966年，Bohra和Jacopini提出了以下三种基本结构，作为表示一个良好算法的基本单元。 (1) 顺序结构，如图2.14所示。 (2) 选择结构，或称分支结构，如图2.15、 2.16所示。,图2.14,(3) 循环结构。有两类循环结构： 当型(While型)循环结构 见图2.17(a)。它的功能是先判断给定的条件p1，成立时，再执行A框操作，执行完A后，再判断条件p1是否成立，如果仍然成立，再执行A框，如此反复执行A框，直到某一次p1条件不成立为止，此时不执行A框，而从b点脱离循环结构。 直到型(Until型)循环 见图2.17(b)。它的功能是先执行A框，然后判断给定的p2条件是否成立，如果p2条件不成立，则再执行A，然后再对p2条件作判断，如果p2条件仍然不成立，又执行A如此反复执行A，直到给定的p2条件成立为止，此时不再执行A，从b点脱离本循环结构。,图2.18是当型循环 图2.19是直到型循环 图2.17 图2.18 图2.19,2.4.4 用N-S流程图表示算法 1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。 全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称N-S结构化流程图。 这种流程图适于结构化程序设计，因而很受欢迎。,N-S流程图用以下的流程图符号： (1) 顺序结构: 用图2.24形式表示。 (2) 选择结构：用图2.25表示。 图2.24 图2.25,(3) 循环结构： 当型循环结构用图2.26形式表示。 图2.26表示当p1条件成立时反复执行A操作，直到p1条件不成立为止。 直到型循环结构用图2.27形式表示。 用以上3种N-S流程图中的基本框，可以组成复杂的N-S流程图，以表示算法。,当型循环结构,直到型循环结构,可以看出用N-S图表示算法的优点。 它比文字描述直观、形象、 易于理解； 比传统流程图紧凑易画，尤其是它废除了流程线； N-S流程图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。写算法和看算法只需从上到下进行就可以了，十分方便。 用N-S图表示的算法都是结构化的算法(不可能出现流程无规律的跳转)。,归纳起来可知，一个结构化的算法是由一些基本结构顺序组成的；每个基本结构又可以包含其他的基本结构；在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转)； 一个非结构化的算法(如图2.12)可以用一个等价的结构化算法(如图2.35)代替，其功能不变。 如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。 N-S图如同一个多层的盒子，又称盒图(box diagram)。,2.4.5 用伪代码表示算法 用传统的流程图和N-S图表示算法，直观易懂，但画起来比较费事。 为了设计算法时方便，常用一种称为伪代码(pseudo code)的工具。 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它不用图形符号，因此书写方便 、格式紧凑，也比较好懂，便于向计算机语言算法(即程序)过渡。 例如， “打印x的绝对值”的算法可以用伪代码表示如下：,IF x is positive THEN print x ELSE print x 也可以用汉字伪代码，如： 若 x为正 打印 x 否则 打印 x 也可以中英文混用，如： IF x 为正 print x ELSE print x,用伪代码写算法并无固定的、严格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。,伪代码的特点： 伪代码书写格式比较自由，容易表达出设计者的思想。 同时，用伪代码写的算法很容易修改。 用伪代码很容易写出结构化的算法。 但是用伪代码写算法不如流程图直观，可能会出现逻辑上的错误。 软件专业人员一般习惯使用伪代码，为便于理解，本书在以后各章中主要采用形象化的N-S图表示算法。,2.4.6 用计算机语言表示算法 要完成一件工作，包括设计算法和实现算法两个部分。 在用流程图或伪代码描述出一个算法后，还要将它转换成计算机语言程序，才能编译执行。,2.5 结构化程序设计方法（STRUCTURED PROGRAMING，简称SP） SP方法主张使用顺序、选择、循环三种基本结构来嵌套连结成具有复杂层次的“结构化程序” 。 SP方法是面向过程的设计方法。 面向对象的程序设计 (ObjectOrient Programming，OOP) 结构化程序设计方法的基本思路是，把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。,结构化程序设计的步骤：(1) 自顶向下；(2) 逐步细化；(3) 模块化设计；(4) 结构化编码。 在接受一个任务后应怎样着手进行呢?有两种不同的方法： 一种是自顶向下，逐步细化； 一种是自下而上，逐步积累。 以写文章为例。如图2.36示意。,图2.36,显然，采用“自顶向下， 逐步细化” 的方法 考虑周全，结构清晰，层次分明； 如果发现有需要修改的部分，只需相关段落即可，与其他部分无关。 我们提倡用这种方法设计程序，即用工程的方法设计程序。,在程序设计中常采用模块设计的方法，尤其是当程序比较复杂时，更有必要。 模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个相对简单的子任务，或根据功能将复杂的大模块划分为若干个子模块。这个过程采用自顶向下的方法来实现。 模块的根本特征是“相对独立，功能单一”。,模块的好坏，通常用“耦合度”和“内聚度”两个指标从不同侧面而加以度量。 所谓耦合度，是指模块之间相互依赖性大小的度量，耦合度越小，模块的相对独立性越大。 所谓内聚度，是指模块内各成