第二章算法ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,C,语言程序设计,第2章 算法,1,第 二 章,程序的灵魂,-,算法,南京信息工程大学计算机与软件学院,黄 群,1第 二 章 程序的灵魂-算法南京信息工程,2,第二章 算法,掌握算法的概念,理解算法的特点,掌握流程图、,N-S,图表示算法的方法,理解结构化程序设计的方法,掌握常见的算法,2第二章 算法掌握算法的概念,3,一个程序应包括的两个方面：,（,1,）对数据的描述,在程序中要指定数据的类型和数据的组织形式，即数据的结构。,（,2,）对操作的描述,即操作步骤，也就是算法。,数据和操作的关系：,数据是操作的对象，操作的目的是对数据进行加工，以得到期望的结果,。,一、算法在程序中的地位,3一个程序应包括的两个方面：一、算法在程序中的地位,4,著名计算机科学家沃斯（,Nikiklaus Wirth,）提出了一个公式：,数据结构,+,算法,=,程序,在设计程序时，还要考虑采用好的设计方法,-,结构化程序设计方法。因此有：,程序,=,数据结构,+,算法,+,程序设计方法,+,语言工具和环境,以上,4,个方面是一个程序设计人员应具备的知识。设计一个程序时要综合运用这几方面的知识。,4著名计算机科学家沃斯（Nikiklaus Wirth）提出,5,上述四个方面中：,算法是灵魂；,数据结构是加工对象；,语言是工具；,编程需要采取合适的方法。,算法解决,做什么,和,怎么做,的问题。,程序中的按一定顺序列出的操作语句，就是算法的体现。,通过本门课，大家学会使用,c,语言的语法编写,C,语言源程序。,5上述四个方面中：,6,二、算法的定义,算法的概念,：用计算机解决问题的步骤，即计算机算法。（,算法举例,）,算法的,5,个特性,：,有穷性,确定性,有零个或多个输入,有一个或多个输出,有效性,6二、算法的定义算法的概念：用计算机解决问题的步骤，即计算机,7,三、简单算法举例,例,1,：,求,1X2X3X4X5,最原始的方法：,步骤,1,：求,1,2,得结果,2,。,步骤,2,：将第,1,步得到的结果再乘以,3,得结果,6,。,步骤,3,：将第,2,步得到的结果再乘以,4,得结果,24,。,步骤,4,：将第,3,步得到的结果再乘以,5,得,120,。即最后结果。,想一想：如果按照此方法，求,1,2,3,.,100,，要写多少步？,因此，上述计算方法不可取！,99,步！,7三、简单算法举例例1：求1X2X3X4X599步！,8,改进的方法（或通用的方法）：,先设两个变量,p,和,i,，,p,代表被乘数，,i,代表乘数。并且将每一步乘积直接放入被乘数变量,p,中。用循环算法求结果。,步骤,1,：令,p=,1,步骤,2,：令,i=,2,步骤,3,：使,p x i,并将乘积放入,p,中。通常表示为,p,i=p,步骤,4,：使,i,的值加,1,，表示为,i+1=i,步骤,5,：如果,i,不大于,5,，返回到步骤,3,继续向下执行；否则算法结束。,p,中的值即最后结果。,8改进的方法（或通用的方法）：,9,先设两个变量,p,和,i,，,p,代表被乘数，,i,代表乘数。并且将每一步乘积直接放入被乘数变量,p,中。用循环算法求结果。,步骤,1,：令,p=,1,步骤,2,：令,i=,3,步骤,3,：使,p i,并将乘积放入,p,中。,通常表示为,p i=p,步骤,4,：使,i,的值加,2,，表示为,i+2=i,步骤,5,：如果,i,不大于,13,，返回到步骤,3,继续向下执行；否 则算法结束。,p,中的值即最后结果。,想一想,:,采用此方法求,1,3,5,.,101,，如何？,如果将题目改为求,1 x 3 x 5 x 7 x 9 x 11x 13,，如何设计算法呢？,9先设两个变量p和i，p代表被乘数，i代表乘数。并且将每一步,10,例,2,：有两个数,a,b,，按大小顺序打印它们。,步骤,1,：输入,a,b,的值；,步骤,2,：如果,ab,则先打印,a,，再打印,b,；,否则，先打 印,b,，再 打印,a,；算法结束。,三、简单算法举例,10例2：有两个数a,b，按大小顺序打印它们。三、简单算法举,11,闰年的条件：,能被,4,整除，但不能被,100,整除的年份；,能被,100,整除，又能被,400,整除的年份；,例,2.,输入一个年份,判定是否闰年，将结果输出,。,11闰年的条件：例2.输入一个年份,判定是否闰年，将结果输,12,S1:,输入一个年份到,y,中,S2:,若,y,不能被,4,整除，则输出,y“,不是闰年,”,;,算法结束,;,否则转,S3;,S3:,若,y,能被,4,整除，不能被,100,整除，则输,出,y“,是闰年,”,;,算法结束,;,否则转,S4;,S4:,若,y,能被,100,整除，又能被,400,整除，输,出,y“,是闰年,”,算法结束,;,否则输出,y“,不是闰年,”,;,算法结束,.,12S1:输入一个年份到y中,13,S1:sigh=1,S2:sum=1,S3:deno=2,S4:sigh=(-1)sigh,S5:term=sigh(1/deno),S6:term=sum+term,S7:deno=deno+1,S8:,若,deno100,，返回,S4,；否则，,例,2.,求,13S1:sigh=1例2.求,14,四、算法的表示,用自然语言表示,用流程图表示（传统流程图和,N-S,图）,用伪代码表示,用计算机语言表示,结构化程序的三种基本结构：,顺序、选择、循环结构,14四、算法的表示用自然语言表示,15,（一）用自然语言表示算法,上节中讨论的例,1,和例,2,的算法是用自然语言写的。,自然语言指人们日常使用的语言，如汉语、英语等。,用自然语言表示算法的特点：通俗易懂，但不严谨，容易产生歧义。,除非问题很简单，一般不用自然语言描述算法。,15（一）用自然语言表示算法上节中讨论的例1和例2的算法是用,16,（二）用流程图表示算法,流程图采用一些图形框表示算法要表述的各种操作。,美国国家标准化协会,ANSI,规定了一些常用的流程图符号,：,起止框 处理框,输入输出框 流程线 或,判断框 连接点,注释,开始,结束,16（二）用流程图表示算法流程图采用一些图形框表示算法要表,17,例,1,的算法用流程图来表示,计算,1 x 3x5x.x11,的值,步骤,1,：令,p=,1,步骤,2,：令,i=,1,步骤,3,：使,p x i,并将乘积放入,p,中。通常表示为,p x i=p,步骤,4,：使,i,的值加,2,，表示为,i+,2,=i,步骤,5,：如果,i,不大于,11,，返回到步骤,3,继续向下执行；否则算法结束。,p,中的值即最后结果。,开始,1=p,1=i,p i=p,i+2=i,i11,真,结束,假,输出,p,的值,17例1的算法用流程图来表示计算1 x 3x5x.x11,18,例,2,的算法用流程图来表示,有两个数,a,b,，按大小顺序打印它们。,步骤,1,：,输入,a,b,的值；,步骤,2,：,如果,ab,则先打印,a,，再打印,b,；否则，先打印,b,，再 打印,a,；,算法结束。,真,假,开始,ab,结束,输出,b,a,的值,输入,a,b,的值,输出,a,b,的值,18例2的算法用流程图来表示有两个数a,b，按大小顺序打印它,19,19,20,（三）三种基本结构,顺序结构：,B,A,虚线框内是一个顺序结构。,AB,两个框是顺序执行的：,按图中所画的框的顺序，先执行,A,操作，再执行,B,操作。,20（三）三种基本结构顺序结构：BA虚线框内是一个顺序结构。,21,选择结构,也称为分支结构。,虚线框内是一个选择结构。,此结构包括一个选择框，框中写有一个条件，根据给定的条件是否成立，从而选择执行,A,框还是,B,框。,例如：条件可以是,i,101,条件,P,A,B,成立,不成立,条件,P,A,成立,不成立,B,操作为空时，画成直线,（三）三种基本结构,21选择结构也称为分支结构。条件PAB成立不成立条件PA成立,22,循环结构（当型,-while,型）,虚线框内是一个当型循环结构。,当给定的条件成立时，执行,A,框中的操作；,执行完,A,操作后，判条件,P,是否成立；,如果仍成立，继续执行,A,操作；,如此反复执行,A,框中的操作，直到条件,P,不成立,为止。,条件,P,A,成立,不成立,（三）三种基本结构,22循环结构（当型-while型）虚线框内是一个当型循环,23,循环结构（直到型,-until,型）,条件,P,A,成立,不成立,虚线框内是一个直到型循环结构。,先执行,A,框中的操作；,执行完,A,操作后，判条件,P,是否成立；,如果不成立，继续执行,A,操作；,如此反复执行,A,框中的操作，直到条件,P,成立,为止。,（三）三种基本结构,23循环结构（直到型-until型）条件PA成立不成立虚,24,（四）结构化程序设计方法,三种基本结构的共同点：,只有一个入口；,一个出口；,结构内每一部分都有机会被执行。,结构内不存在,死循环,。如条件永远成立时，就成了,死循环,已经证明，用上述三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。,由基本结构构成的算法属于,结构化,的算法,24（四）结构化程序设计方法三种基本结构的共同点：,25,对例,1,算法的流程图的结构化分析,计算,1 x 3x5x.x101,的值,步骤,1,：令,p=,1,步骤,2,：令,i=,3,步骤,3,：使,p x i,并将乘积放入,p,中。通常表示为,p x i=p,步骤,4,：使,i,的值加,2,，表示为,i+,2,=i,步骤,5,：如果,i,不大于,101,，返回到步骤,3,继续向下执行；否则算法结束。,p,中的值即最后结果。,开始,1=p,3=i,p i=p,i+2=i,i101,真,结束,假,输出,p,的值,这两个操作之间是顺序关系,这是一个循环结构,这是一个顺序结构,上述算法由基本结构组成,25对例1算法的流程图的结构化分析计算1 x 3x5x.,26,对例,2,算法的流程图的结构化分析,有两个数,a,b,，按大小顺序打印它们。,步骤,1,：,输入,a,b,的值；,步骤,2,：,如果,ab,则先打印,a,，再打印,b,；否则，先打印,b,，再 打印,a,；,算法结束。,真,假,开始,ab,结束,输出,b,a,的值,输入,a,b,的值,输出,a,b,的值,这是一个选择结构,上述算法由基本结构组成,26对例2算法的流程图的结构化分析有两个数a,b，按大小顺序,27,用基本结构的组合表示算法，从而去掉了流程线。避免了随意的跳转。,1973,年两名美国学者提出了一种新的流程图形式，并用二人名字的第一个字母组合命名了该流程图。即,N-S,流程图，也称盒图。,三种基本结构的表示：,顺序 选择 当型循环 直到型循环,P,成立,A,B,（五）用,N-S,流程图表示算法,A,B,不成立,A,当条件,P,成立时,直到条件,P1,成立,A,27用基本结构的组合表示算法，从而去掉了流程线。避免了随意的,28,前面的算法用,N-S,流程图来表示,计算,1 x 3x5x.x11,的值,步骤,1,：令,p=,1,步骤,2,：令,i=,1,步骤,3,：使,p x i,并将乘积放入,p,中。通常表示为,p x i=p,步骤,4,：使,i,的值加,2,，表示为,i+,2,=i,步骤,5,：如果,i,不大于,11,，返回到步骤,3,继续向下执行；否则算法结束。,p,中的值即最后结果。,这两个操作之间是顺序关系,1=P,1=i,直到,i11,p x i=p,i+2=i,打印,P,的值,这是一个顺序结构,这是一个循环结构,上述算法由基本结构组成,28前面的算法用N-S流程图来表示计算1 x 3x5x.,29,（六）用伪码表示算法,伪码,是用一种介于自然语言和计算机语言之间的文字和符号来描述算法。,好处：,书写方便，格式紧凑，易懂，便于向计算机语言过渡。,前面的算法可用伪码表示为：,开