第二章-算法---程序的灵魂课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,2,章 算法,-,程序的灵魂,第2章 算法-程序的灵魂,1,一个程序主要包括以下两方面的信息：,(1),对数据的描述,。在程序中要指定用到,哪,些数据以及这些数据的类型和数据的组织形式,这就是数据结构,(data structure),(2),对操作的描述,。即要求计算机进行操作的步骤,也就是算法,(algorithm),一个程序主要包括以下两方面的信息：,2,数据是操作的对象,操作的目的是对数据进行加工处理，以得到期望的结果,著名计算机科学家沃思,(Nikiklaus Wirth),提出一个公式：,算法,+,数据结构,=,程序,数据是操作的对象,3,一个程序除了,算法和数据结构这,主要要素外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示,算法,、,数据结构,、,程序设计方法,和,语言工具,是一个程序设计人员应具备的知识,一个程序除了算法和数据结构这主要要素外，还应当采用结构化程序,4,算法是解决“做什么”和“怎么做”的问题,程序中的操作语句，是算法的体现,不了解算法就谈不上程序设计,算法是解决“做什么”和“怎么做”的问题,5,2.1,什么是算法,2.2,简单的算法举例,2.3,算法的特性,2.4,怎样表示一个算法,2.5,结构化程序设计方法,2.1 什么是算法,6,2.1,什么是算法,广义地说，为解决一个问题而采取的方法和步骤，就称为“,算法,”,对同一个问题，可以有不同的解题方法和步骤,为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法,2.1 什么是算法广义地说，为解决一个问题而采取的方法和步骤,7,2.1,什么是算法,计算机算法可分为两大类别：,数值运算算法,非数值运算算法,数值运算,的目的是求数值解,非数值运算,包括的面十分广泛，最常见的是用于事务管理领域,2.1 什么是算法计算机算法可分为两大类别：,8,2.2,简单的算法举例,例,2.1,求,1,2,3,4,5,可以用最原始的方法进行：,步骤,1,：先求,1*2,，得到结果,2,。,步骤,2,：将步骤,1,得到的乘积,2,再乘以,3,，得到结果,6,。,步骤,3,：将,6,再乘以,4,，得,24,。,步骤,4,：将,24,再乘以,5,，得,120,。这就是最后的结果。,例,2.1,求,1,2,3,4,5,1000,太繁琐,2.2简单的算法举例例2.1 求12345例2.1,9,2.2,简单的算法举例,改进的算法：,设变量,p,为被乘数,变量,i,为乘数,用循环算法求结果,2.2简单的算法举例改进的算法：,10,2.2,简单的算法举例,S1,：使,p=1,，或写成,1,p,S2,：使,i=2,，或写成,2,i,S3,：使,p,与,i,相乘，乘积仍放在变量,p,中，可表示为：,p*i,p,S4,：使,i,的值加,1,，即,i+1,i,S5,：如果,i,不大于,5,，返回重新执行,S3,；否则，算法结束,最后得到,p,的值就是,5!,的值,若是,1000,，求什么？,2.2简单的算法举例S1：使p=1，或写成1p若是1000,11,2.2,简单的算法举例,S1,：使,p=1,，或写成,1,p,S2,：使,i=2,，或写成,2,i,S3,：使,p,与,i,相乘，乘积仍放在变量,p,中，可表示为：,p*i,p,S4,：使,i,的值加,1,，即,i+1,i,S5,：如果,i,不大于,5,，返回重新执行,S3,；否则，算法结束,最后得到,p,的值就是,5!,的值,若,求,1,3,5,7,9,11,3,3,2,2,11,11,相当于,i 11,2.2简单的算法举例S1：使p=1，或写成1p若求13,12,2.3,算法的特性,一个有效算法应该具有以下,特点,：,(1),有穷性,。一个算法应包含有限的操作步骤，而不能是无限的。,(2),确定性,。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。,2.3算法的特性一个有效算法应该具有以下特点：,13,2.3,算法的特性,一个有效算法应该具有以下,特点,：,(3),有零个或多个输入,。所谓输入是指在执行算法时需要从外界取得必要的信息。,(4),有一个或多个输出,。算法的目的是为了求解，“解”就是输出。,没有输出的算法是没有意义的。,(5),有效性,。算法中的每一个步骤都应当能有效地执行，并得到确定的结果。,2.3算法的特性一个有效算法应该具有以下特点：,14,2.3,算法的特性,对于一般最终用户来说,:,他们并不需要在处理每一个问题时都要自己设计算法和编写程序,可以使用别人已设计好的现成算法和程序,只需根据已知算法的要求给予必要的输入，就能得到输出的结果,输入,3,个数,黑箱子,3,个数中最大数,求,3,个数的最大数,2.3算法的特性对于一般最终用户来说:输入3个数黑箱子3个数,15,2.4,怎样表示一个算法,常用的方法有：,自然语言,传统流程图,结构化流程图,伪代码,2.4怎样表示一个算法常用的方法有：,16,2.4,怎样表示一个算法,2.4.1,用自然语言表示算法,2.4.2,用流程图表示算法,2.4.3,三种基本结构和改进的流程图,2.4.4,用,N-S,流程图表示算法,2.4.5,用伪代码表示算法,2.4.6,用计算机语言表示算法,2.4怎样表示一个算法2.4.1 用自然语言表示算法,17,2.4.1,用自然语言表示算法,2.2节介绍的算法是用自然语言表示的,用自然语言表示通俗易懂，但文字冗长，容易出现歧义性,用自然语言描述包含分支和循环的算法，不很方便,除了很简单的问题外，一般不用自然语言,2.4.1 用自然语言表示算法2.2节介绍的算法是用自然语言,18,2.4.2,用流程图表示算法,流程图,是用一些图框来表示各种操作,用图形表示算法，直观形象，易于理解,起止框,输入输出框,处理框,判断框,流程线,连接点,注释框,x0,Y,N,一个入口,两个出口,2.4.2用流程图表示算法流程图是用一些图框来表示各种操作起,19,2.4.2,用流程图表示算法,流程图,是用一些图框来表示各种操作,用图形表示算法，直观形象，易于理解,起止框,输入输出框,处理框,判断框,流程线,连接点,注释框,位置不够,防止交叉,2.4.2用流程图表示算法流程图是用一些图框来表示各种操作起,20,例,2.6,将例,2.1,的算法用流程图表示。,求,1,2,3,4,5,如果需要将最后结果输出,:,1,t,i5,开始,2,i,t*i,t,i+1,i,结束,N,Y,例2.6 将例2.1的算法用流程图表示。1ti5开始,21,例,2.6,将例,2.1,的算法用流程图表示。,求,1,2,3,4,5,如果需要将最后结果输出,:,1,t,输出,t,i5,开始,2,i,t*i,t,i+1,i,结束,N,Y,例2.6 将例2.1的算法用流程图表示。1t输出ti,22,2.4.3,三种基本结构和改进的流程图,1.,传统流程图的弊端,传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制,使用者可以毫不受限制地使流程随意地转来转去，使人难以理解算法的逻辑,2.4.3 三种基本结构和改进的流程图1.传统流程图的弊端,23,2.4.3,三种基本结构和改进的流程图,2.,三种基本结构,(1),顺序结构,A,B,2.4.3 三种基本结构和改进的流程图2.三种基本结构AB,24,2.4.3,三种基本结构和改进的流程图,2.,三种基本结构,(2),选择结构,A,B,Y,p,N,A,Y,p,N,2.4.3 三种基本结构和改进的流程图2.三种基本结构AB,25,2.4.3,三种基本结构和改进的流程图,2.,三种基本结构,(3),循环结构,当型循环结构,A,Y,p1,N,Y,x5,1,t,输出,t,2,i,t*i,t,i+1,i,例2.11将例2.1的求5!算法用N-S图表示。直到i51,31,一个结构化的算法是由一些基本结构顺序组成的,在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内,一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变,如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法,一个结构化的算法是由一些基本结构顺序组成的,32,2.4.5,用伪代码表示算法,伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法,用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用,2.4.5用伪代码表示算法伪代码是用介于自然语言和计算机语言,33,例,2.16,求,5!,。,begin,(,算法开始,),1,t,2,i,while i,5,t*i,t,i+1,i,print t,end,(,算法结束,),例2.16 求5!。,34,2.4.6,用计算机语言表示算法,要完成一项工作，包括,设计算法,和,实现算法,两个部分。,设计算法的目的是为了实现算法。,不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。,2.4.6用计算机语言表示算法要完成一项工作，包括设计算法和,35,例,2.18,将例,2.16,表示的算法（求,5!,）用,C,语言表示。,例2.18 将例2.16表示的算法（求5!）用C语言表示,36,#include,int main(),int i,t;,t=1;,i=2;,while(i=5),t=t*i;,i=i+1;,printf(%dn,t);,return 0;,#include,37,2.5,结构化程序设计方法,结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构,。,结构化程序设计方法的,基本思路,是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。,2.5结构化程序设计方法结构化程序设计强调程序设计风格和程序,38,2.5,结构化程序设计方法,采取以下方法保证得到结构化的程序：,（,1,）,自顶向下,；,（,2,）,逐步细化,；,（,3,）,模块化设计,；,（,4,）,结构化编码,。,2.5结构化程序设计方法采取以下方法保证得到结构化的程序：,39,