[IT认证]第02章_算法.ppt

《[IT认证]第02章_算法.ppt》由会员分享，可在线阅读，更多相关《[IT认证]第02章_算法.ppt（41页珍藏版）》请在三一文库上搜索。

1、,第二章,算 法,主要内容,2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法,2019/1/29,引入: 一个程序应包括两个方面的内容:,对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm),著名计算机科学家沃思提出一个公式: 数据结构 + 算法 = 程序,数据结构算法程序设计方法语言工具,完整的程序设计应该是:,2019/1/29,2.1 算法的概念,广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。,方法1：1+2，+3，+4，一直加到100 加99次 方法2：100+(

2、1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50 加51次,对同一个问题，可有不同的解题方法和步骤,例： 求,2019/1/29,2.1 算法的概念,为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。,计算机算法可分为两大类别： 数值运算：求数值解，例如求方程的根、求函数的定积分等。 非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。,2019/1/29,2.2 简单算法举例,例2.1: 求12345,步骤1：先求12，得到结果2 步骤2：将步骤1得到的乘积

3、2再乘以3，得到结果6 步骤3：将6再乘以4，得24 步骤4：将24再乘以5，得120,太繁琐,如果要求121000，则要写999个步骤,2019/1/29,S1：1 p S2：3 i S3：pi p S4：i+2 p S5：若i11，返回S3。否则，结束。,如果题目改为：求13511算法只需作很少的改动：,算法简练,2019/1/29,用这种方法表示的算法具有通用性、灵活性。 S3到S5组成一个循环，在实现算法时 要反复 执行S3，S4，S5等步骤，直到某一时刻。 执行S5步骤时经过判断，乘数i已超过规定的数值而不返回S3步骤为止。此时算法结束，变量p的值就是所求结果。,S1：1 p S2：

4、3 i S3：pi p S4：i+2 p S5：若i11，返回S3。否则，结束。,2019/1/29,例2.2:输入三个数，然后输出其中最大的数。 分析：将三个数依次输入到变量、B、C中 设变量MAX存放最大数。 其算法如下： 1) 输入A、B、C。 2) A与B中大的一个放入MAX中。 3) 把C与MAX中大的一个放入MAX中。 4) 输出MAX，MAX即为最大数。,2019/1/29,例2.3 输入10个数，打印输出其中最大的数。 算法设计如下： （1）输入1个数,存入变量A中,将记录数据个数的变量N赋值为1，即N=1 （2）将A存入表示最大值的变量Max中，即Max=A （3）再输入一个

5、值给A，如果AMax 则 Max=A, 否则Max不变 （4）让记录数据个数的变量增加1，即N=N+1 （5）判断N是否小于10，若成立则转到第（3）步执行，否则转到第（6）步。 （6）打印输出max,2019/1/29,2.3 算法的特性,有穷性：包含有限的操作步骤 确定性：算法中的每一个步骤都应当是确定的 有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息 有一个或多个输出：算法的目的是为了求解，“解” 就是输出 有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果 。,一个算法应该具有以下特点：,2019/1/29,2.4 算法的表示,可以用不同的方法表示算法: 自

6、然语言 传统流程图 流程图 伪代码,2019/1/29,1) 用自然语言表示算法,自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。 用自然语言表示通俗易懂，但文字冗长，容易出现“歧义性”。 自然语言表示的含义往往不大严格，要根据上下文才能判断其正确含义，描述包含分支和循环的算法时也不很方便。因此，除了那些很简单的问题外，一般不用自然语言描述算法。,2019/1/29,) 用流程图表示算法,美国国家标准化协会 ANSI(American National Standard Institute)规定了一些常用的流程图符号：,2019/1/29,例： 从10个数中选出最大的数的流程图,N

7、10,Max =A N=1,AMax,Max =A,输入A,开始,再输入给A,N=N+1,打印Max,结束,Y,N,N,Y,2019/1/29,小结：,流程图是表示算法的较好的工具。一个流程图包括以下几部分 ： (1)表示相应操作的框； (2)带箭头的流程线； (3)框内外必要的文字说明。,2019/1/29,三种基本结构 Bohra和Jacopini提出了以下三种基本结构： 顺序结构、选择结构、循环结构 用这三种基本结构作为表示一个良好算法的基本单元。,2019/1/29,三种基本结构的图示：,顺序结构,选择结构,2019/1/29,循环结构的图示：,当型(While型)循环结构,直到型(U

8、ntil型)循环,2019/1/29,三种基本结构的共同特点： (1)只有一个入口； (2)只有一个出口；（请注意：一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。） (3)结构内的每一部分都有机会被执行到； (4)结构内不存在“死循环”(无终止的循环)。,2019/1/29,小结：,由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。,2019/1/29,) 用N-S流程图表示算法,1973年美国学者I.Nassi和B.Shn

