第2章 算法---程序的灵魂 2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,第,2,章 算法,-,程序的灵魂,一个程序主要包括以下两方面的信息：,(1),对数据的描述。,在程序中要指定用到,哪,些数据以及这些数据的类型和数据的组织形式,这就是,数据结构,(data structure),(2),对操作的描述。,即要求计算机进行操作的步骤,也就是,算法,(algorithm),著名计算机科学家沃思,(,Nikiklaus,Wirth),提出一个公式：,算法,+,数据结构,=,程序,算法,、,数据结构,、,程序设计方法,和,语言工具,是一个程序设计人员应具备的知识,2.1,什么是算法,2.2,简单的算法举例,2.3,算法的特性,2.4,怎样表示一个算法,2.5,结构化程序设计方法,2.1,什么是算法,自学,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,。这就是最后的结果。,改进的算法：,设变量,p,为被乘数,变量,i,为乘数,用循环算法求结果,2.2,简单的算法举例,S1,：,1,p,S2,：,2,i,S3,：,p*,i,p,S4,：,i+1,i,S5,：如果,i,不大于,5,，返回重新执行,S3,；否则，算法结束,最后得到,p,的值就是,5!,的值,若是,1000,呢？,例,2.3,判定,2000,2500,年中的每一年是否闰年，并将结果输出。,闰年的条件：,(1),能被,4,整除，但不能被,100,整除的年份都是闰年，如,2008,、,2012,、,2048,年,(2),能被,400,整除的年份是闰年，如,2000,年,不符合这两个条件的年份不是闰年,例如,2009,、,2100,年,设,year,为被检测的年份。算法表示如下：,S1,：,2000,year,S2,：若,year,不能被,4,整除，则输出,year,的值和“不是闰年”。然后转到,S6,S3,：若,year,能被,4,整除，不能被,100,整除，则输出,year,的值和“是闰年”。然后转到,S6,S4,：若,year,能被,400,整除，,则,输出,year,的值和“是闰年”，然后转到,S6,S5:,其他情况,输出,year,的值和“不是闰年”,S6,：,year+1,year,S7,：当,year,2500,时，转,S2,，否则停止,year,不能被,4,整除,非闰年,year,被,4,整除，但不能被,100,整除,闰年,year,被,100,整除，又能被,400,整除,闰年,其他,非闰年,逐渐缩小判断的范围,例,2.5,给出一个大于或等于,3,的正整数，判断它是不是一个素数。,所谓素数,(prime),，是指除了,1,和该数本身之外，不能被其他任何整数整除的数,例如，,13,是素数，因为它不能被,2,，,3,，,4,，,12,整除。,判断一个数,n(n,3),是否素数：将,n,作为被除数，将,2,到,(n-1),各个整数先后作为除数，如果都不能被整除，则,n,为素数,S1,：输入,n,的值,S2,：,i=2,（,i,作为除数）,S3,：,n,被,i,除，得余数,r,S4,：如果,r=0,，表示,n,能被,i,整除，则输出,n,“不是素数”，算法结束；否则执行,S5,S5,：,i+1,i,S6,：如果,i,n-1,，返回,S3,；否则输出,n,“是素数”，然后结束。,可改为,n/2,2.3,算法的特性,自学,2.4,怎样表示一个算法,常用的方法有：,自然语言,传统流程图,结构化流程图,伪代码,2.4,怎样表示一个算法,2.4.1,用自然语言表示算法,2.4.2,用流程图表示算法,2.4.3,三种基本结构和改进的流程图,2.4.4,用,N-S,流程图表示算法,2.4.5,用伪代码表示算法,2.4.6,用计算机语言表示算法,2.4.1,用自然语言表示算法,自学,2.4.2,用流程图表示算法,起止框,输入输出框,处理框,判断框,流程线,连接点,注释框,例,2.6,将例,2.1,的算法用流程图表示。,求,1,2,3,4,5,如果需要将最后结果输出,:,1,t,输出,t,i5,开始,2,i,t*,i,t,i+1,i,结束,N,Y,例,2.8,例,2.3,判定闰年的算法用流程图表示。判定,2000,2500,年中的每一年是否闰年，将结果输出。,N,Y,N,开始,2000,year,year,不能,被,4,整除,year,是闰年,year,不能,被,100,整除,year+1,year,year2500,结束,Y,year,不能,被,400,整除,year,不是闰年,year,是闰年,year,不是闰年,Y,N,Y,N,例,2.10,例,2.5,判断素数的算法用流程图表示。对一个大于或等于,3,的正整数，判断它是不是一个素数。,N,Y,输出,n,是素数,结束,开始,输入,n,2i,n%i,r,r=0,i+1i,i,输出,n,是素数,Y,N,2.4.3,三种基本结构和改进的流程图,(1),顺序结构,A,B,2.4.3,三种基本结构和改进的流程图,(2),选择结构,A,B,Y,p,N,A,Y,p,N,2.4.3,三种基本结构和改进的流程图,(3),循环结构,当型循环结构,A,Y,p1,N,Y,x5,1,t,输出,t,2,i,t*,i,t,i+1,i,例,2.13,将例,2.3,判定闰年的算法用,N-S,图表示,直到,year2500,2000,year,year+1,year,否,是,year%4,为,0,否,是,输出,year,非闰年,year%100,不为,0,year%400,为,0,是,否,输出,year,非闰年,输出,year,闰年,输出,year,闰年,例,2.15,将例,2.5,判别素数的算法用,N-S,流程图表示。,输入,n,r=0,是,否,0,w,2,i,n%i,r,1,w,i+1,i,直到,i,或,w 0,w=0,是,否,输出,n,是素数,输出,n,不是素数,2.4.5,用伪代码表示算法,自学,2.4.6,用计算机语言表示算法,自学,2.5,结构化程序设计方法,自学,