第2章 程序的灵魂－算法.pptVIP

第二章 程序的灵魂－算法 第二章 程序的灵魂－算法 著名计算机科学家沃思提出一个公式： 程序 = 数据结构 + 算法 由于采用结构化方法进行程设, 且用某一种计算机语言表示,因此还可表示为： 程序=数据结构+算法+程序设计方法 +语言工具和环境 算法:是灵魂，是解决“做什么”、“怎么做” 数据结构：是加工对象 程序设计方法：程序应当采用的结构化程序设计方法 语言：是工具。 2.1 算法的概念 1. 算法：为解决一个问题而采取的方法及步骤，就 称为一个算法。 对于同一问题有不同的解题 的方法。例如：求1+2+3+…+100。为了有效进行解题,不仅确保算法正确,还应考虑算法的质量,即选择合适的算法 2. 算法的分类： 数值算法, 非数值算法 1)数值算法：目的是求数值解，(例如:求方程的根,函数定积分等)算法成熟，把算法汇编成册存放在磁盘上,供用户调用.(如：数学程序库) 2)非数值算法：用于事物管理领域，(如:图书检索,人事管理)种类繁多，要求各异，难以规范化。 2．2 简单算法举例 例2.1：求1*2*3*4*5 方法一： 步骤1：先求1*2，得到结果2。 步骤2：将步骤1得到的乘积2再乘以3，得到结果6。 步骤3：将步骤2得到的乘积6再乘以4，得到结果24。 步骤4：将步骤3得到的乘积24再乘以5，得到最后结果120。 2．2 简单算法举例（续） 方法二： 步骤1：设P=1（P为乘数）。 步骤2：设I=2（I为被乘数）。 步骤3：使P*I，乘积仍放在变量P中，可表示为P=P*I。 步骤4：使I的值加1，可表示为I=I+1 。 步骤5：判断：如果I不大于5，返回重新执行步骤3、4、5； 否则算法结束。最后求得的P的值就是5！的值。 2．2 简单算法举例（续） 例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来．用n表示学生学号,n1代表第一个学生学号, ni代表第i个学生的学号,g代表学生成绩, gi代表第i个学生成绩． 算法如下： S1: 1=i S2: 若gi≥80则打印ni 和gi ，否则不打印 S3: i+1=i S4: 若i≤50返回s2，否则算法结束 2．3 算法的特性 （1）有穷性：一个算法应包含有限的操作步骤，而不能是无限的 （2）确定性：算法中每一步的操作步骤都是确定的，不能模棱两可 （3）有零个或多个输入：在执行算法时从外界取的必要的信息 (4）有一个或多个输出：即算法的求解 (5）有效性：算法中每一个步骤都应当能有效执行 2.4 怎样表示一个算法 2.4.1 用自然语言表示算法 算法可以用自然语言描述的。自然语言就是人们日常使用的语言，可以是汉语、英语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现歧义。自然语言表示的含义往往不太严格，要根据上下文才能准确判断其含义。此外，用自然语言描述分支和循环的算法，不是很直观。因此，除了简单问题，一般不采用自然语言描述算法。 2.4.2 用流程图表示算法 用流程图表示：流程图是一种传统的算法表示法，它利用特定的几何图形框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它简单直观，所以应用广泛。 2.4.2 用流程图表示算法 美国标准化协会ANSI规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用 一、举例 例1： 求5!，其算法 流程图如右 所示。 例2： 将50名学 生中成绩 在80分以 上的学生 的学号及 成绩打印 出来。 2.4.3 三种基本结构 和改进的流程图 1. 传统流程图的弊端 传统流程图采用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程转来转去，使流程图变得毫无规律。 三种基本结构：人们对传统流程图进行改进，规定几种基本的结构，然后由这些基本结构按一定规律组成算法结构，整个算法结构是由上而下地将各个基本结构顺序排列起来 1)顺序结构：是最简单的一种基本结构，如右图所示。 2)选择结构： 根据给定的条件p选择执行A或者B。 3)循环结构 (1)当型(while)循环结构 (2)直到型(Until)循环 3. 三种基本结构的共同特点 1)只有一个入口 2)只有一个出口 3)结构内的每一个部分都有机会被执行 4)结构内不存在“死循环” 已经证明，任何复杂的问题都可以通过由以上三种基本结构顺序组成的算法结构来解决。 2.4.4 用N-S流程图表示算法 将全部算法写在一个矩形框内，在矩形内还可包含其它从属于它的框N和S是两位美国学者的英文名的第一个字母 N-S流程图用以下符号表示： N-S图的使用特点: 1、比文字描述更加直观、形象，易于理解； 2、比传统的流程