9、eiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其它的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称N-S结构化流程图 。,2019/1/29,N-S流程图用以下的流程图符号：,(1)顺序结构,(2)选择结构,(3)循环结构,2019/1/29,用三种N-S流程图中的基本框，可以组成复杂的N-S流程图。图中的A框或B框，可以是一个简单的操作，也可以是三个基本结构之一。,A框是一个选择结构,B框是一个循环结构,2019/1/29,传统流程图,N10,Max =A N=1,AMax,Max =A,输

10、入A,开始,再输入给A,N=N+1,打印Max,结束,Y,N,N,Y,输入A,当N=10,Max =A,N=N+1,打印Max,输入A,NS流程图,A=Max,Y,N,2019/1/29,N-S图表示算法的优点,比文字描述直观、形象、 易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N-S流程图中的上下顺序就是执行时的顺序。用N-S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。,2019/1/29,）用伪代码表示算法,概念：伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。 特点：它如同一篇

11、文章一样 ，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便 、格式紧凑，也比较好懂，也便于向计算机语言算法(即程序)过渡。 用处：适用于设计过程中需要反复修改时的流程描述。,2019/1/29,例如：例2.2可用如下的伪代码表示 Begin（算法开始） 输入 A，B，C IF AB 则 AMax 否则 BMax IF CMax 则 CMax Print Max End (算法结束),2019/1/29,IF x is positive THEN print x ELSE print -x 也可以用汉字伪代码表示： 若 x为正 打印 x 否则 打印 -x 也可以

12、中英文混用，如： IF x 为正 print x ELSE print -x,例： “打印x的绝对值” 算法可以用伪代码 表示为：,2019/1/29,5)用计算机语言表示算法,概念：用计算机实现算法。计算机是无法识别流程图和伪代码的。只有用计算机语言编写的程序才能被计算机执行。因此在用流程图或伪代码描述出一个算法后，还要将它转换成计算机语言程序。 特点：用计算机语言表示算法必须严格遵循所用的语言的语法规则，这是和伪代码不同的。 用处：要完成一件工作，包括设计算法和实现算法两个部分。设计算法的目的是为了实现算法。,2019/1/29,应当强调说明：写出了C程序，仍然只是描述了算法，并未实现算法

13、。只有运行程序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。,用计算机解决问题的过程,2019/1/29,main() int x; scanf(“%f”, ,例： “打印x的绝对值”的算法可以用语言表示为：,2019/1/29,2.5 结构化程序设计方法,一个结构化程序 就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。 结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。 结构化程序设计方法的基本思路是：把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理

14、的范围内。,2019/1/29,2.5 结构化程序设计方法,采取以下方法来保证得到结构化的程序： 自顶向下； 逐步细化； 模块化设计； 结构化编码。,两种不同的方法： 自顶向下，逐步细化； 自下而上，逐步积累。,2019/1/29,用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。,2019/1/29,S1,NS流程图,S3,S2,例：给100个整数，打印输出其中的素数,2019/1/29,S1,NS流程图,S3,S2,S21,2019/1/29,细化后的流程图,2019/1/29,自顶向下，逐步细化方法的优点： 考虑周全，结构清晰，层

15、次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。,2019/1/29,模块设计的方法： 模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。 在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。 子模块一般不超过50行 划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。,2019/1/29,“算法”是指通过编程解决问题的方法和步骤。它是程序设计的灵魂它包含所采用的数据类型、控制结构以及输入输出方式等。解决同一个问题一般有多种算法。 评价算法优劣主要从三个方面考虑： (1)代码复杂度，指的是程序代码是否精简易读，逻辑是否清晰； (2)空间复杂度，是指程序中变量、数组等占用内存资源的大小； (3)时间复杂度，是指程序运行所需时间。多数情况下，这三个 方面是相互矛盾的，应根据具体需要进行折衷处理。 有经验的程序员可以设计出代码小、效率高、占用系统资源少、便于理解、易于调试的算法。而初学者则需要经过一定的训练、不断的实践才能达到这样的水平。,关于算法,