[工学]2-1_算法.ppt

Chapter 2 程序的灵魂---算法 邢岳林 SDU_ISE Agenda 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 化程序设计方法 什么是程序? 一个程序应该包含： 对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm) 什么是算法? 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。 对同一个问题，可有不同的解题方法和步骤 例： 求 方法1：1+2，+3，+4，一直加到100 加99次 方法2：100+(1+99)+(2+98)+…+(49 +51)+50 = 100 + 49×100 +50 加51次 什么是算法? 为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。 计算机算法可分为两大类别： 数值运算算法：求数值解，例如求方程的根、求函数的定积分等。 非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。 算法举例 算法举例 算法举例 算法举例 算法的特性 有穷性：包含有限的操作步骤。 确定性：算法中的每一个步骤都应当是确定的。 有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息。 有一个或多个输出：算法的目的是为了求解，“解” 就是输出。 有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果 算法的表示 可以用不同的方法表示算法，常用的有： 自然语言 传统流程图 结构化流程图 伪代码 PAD图 算法的表示 自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。 用自然语言表示通俗易懂，但文字冗长，含义不严格，要根据上下文才能判断其正确含义，容易出现“歧义性”。 描述包含分支和循环的算法时也不很方便。 因此，除了那些很简单的问题外，一般不用自然语言描述算法。 算法的表示 用流程图表示算法 ANSI(American National Standard Institute)规定了一些常用的流程图符号： 流程图 例2.6 将求5!的算法 用流程图表示 流程图 例2.7 将例2.2的算法 用流程图表示。 打印50名 学生中成绩 在80分以上者的学号 和成绩。 流程图 流程图是表示算法的较好的工具。一个流程图包括以下几部分 ： (1) 表示相应操作的框； (2) 带箭头的流程线； (3) 框内外必要的文字说明。 流程图 传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以毫不受限制地使流程随意地转向，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。如图： 流程图 三种基本结构 Bohra和Jacopini提出了以下三种基本结构： 顺序结构、选择结构、循环结构 用这三种基本结构作为表示一个良好算法的基本单元。 流程图 三种基本结构 流程图 三种基本结构 流程图 三种基本结构的共同特点： (1)只有一个入口。 (2)只有一个出口。（请注意：一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。） (3)结构内的每一部分都有机会被执行到。 (4)结构内不存在“死循环”(无终止的循环)。 流程图 小结 由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。 N-S流程图 1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其它的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称N--S结构化流程图。 N-S流程图 N-S流程图用以下的流程图符号： N-S流程图 例2.11 将例2.1的求5!算法用N-S图表示 N-S流程图 例2.12 将例2.2的算法用N-S图表示。（打印50名学生中成绩高于80分的学号和成绩） N-S流程图 N--S流程图的优点 比文字描述直观、形象、 易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N--S流程图中的上下顺序就是执行时的顺序。用N--S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。 结构化的算法 一个结构化的算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一