最新09程序设计语言初步第四章二课件

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master title style,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,09程序设计语言初步第四章二,09程序设计语言初步第四章二,1,4.1,算法的概念,4.2,算法的三种基本结构,4.3,算法的描述方法,4.4,结构化程序设计方法,4.5,算法设计实例研究,提纲,2,4.1 算法的概念提纲2,最新09程序设计语言初步第四章二课件,3,最新09程序设计语言初步第四章二课件,4,最新09程序设计语言初步第四章二课件,5,最新09程序设计语言初步第四章二课件,6,最新09程序设计语言初步第四章二课件,7,最新09程序设计语言初步第四章二课件,8,例1 求12,910,，即,10,！,第一种算法：,S1(,求,2!),：先求,21,，得到结果,2,并赋值给变量,p,；即：,21,p,；,S2 (,求,3!),：将步骤,S1,得到的乘积,p,（,p=2,）再乘以,3,，得结果,6,并 赋值给变量,p,；即：,3,p,p,；,S3(,求,4!),：将,p,（,p=6,）再乘以,4,，得,24,并赋值给变量,p,；即：,4p,p,；,S4(,求,5,！,),：将,p,（,p=24,）再乘以,5,，得,120,并赋值给变量,p,；即：,5p,p,；,S9(,求,10!),：将,p,（,p=362880),乘以,10,，得,3628800,，,10p,p,；,9,例1 求12910 ，即10！第一种算法：S1(,#include,main(),int p;,p=2*1; /,求,2!,赋值给,p,p=3*p; /,求,3!,赋值给,p,p=4*p;,p=5*p;,p=6*p;,p=7*p;,p=8*p;,p=9*p;,p=10*p;,/,求,10!,赋值给,p,printf(%d,p);,system(pause);,return 0;,评价：求,10!,需要写,9,个赋值操作，算法过于繁琐！试想：求,1000,！的算法,10,#include评价：求10!需要写9个赋,对算法进行抽象,:,核心操作就是两数相乘,ip,p,，反复相乘,10-1=9,次，,i,初始值为,2,，,p,初始值为,1,，每相乘一次,i,的值加,1,。,根据上述分析，本题可利用循环结构求解：,第,1,次循环用于求,2,！，第,2,次循环在第,1,次循环基础上求,3,！，,第,9,次循环在第,8,次循环基础上求,10,！,例1 求12,910,，即,10,！,11,对算法进行抽象:例1 求12910 ，即10！1,定义两个变量,p,和,i，p,代表阶乘结果,i,代表本次循环要求的是,i!,；,循环条件：,ip；,S4：,使,i,的值加1，即,i+1=i；,S5：,如果,i=10,，返回重新执行步骤,S3,以及其后的步骤,S4,和,S5；,否则，算法结束。,最后得到,p,的值就是10！的值。,求12,910算法思路：,“迭代”和“循环”,：在程序设计中，重复执行同样操作的过程称为,“,迭代,”,。程序中被重复执行的程序段称为,“,循环,”,。,13,S1：使i=2 ；求12910算法思路：“迭代”和,例,1,源程序,#include,main(),int n, i, p; /n,：存储要求阶乘的数；,p,：存储求得的阶乘；,printf(input n:n);,scanf(%d,i=2;,p=1;,while (i = n),p=i*p;,i=i+1;,printf(%d!=%d,n,p);,system(pause);,return 0;,14,例1源程序#include 14,练习,1,：输入十个整数，求出最大值、最小值。,算法思路：采用迭代计算的方法,以求最大值为例，即：,Max(N,1,)=N,1,Max(N,2,N,1,)= N,1,if,N,2,=N,1,Max(N,3,N,2,N,1,)= Max( N,3, Max(N,2,N,1,) ),.,Max(N,n, N,n-1 ,N,2,N,1,),Max(N,n,Max(N,n-1 ,N,2,N,1,),定义变量,max,来存储前,n-1,个整数的最大值。第,n,个数将和,max,比较，决定前,n,个数的最大值。,整个问题就被转变为求,9,次两个数的最大值。,每一次都是读入一个数，和之前求得的最大数再去比较。,15,练习1：输入十个整数，求出最大值、最小值。定义变量max来存,循环条件,：,imax,则,max=n,；,否则，如果,nmin,则,min=n,；,i=i+1;,循环初始化：,读入一整数,n;,min,n; max=n;,i,2,；,请写出本题源程序,16,循环条件：i10循环体：循环初始化：请写出本题源程序16,源程序：,输入十个整数，求出最大值、最小值,#include,#define COUNT 10,main(),int i, n, max, min;/i:,循环计数；,n:,读取的数；,/max:,当前最大值,; min:,当前最小值,scanf(%d, ,max=n; /,将第一个数作为最大值和最小值,min=n;,i=2; /,代表接下去要读取的是第,2,个数,17,源程序：输入十个整数，求出最大值、最小值#includes,源程序：,输入十个整数，求出最大值、最小值,(,续,),while (i max) /,求最大数,max = n;,else if (n i,；,问题分析：就是反复输入处理每一个学生的信息，处理,120,次。,19,例2 输入120个学生的学号和成绩，要求将他们之中成绩在6,输入,120,个学生的学号和成绩，要求将他们之中成绩在60分以上者的学号和成绩打印出来。,S1：1=i；,S2：,读入第,i,个学生的学号和成绩分别到变量,num,和,score,中；,S3：,如果,score 60，,则打印,num,和,score,；,S4：i+1=i,；,S5,：,如果,i120,，,则返回,S2，,继续执行；否则，算法结束。,循环处理模式：,处理本次循环要做的任务；,为下一次循环做准备；,20,输入120个学生的学号和成绩，要求将他们之中成绩在60分以上,4.1,算法的概念,练习,2,：请写出本题对应的程序,21,4.1 算法的概念练习2：请写出本题对应的程序21,4.1,算法的概念,#include,main(),int no,total,count;/no:,学号。,total:,总学生数。,count,：计数,float score;/,成绩,printf(how many int numbers do you want to input:n);,scanf(%d,count=1;,while(count60),printf(no:%dtscore:%fn,no,score);,count=count+1;,system(pause);,return 0,；,22,4.1 算法的概念#include,例3 一个大于或等于,3,的正整数，判断它是否为一个素数（质数）,。,所谓质数，是指除了,1,和该数本身外，不能被其他任何整数整除的数。例如，,13,是素数（质数）。因为它不能被,2,，,3,，,4,，,，,12,整除。,由于素数在当代的密码学中扮演了中心的作用，所以该问题具有重要意义。,判断一个数,n,（,n3,）是否为质数：将,n,作为被除数，将,2,到（,n-1,）各个整数依次作为除数，如果都不能被整除，则,n,为素数。,4.1,算法的概念,23,例3 一个大于或等于3的正整数，判断它是否为一个素数（质数,判断质数,看,n,能否被,2,到（,n-1,）之间的各个整数整除：,变量抽象：,n,：存放被判断的整数；,i,：存放除 数，取值为,2,n-1；,r,：,存放,n/i,得到的余数,循环体：,n,被,i,除，得余数,r；,即,n mod i=r,；,如果,r=0，,表示,n,能被,i,整除，则打印,n“,不是素数”，算法结束；否则,i+1=i,；,循环条件：,ir,；,如果,r=0，,表示,n,能被,i,整除，则打印,n“,不是素数”，令,isPrim=1,；否则,i+1=i,；,循环条件：,ir,S4：,如果,r=0，,表示,n,能被,i,整除，则打印,n,“,不是素数,”,，算法结束；否则执行,S5；,S5：i+1=i；,S6：,如果,in-1，,返回,S3；,否则，打印,n,“,是素数,”,，算法结束。,n,：被判断的整数；,i,：被除数,；r：,存放,n/i,得到的余数,事实上，,i,只需,2,到 之间的整数整除即可。,26,S1：输入n的值；n：被判断的整数；i：被除数；r：存放n,4.1,算法的概念,4.2,算法的三种基本结构,4.3,算法的描述方法,4.4,结构化程序设计方法,4.5,算法设计实例研究,提纲,27,4.1 算法的概念提纲27,4.2,算法的三种基本结构,三种控制结构,(Bohra,和,Jacopini,),顺序结构、 选择结构、循环结构,顺序结构,按书写顺序执行的语句构成的程序段。,28,4.2 算法的三种基本结构 三种控制结构(Bohra和,选择结构,根据给定的表达式是否成立而选择执行操作,A,或操作,B,。如果表达式成立，则执行,操作,A,；如果表达式不成立，则执行,操作,B,。,操作,B,可以为空。,4.2,算法的三种基本结构,29,选择结构 根据给定的表达式是否成立而选择执行操作A或操作B。,当型循环结构,4.2,算法的三种基本结构,C,语言无直到型循环结构。,比较：直到型循环结构和,C,语言中的,do-while,结构？,直到型循环结构,30,当型循环结构4.2 算,三种控制结构的共同点,只有一个入口（,a,处）,只有一个出口（,b,处）,结构内的每一个部分都有机会被执行到,结构内不存在“死循环”（无终止的循环）,4.2,算法的三种基本结构,由这三种基本结构顺序组成的算法结构，可以解决任何复杂问题！,31,三种控制结构的共同点4.2 算法的三种基本结构由这三种基本,4.1,算法的概念,4.2,算法的三种基本结构,4.3,算法的描述方法,4.4,结构化程序设计方法,4.5,算法设计实例研究,提纲,32,4.1 算法的概念提纲32,4.3,算法的描述方法,用自然语言描述,用流程图描述,用,N-S,流程图描述,用伪码描述,用计算机语言描述,33,4.3 算法的描述方法33,4.3,算法的描述方法,自然语言,文字冗长；,不严格，易产生歧义（二义性）；,不方便描述分支和循环结构；,34,4.3 算法的描述方法自然语言34,4.3,算法的描述方法,流程图,流程图的基本元素（,ANSI,规定）,起止框,输入/出框,判断框,处理框,流程线,连接点,注释框,35,4.3 算法的描述方法流程图 流程图的基本元素（ANSI,4.3,算法的描述方法,流程图,流程图描述的选择结构,36,4.3 算法的描述方法流程图流程图描述的选择结构36,当型循环结构,直到型循环结构,流程图描述的循环结构,4.3,算法的描述方法流程图,37,当型循环结构 直到型循环结构流程图描述的循,连接点（小圆圈）：用于将画在不同地方的流程线连接起来,38,连接点（小圆圈）：用于将画在不同地方的流程线连接起来 38,求,10,！流程图,使用当型循环结构描述,39,求10！流程图使用当型循环结构描述39,打印学生序号,及成绩流程图,40,打印学生序号40,判断质数的流程图,使用直到型循环结构描述,判断,r,是否为,0,条件成立则,跳出循环,41,判断质数的流程图使用直到型循环结构描述判断r是否为0条件成立,练习：将以上流程图改成用当型循环结构表示。,该流程图中循环结构有两个出口！违反单入单出原则！,如何改进？,42,练习：将以上流程图改成用当型循环结构表示。该流程图中循环结构,改进后的流程图：单入单出,设置标志位,isPrim,43,改进后的流程图：单入单出 设置标志位isPrim43,传统流程图的弊端,对流程线的使用没有严格限制，阅读困难；,不能保证算法结构的单入单出特性；,占用篇幅较多,；,4.3,算法的描述方法,N-S,流程图,必须限制箭头的滥用，让流程只能顺序执行下去！,保证结构化原则的流程描述工具,N-S,图,44,传统流程图的弊端 4.3 算法的描述方法N-S流程图必须,基本结构,4.3,算法的描述方法,N-S,流程图,p,、,p1,表示的是判断条件；,A,、,B,框是操作；,注意：,A,、,B,框可以是一个简单的操作（如读入数据或打印输出等），也可以是三种基本结构之一,顺序结构,选择结构,当型循环结构,直到型循环结构,45,基本结构4.3 算法的描述方法N-S流程图p、p1,例1 求,10!,的,N-S,流程图,4.3,算法的描述方法,N-S,流程图,46,例1 求10!的N-S流程图4.3 算法的描述方法N-,例2 打印学生成绩,N-S,流程图,4.3,算法的描述方法,N-S,流程图,47,例2 打印学生成绩N-S流程图4.3 算法的描述方法N-,例,3,判断质数的,N-S,流程图,4.3,算法的描述方法,N-S,流程图,48,例3 判断质数的N-S流程图4.3 算法的描述方法N-S,4.3,算法的描述方法,伪码描述,流程图和,N-S,图画起来比较费事，适合于表示算法，而在算法设计中使用不是很理想。,伪码,用,介于自然语言和程序设计语言之间的文字和符号来描述算法。,【,返回,】,IF,x is positive,THEN,print x,ELSE,print y,WHILE,i60,THEN,print score,i,加,1,49,4.3 算法的描述方法伪码描述流程图和N-S图画起来比较,4.3,算法的描述方法,例4：利用泰勒级数：,-,L,L,L,L,+,-,-,+,+,-,+,-,=,+,)!,1,2,(,),1,(,!,7,!,5,!,3,sin,1,2,1,7,5,3,n,x,x,x,x,x,x,n,n,计算正弦的值，直到最后一项绝对值小于10,-6,时为止。,被除数,除数,符号,n,1,n,2,n,3,分析：求,n,项和的算法思路,Sum(a,1,)=a,1,Sum(a,1,a,2,)=Sum(a,1,)+a,2,=a,1,+a,2,Sum(a,1,a,2, a,3,)=Sum(a,1,a,2,)+a,3,Sum(a,1,a,2,a,n,)=Sum(a,1,a,2,a,n-1,)+a,n,50,4.3 算法的描述方法例4：利用泰勒级数：-LLLL+-,4.3,算法的描述方法,算法的核心操作是求两数之和，其中第一个操作数是前一次求得的和。如何求第二个操作数？,算法,1,：,n,决定了第,n,项因子的值，即第二个操作数；因此每一次可根据当前,n,的值计算出第二个操作数。,请用,N,S,图描述出算法,1,。,51,4.3 算法的描述方法算法的核心操作是求两数之和，其中第一,求,sin(x),算法,1,i,代表下一个,p,是第几项，因此初值是,1,变量抽象：,x,：存储未知数,x,的值；,sum,：存储和 ；,p,：存储当前待加的因子；,i,：当前待加的是第几个因子,52,求sin(x)算法1i代表下一个p是第几项，因此初值是1变量,问题：,任何数据类型只能表示一定范围内的数，当试图往变量中存储在范围之外的数，数据无法正确存储。,求,x,的,n,次方和,(2n-1)!,时可能会导致结果太大而溢出。,解决方法：,1.,用浮点型变量来保存,(2n-1)!,的结果,2.,改进算法,算法,2,53,问题：任何数据类型只能表示一定范围内的数，当试图往变量中存储,4.3,算法的描述方法,=,-,-,-,)!,3,2,(,),1,(,3,2,i,x,i,i,=,-,-,-,+,)!,1,2,(,),1,(,1,2,1,i,x,i,i,-,L,L,L,L,+,-,-,+,+,-,+,-,=,+,)!,1,2,(,),1,(,!,7,!,5,!,3,sin,1,2,1,7,5,3,n,x,x,x,x,x,x,n,n,算法,2,：设第,i,项因子表示为 ，考察 和 的关系。,= *(-1)*,x,2,/(,(2i-1)*(2i-2),54,4.3 算法的描述方法=-)!32()1(32ixii,请用,N,S,图描述算法,2,。,4.3,算法的描述方法,【,源程序演示,】,i,代表下一个,p,是第几项，因此初值是,1,55,请用NS图描述算法2。4.3 算法的描述方法【源程序演示,#include,#include,main(),int i;,float x;,double sum,p; /p,用于存放待加的那一项,printf(input x:);,scanf(%f,/*,变量初始化*,/,sum=0.0;,i=1;,p=x;,/*,求解*,/,while(fabs(p)1e-8),sum=sum+p;,i=i+1;,p=-p*x*x/(2*i-2)*(2*i-1);,printf(sin(%f) = %lfn,x,sum);,system(pause);,return 0;,56,#include56,4.1,算法的概念,4.2,算法的三种基本结构,4.3,算法的描述方法,4.4,结构化程序设计方法,4.5,算法设计实例研究,提纲,57,4.1 算法的概念提纲57,源自于对,goto,语句的争论,goto,语句详见,程序设计教程,436,页,4.4,结构化程序设计方法,58,源自于对goto语句的争论4.4 结构化程序设计方法58,#include ,main(),int count=1;,start: /,标号,是跟有冒号的标识符,if (count10),goto end;,printf(%d ,count);,count=count+1;,goto start;,end:,printf(n);,system(pause);,return 0;,1 2 3 4 5 6 7 8 9 10,请按任意键继续,. . .,运行效果：,59,#include 1 2 3 4 5 6,4.4,结构化程序设计方法,用三种基本结构组成的程序必然是,结构化,的程序，这种程序便于编写、阅读、修改和维护 。,结构化程序设计强调,程序设计风格,和,程序结构的规范化,，提倡清晰的结构 。,结构化程序设计方法的基本思想：采用分而治之的方法，将一个复杂问题分解为相对简单的一些子问题，然后针对这些子问题进行求解。如果某个子问题仍然是比较复杂的，再进一步分解为子,-,子问题，直到所有问题都能够求解。求解问题的过程是分阶段进行的，每个阶段处理的问题都控制在人们容易理解和处理的范围内（,67,个之内）。,60,4.4 结构化程序设计方法用三种基本结构组成的程序必然是结,4.4,结构化程序设计方法,结构化程序设计方法,自顶向下；,逐步细化；,模块化设计（函数）；,结构化编码（三种基本结构）。,61,4.4 结构化程序设计方法结构化程序设计方法61,例,4.13,利用辗转相除法求两个正整数的最大公约数。,辗转相除法求最大公约数的数学定义如下：,GCD,（,x,y,）,= y | xy and x MOD y = 0,GCD,（,y, x MOD y,）,| xy and x MOD y 0; ,说明：先判断,x,能否被,y,整除，若可以，则最大公约数就是除数,y,；否则，则将,y,作为被除数，,x MOD y,作为除数继续上面的操作，直到,x,能否被,y,整除为止。,GCD(6,4),GCD(4,2),=,=,2,=,GCD(124,6),最大公约数为,2,例如：求,GCD(124,6),的过程为：,62,例4.13 利用辗转相除法求两个正整数的最大公约数。GCD,算法,1,x,y,r,2,3,1,交换变量,x,和,y,的值：,自顶向下，逐步细化,63,算法1xyr231交换变量x和y的值：自顶向下，逐步细化63,最终算法,1,算法设计任务结束的标准是各步骤已精细到能用语句描述，即满足算法的,5,大特征标志算法设计任务结束 。,64,最终算法1算法设计任务结束的标准是各步骤已精细到能用语句描述,算法,2,思考：能否不借助于变量,r,，而是,x,y; y,x%y,？,或者,y,x%y,；,x,y,65,算法2思考：能否不借助于变量r，而是xy; y x%y,练习,3,：设计算法，求一个正整数的长度。,算法,1,：例如,num=12345,，求,num,的长度,第,1,步：去掉最低位，,num=1234,，长度,len=1,第,2,步：去掉最低位，,num=123,，长度,len=2,第,3,步：去掉最低位，,num=12,，长度,len=3,第,4,步：去掉最低位，,num=1,，长度,len=4,第,5,步：去掉最低位，,num=0,，长度,len=5,算法中每一步的核心操作是从,num,中去掉最低位，长度,len,加,1,66,练习3：设计算法，求一个正整数的长度。算法中每一步的核心操作,67,67,假设,num,长度不超过,8,，例如,num=12345,，求,num,的长度,算法,2,：试探能被,10,的几次方除后商不为,0,第,1,步：,num /10,7,=0,第,2,步：,num /10,6,=0,第,3,步：,num /10,5,=0,第,4,步：,num /10,4,!=0,说明长度为,4+1,5,算法中每一步的核心操作是试探：,num,除,10,i,后商是否,0,68,假设num长度不超过8，例如num=12345，求num的长,增加对输入为,0,的判断,进一步细化,69,增加对输入为0的判断进一步细化69,练习,4,：输入一个不超过,8,位的正整数，要求把这个整数分解为单个数字，然后打印出每一个数字（每一个数字之间用两个空格分开）。例如用户输入了,4200,，程序打印结果为：,4 2 0 0,。设计算法。,第,1,步：得到,num,最高位,4,并输出，,num=200,第,2,步：得到,num,最高位,2,并输出，,num=0,第,3,步：得到,num,最高位,0,并输出，,num=9,第,4,步：得到,num,最高位,0,并输出，,num=0,70,练习4：输入一个不超过8位的正整数，要求把这个整数分解为单个,71,71,练习,5,：设计算法，判断一个正整数是否是回文数。回文数是指正读和反读都一样的数。,算法,1,：,比较第,1,位和倒数第,1,位,比较第,2,位和倒数第,2,位,算法,2,：反着读，假设读得的数为,reverseNum,，判断,num,和,reverseNum,是否相等,72,练习5：设计算法，判断一个正整数是否是回文数。回文数是指正读,以求,a,0,a,1,a,2,a,3,的逆数为例，假设,reverse,实现逆着读,reverse(a,3,)=a,3,reverse(a,2,a,3,)=a,3,a,2,=a,3,*10 + a,2,=,reverse(a,3,)*10+a,2,reverse(a,1,a,2,a,3,)=a,3,a,2,a,1,=a,3,a,2,*10 + a,1,=reverse(a,2,a,3,)*10+ a,1,reverse(a,0,a,1,a,2,a,3,)=a,3,a,2,a,1,a,0,=a,3,a,2,a,1,*10+a,0,=reverse(a,1,a,2,a,3,)*10+a,0,73,以求a0a1a2a3的逆数为例，假设reverse实现逆着读,判断回文数,-,算法,1,74,判断回文数-算法174,判断回文数,-,算法,2,75,判断回文数-算法275,#include,main(),int num;/,存放输入的整数,int num1; /*,循环中处理的数,每循环一次,右边少一位,假设,num,为,1234,则,num1,初始值为,1234,然后是,123,然后是,12.;*/,int reverse;/*,是用分解出来的数字组成的新数*,/,int m;/*m:,存放每一个分解出来的数字,;*/,printf(,请输入一个小于,8,位的正整数,:); /,读取要判断的整数,scanf(%d,/*,从右到左依次取出各个数字组装成一个新的整数保持到,reverse,中*,/,num1=num;,reverse=0;,while(num1!=0),m=num1%10; /*,取出,num1,的最低位*,/,reverse=reverse*10+m; /*,将最低位组装到,reverse,中*,/,num1=num1/10; /*,去掉,num1,的最低位*,/,if (num=reverse),printf(%d,是回文数,n,num);,else,printf(%d,不是回文数,n,num);,system(PAUSE);,return 0;,76,#include76,总结：循环结构解题,很多题目都需要循环结构进行求解。,当一时难以整理出每次循环（迭代）所做的事情时，可以先看一下如果这件事情交给人做的话，一步一步是怎么做的。,在上一步基础上抽象出循环结构的四个方面。,77,总结：循环结构解题很多题目都需要循环结构进行求解。77,总结：循环结构解题,2,和,3,一般没有绝对的先后顺序。,在分析清楚,2,和,3,后，才分析,4,（为什么？）。,一般将,1,放在最后分析,在,4,中，要对出现在,2,和,3,中的某些变量进行修改，为下次循环做好准备，并使得循环能最终结束。,思考上述四项工作有无先后顺序？应该是什么顺序？,78,总结：循环结构解题2和3一般没有绝对的先后顺序。在4中，要对,总结：对一批数进行处理的模式,循环次数未知,循环次数已知,79,总结：对一批数进行处理的模式循环次数未知循环次数已知79,4.1,算法的概念,4.2,算法的三种基本结构,4.3,算法的描述方法,4.4,结构化程序设计方法,4.5,算法设计实例研究,提纲,80,4.1 算法的概念提纲80,例,4.14,设计交通车辆观测统计算法。,问题描述：在一个路口设置一个探测器，通过通信线路连接到后台的计算机。路口每通过一辆汽车，探测器向计算机发出一个车辆信号,1,，探测器每隔,1,秒钟向计算机发出一个时钟信号,0,，观测结束向计算机发出结束信号,。,要求在计算机上设计一个程序，能够接收探测器发出的信号，统计出观测的时长、在观测时长内通过的车辆总数、以及两辆车之间最大的时间间隔。,问题分析：探测器向计算机发出的信号可以认为是一个任意长的字符序列（以,#,结束），比如：“,011011000111101#”,，这样设计程序实际上演变为读取该字符序列，然后进行相关的操作。,1,4.5,算法设计实例研究,观测时长,：字符序列中,0,的个数,(6,秒,),；,车辆总数,：字符序列中,1,的个数,(9,辆,),；,两车间最大时间间隔,：两个,1,之间的最大连续,0,的个数,(3,秒,),；,探测器,81,例4.14 设计交通车辆观测统计算法。 问题分析：探测器向计,计算观测时长（,0,的个数）和车辆总数（,1,的个数）是容易实现的，但是如何计算最大时间间隔需要进一步考虑。在对一个比较复杂的问题进行分析时，我们应该采用分而治之的方法，将复杂的问题分解为相对比较简单的问题，再针对该较简单问题进行求解。,我们首先设计算法主体框架。,“,0000,11,0,1,000,11,0,1,0,#,”,！注意：,2006,年,9,月出版的教材假设接收到的信号总是以,1,开始，因此算法会有所简化,82,计算观测时长（0的个数）和车辆总数（1的个数）是容易,“,0000,11,0,1,000,11,0,1,0,#,”,signal!=,#,待细化,83,“0000110100011010#”signal!=#,84,84,Level 1,层算法设计,第,0,层算法,第,1,层算法,85,Level 1层算法设计第0层算法第1层算法85,“,0000,11,0,1,000,11,0,1,0,#,”,分析：,处理时钟信号,0,观测时长,seconds,加,1,；,两种情况。如果此前已接收到车辆信号,1,(,如何判断？,),，则间隔时长,interval,加,1,；否则不做任何处理。,86,“0000110100011010#”分析：处理时钟信号0,“,0000,11,0,1,000,11,0,1,0,#,”,分析：,处理车辆信号,1,第一种： “,0000,1,10100011010#”,（这是第一个,1,）,车辆总数,vehicles,加,1,第二种： “,00001,1,010001,1,010#”,（不是第一个,1,，且前一个信号也是,1,）,车辆总数,vehicles,加,1,第三种： “,0000110,1,000,1,10,1,0#”,（不是第一个,1,，且前一个信号是,0,）,车辆总数,vehicles,加,1,处理是否要更新最长时间间隔（,interval,：两车之间的时间间隔，,longest,：两车之间的最长时间间隔）,87,“0000110100011010#”分析：处理车辆信号1,“,0000,1,1,0,1,000,1,1,0,1,0,#,”,分析：处理车辆信号,1,vehicles,vehicles,+,1,；,情况,1,：第一个,1,判断式：,vehicles,=1,情况,2,：不是第一个,1,，且前一个信号也是,1,判断式：,vehicles1 & interval=0,情况,3,：不是第一个,1,，且前一个信号是,0 :,判断式：,vehicles1 & interval0,处理：,1,）若,intervallongest,则,longest,interval,。,2,）,interval,0,。,情况,1,情况,3,情况,2,88,“0000110100011010#”分析：处理车辆信号1,“,0000,11,0,1,000,11,0,1,0,#”,验证算法,【,程序演示,】,89,“0000110100011010#”验证算法【程序演示】8,#include,main(),int vehicles; /,记录车辆信号总数,int seconds; /,记录时钟信号总数,int longest; /,记录最长时间间隔,int interval; /,记录时间间隔,char signal; /,存放读取的信号,/*,初始化设置 *,/,vehicles=0;,seconds=0;,longest=0;,interval=0;,printf(please input signal: n);,scanf(%c,/*,读入第一个信号 *,/,90,#include90,/*,循环结构处理输入信号的字符序列,边读取边处理 *,/,while (signal!=#) ,if (signal=1) /*,处理车辆信号*,/,vehicles=vehicles+1;,if (vehicles1 & interval0),if (intervallongest),longest=interval;,interval=0;,else/*,处理时钟信号*,/,seconds=seconds+1;,if (vehicles0),interval=interval+1;,scanf(%c,91,/* 循环结构处理输入信号的字符序列,边读取边处理 */9,/*,输出结果 *,/,printf(%d vehicles passed in %d secondsn,vehicles,seconds);,printf(the longest gap was %d secondsn,longest);,system(PAUSE);,return 0;,92,/* 输出结果 */92,练习：将一个由数字字符组成的字符串转换为整数或者小数并输出。如：,输入,:134.567#,输出,:134.567,93,练习：将一个由数字字符组成的字符串转换为整数或者小数并输出。,#include,main(),char ch;,int num; /存放小数点前面的字符转换后得到的整数,float fnum; /存放小数点后面的字符转换后得到的浮点数,int n; /存放字符对应的数字,int p; / 存放小数点后面的字符转换后得到的数字对应的基数1/p。小数点后第一位数的基数是1/10,int flag;/用于表示输入的字符中是否有小数点。若有，则flag值为1；否则为0,num = 0;,fnum = 0;,p = 10;,flag = 0;,printf(please input the string:);,算法,1,：读情况对字符进行处理,94,#include算法1：读情况对字符进行,scanf(%c,while( ch != #),if (ch=.),flag = 1;/flag,为,1,，表示输入了小数点,else /,处理小数点之前的字符,n = ch - 0;,if (flag = 0)/,若输入的是小数点之前的数,num = num * 10 + n;,else/,处理小数点之后的字符,fnum = fnum + (float)n / p; /,必须进行强制类型转换，否则,n/p,结果为,0,p = p * 10;,scanf(%c,95,scanf(%c,95,if (flag = 0),printf(the result is:%dn,num);,else,printf(the result is:%fn,num+fnum);,system(pause);,return 0;,96,if (flag = 0)96,#include,main(),char ch;,int num;,float fnum;,int n;,int p;,printf(please input the string:);,/,处理整数部分,num = 0;,scanf(%c,while(ch != . & ch != #),n = ch - 0;,num = num * 10 + n;,scanf(%c,算法,2,：先循环处理小数点前面的字符，再循环处理小数点后面的字符,97,#include算法2：先循环处理小数点,if (ch=.),/,处理小数部分,p = 10;,scanf(%c,while(ch != #),n = ch - 0;,fnum = fnum + (float)n / p; /,必须进行强制类型转换，否则,n/p,结果为,0,scanf(%c,p = p * 10;,if (fnum 0),printf(the result is:%dn,num);,else,printf(the result is:%fn,num+fnum);,system(pause);,return 0;,98,if (ch=.)98,迭代算法,迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。,利用迭代算法解决问题，需要做好以下三个方面的工作,确定迭代变量,a,i,。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。,建立迭代关系式，即,a,i,f(a,i-1,),对迭代过程进行控制,。,迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。,99,迭代算法迭代算法是用计算机解决问题的一种基本方法。它利用计算,例,4.15,猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一只，第二天照此办理，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？,4.5,算法设计实例研究,100,例4.15 猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉,分析：假设第一天早上吃前有桃子,a1,个,第二天早上吃前有桃子,a2,个，第三天早上吃前有桃子,a3,个，以此类推，则,a,2,a,1,（,a,1,/2+1,）,= a,1,/2-1,a,9,a,8,（,a,8,/2+1,）,= a,8,/2-1,a,10,a,9,（,a,9,/2+1,）,= a,9,/2-1 = 1,可见，在已知,a,10,的情况下，可以求得,a,9,，已知,a,9,可以求得,a,8,最终求得,a,1,101,分析：假设第一天早上吃前有桃子a1个,第二天早上吃前有桃子a,即：,a,9,= 2 ( a,10,+ 1 ),a,8,= 2 ( a,9,+ 1 ),a,1,= 2 ( a,2,+ 1 ),也就是：,a,i,2(a,i+1,+1) i=9,8,7,6,.,1,现在已知,a,10,值为,1,，可以采用迭代法求得,a,1,。,102,即：102,103,103,依次计算出第,9,天、第,8,天,第,1,天吃前的桃子数,current_day_count,表示当天的桃子数，代表数学模型中的,ai,。初始值是,1,，代表第,10,天早上的桃子数是,1,。,day_count,表示第几天，代表数学模型中的,i,。初始值为,9,，代表第一次循环求的是第,9,天早上的桃子数。,【,程序,演示,】,104,依次计算出第9天、第8天第1天吃前的桃子数current,#include,main(),int day,；,/,表示当前求解的是第几天吃前的桃子数,int peach; /,示某一天的桃子数,day = 9; /,第一次循环求第,9,天吃前的桃子数,peach = 1; /,第,10,天吃前的桃子数是,1,while(day = 1),peach = 2 * ( peach + 1);,day = day - 1;,printf(,桃子数是：,%d,peach);,system(pause);,105,#include105,第一天：,1534,个桃子,第二天：,766,个桃子,第三天：,382,个桃子,第四天：,190,个桃子,第五天：,94,个桃子,第六天：,46,个桃子,第七天：,22,个桃子,第八天：,10,个桃子,第九天：,4,个桃子,第十天：,1,个桃子,106,第一天：1534个桃子106,Common Problems:,Sentence 1;,Sentence 2;,; (if, while, for),main(),107,Common Problems:107,逗号运算符和逗号表达式,逗号运算符 ， 用于把几个表达式串在一起。,逗号表达式 含有逗号运算符的表达式，实现对各个表达式的顺序求值，主要用于,for,语句中。,执行过程 先计算表达式,1,，然后依次计算其后的各个表达式的值，并将最右边那个表达式的值作为逗号表达式的值。,表达式1,，,表达式2,，,，,表达式,n,y = 1 0 ;,x = ( y = y - 5 , 30 / y ) ;,/,运算后,y,=,5,，,x,=,6,。,/,逗号表达式优先级比赋值表达式低，所以必须加括号,108,逗号运算符和逗号表达式表达式1 ，表达式2， ，表达式ny,总结：循环结构解题,很多题目都需要循环结构进行求解。,当一时难以整理出每次循环（迭代）所做的事情时，可以先看一下如果这件事情交给人做的话，一步一步是怎么做的。,在上一步基础上抽象出循环结构的四个方面。,109,总结：循环结构解题很多题目都需要循环结构进行求解。109,总结：循环结构解题,2,和,3,一般没有绝对的先后顺序。,在分析清楚,2,和,3,后，才分析,4,（为什么？）。,一般将,1,放在最后分析,在,4,中，要对出现在,2,和,3,中的某些变量进行修改，为下次循环做好准备，并使得循环能最终结束。,思考上述四项工作有无先后顺序？应该是什么顺序？,110,总结：循环结构解题2和3一般没有绝对的先后顺序。在4中，要对,总结：对一批数进行处理的模式,循环次数未知,循环次数已知,111,总结：对一批数进行处理的模式循环次数未知循环次数已知111,迭代算法,迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。,利用迭代算法解决问题，需要做好以下三个方面的工作,确定迭代变量,a,i,。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。,建立迭代关系式，即,a,i,f(a,i-1,),对迭代过程进行控制,。,迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。,112,迭代算法迭代算法是用计算机解决问题的一种基本方法。它利用计算,练习,6,：一个皮球从,100m,高处落下，每次落地后反弹到原来高度的一半。编写程序，求,20,次反弹时弹起的高度。,【,程序,演示,】,分析：,a,0,=100,a,1,=a,0,/2,a,2,=a,1,/2,a,20,=a,19,/2,113,练习6：一个皮球从100m高处落下，每次落地后反弹到原来高度,#include,#define TIMES 20,main(),int times; /,记录是第几次弹起,double height; /,记录小球弹起时的高度,height=10000.0; /*height,的单位是,cm*/,times=1;/*,第一次循环求第,1,次弹起高度 *,/,while(times=TIMES),height=height/2;/*,除以,2,后的,height,表示第,times,次弹起的高度*,/,times=times+1;,printf(,第,%d,次小球弹起的高度是,%f,厘米,TIMES,height);,return 0;,114,#include114,练习,7,：