第6章-函数与过程.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 函数与过程,第一节 函数,第二节 过程,第三节 递推算法,第四节 递 归,前面我们曾经学习了程序设计中的三种基本控制结构（顺序、分支、循环）。用它们可以组成任何程序。但在应用中，还经常用到子程序结构。,通常，在程序设计中，我们会发现一些程序段在程序的不同地方反复出现，此时可以将这些程序段作为相对独立的整体，用一个标识符给它起一个名字，凡是程序中出现该程序段的地方，只要简单地写上其标识符即可。这样的程序段，我们称之为子程序。,子程序的使用不仅缩短了程序，节省了内存空间及减少了程序的编译时间，而且有利于结构化程序设计。因为一个复杂的问题总可将其分解成若干个子问题来解决，如果子问题依然很复杂，还可以将它继续分解，直到每个子问题都是一个具有独立任务的模块。这样编制的程序结构清晰，逻辑关系明确，无论是编写、阅读、调试还是修改，都会带来极大的好处。,在一个程序中可以只有主程序而没有子程序,(,本章以前都是如此,),，但不能没有主程序，也就是说不能单独执行子程序。,Pascal,中子程序有两种形式：,函数,和,过程,。,第一节 函数,在此之前，我们曾经介绍并使用了,Pascal,提供的各种标准函数，如,Abs(),Sqr(),等等，这些系统提供的函数为我们编写程序提供了很大的方便。比如：求,sin(1)+sin(2)+,+sin(100),的值。但这些函数只是常用的基本函数，编程时经常需要自定义一些函数。,我们来看看下面一个例子：,求：,1,！,2,！,3,！,10,！？,如果要编写程序，我们看到求阶乘的操作要执行,10,次，只不过每次所求的数不同。我们想：不至于编写,10,遍求阶乘的程序吧。我们希望有一个求阶乘的函数，假设为,js(x),，那么我们就可以这样求这道题了。,例,6.1,Program ex6_1;,var i:integer;,sum:longint;,BEGIN,sum:=0;,for i:=1 to 10 do,sum:=sum+js(i);,writeln(sum=,sum);,END.,现在的问题是：,Free PASCAL,没提供,js(x),这样一个标准函数，这个程序是通不过的。如果是,PASCAL,的标准函数，我们可以直接调用，如,trunc(x),，,ln(x),，,sqrt(x),而,PASCAL,提供给我们的可供直接调用的标准函数不多。没关系，我们编写自己的函数！,函数的定义,在,Pascal,中，函数也遵循先说明后使用的规则，在程序中，函数的说明放在调用该函数的程序（主程序或其它子程序）的说明部分。函数的结构与主程序的结构很相似。,函数定义的一般格式：,Function ():;,/,函数首部,;,begin,/,以下是函数体,;,;,end;,说明：,函数由首部与函数体两部分组成。,函数首部以关键字,Function,开头，表示子程序是一个函数。,函数名是用户自定义的标识符。,函数的类型也就是函数返回值的类型，所求得的函数值通过函数名传回调用它的程序。可见，函数的作用一般是为了求得一个值。,形式参数简称形参，形参即函数的自变量。自变量的初值来源于函数调用。在函数中，形参一般格式如下：,变量名表,1:,类型标识符,1,；变量名表,2:,类型标识符,2,；,；变量名表,n:,类型标识符,n,。,可见形参表相当于变量说明，对函数自变量进行说明。,当缺省形参表（当然要同时省去一对括号）时，称为无参函数。,函数体与程序体基本相似，由说明部分和执行部分组成。,函数体中的说明部分用来对本函数使用的标号、常量、类型、变量、子程序加以说明，这些量只在本函数内有效，有效范围是局部的。,函数体的执行部分由,begin,开头，,end,结束，中间有若干用分号隔开的语句，只是,end,后应跟分号，不能像程序那样用句号,.,。,在函数体的执行部分，至少应该给函数名赋一次值，以使在函数执行结束后把函数值带回调用程序，新版本支持用,exit(,返回值,),命令带出返回值。,编写一个阶乘的函数，我们给此函数取一个名字,js,。,Function js(n:integer):longint;,Var i:integer;,s:longint;,begin,s:=1;,for i:=1 to n do,s:=s*i;,js:=s;,end;,在本例中，函数名叫,js,，只有一个,integer,型的自变量,n,，函数,js,属,longint,型。在本函数中，要用到两个变量,i,，,s,，在,var,后已加以说明。在函数体中，是一个求阶乘的语句，但有一点要注意：虽然,n,的阶乘的值在,s,中，但最后必须将此值赋给函数,js,，此时,js,不带任何参数。在任何函数中，最后都要把最终结果赋给函数名，因为该函数的结果是靠函数名返回的。,在这里，函数的参数,n,是一个接口参数，说得更明确点是入口参数。如果我们调用函数：,js(3),，那么在程序里所有有,n,的地方，,n,被替代成,3,来计算。在这里，,3,就被称为实参。又如：,sqrt(4),，,ln(5),，这里,4,，,5,叫,实参,。而,ln(x),，,sqrt(x),中的,x,，,y,叫,形参,。,函数的调用,我们可以在任何与函数值类型兼容的表达式中调用函数，或者说，函数调用只能出现在允许表达式出现的地方，或作为表达式的一个因子。,函数调用方式与标准函数的调用方式相同。,函数调用的一般格式：,函数名,或,函数名（实在参数表）,说明：,实在参数简称实参。实参的个数必须与函数说明中形参的个数一致，实参的类型与形参的类型应当一一对应。,调用函数时，一般的，实参必须有确定的值。,函数调用的步骤为：计算实参的值，,赋给,对应的形参；,我们对函数进行了定义，在后面的程序中都可以象标准函数那样直接调用自定义函数了。我们对,例,6.1,用自定义函数进行编写程序。,例,6.2,求,1!+2!+10!,的值。,程序如下,：,Program ex6_2;,var i:integer;,sum:longint;,Function js(n:integer):longint;,var i:integer;,s:longint;,begin,s:=1;,for i:=1 to n do,s:=s*i;,js:=s;,end;,BEGIN,sum:=0;,for i:=1 to 10 do,sum:=sum+js(i);,writeln(sum=,sum);,END.,函数的应用举例,例,6.4,利用前面定义的阶乘函数，求,5,！，,9,！。,程序如下：,Program ex6_4;,Var a1,a2:longint;,Function js(n:integer):longint;,Var i:integer;,s:longint;,begin,s:=1;,for i:=1 to n do,s:=s*i;,js:=s;,end;,BEGIN,a1:=js(5);,a2:=js(9);,writeln(5!=,a1,9!=,a2);,END.,在这个程序中，在主程序的,BEGIN,之前，我们对函数进行了一次说明，在后面的程序中都可以象标准函数那样直接调用自定义函数了。在,Function,语句中，用的是形参,n,，在主程序调用中，调用函数是用的实参，如：,js(5),；程序执行到这儿会自动将,5,代入前面的,Function,函数中，用,5,取代所有的,n,，最终将结果赋值给,js,。所以在,a1,中一定是,5,！，,a2,中是,9,！。另外，函数不能单独使用，一定要结合主程序才能运行。,主程序的变量,a1,，,a2,叫全程变量，它们除了主程序外，还可以在函数中出现；在函数说明中用到的变量,i,，,s,则是局部变量，只能在函数部分使用，一旦出了函数则失去意义；别外要注意：全程变量和局部变量尽量不要同名。,例,6.5,任意输入,10,组三角形的三边，求其面积。,我们可以定义一个已知三角形三边求其面积的函数，设为,area(a1,a2,a3),。,程序如下,：,Program ex6_5;,Var a,b,c,s:real;,i:integer;,Function area(a1,a2,a3:real):real;,var s1,d:real;,begin,d:=(a1+a2+a3)/2;,s1:=Sqrt(d*(d-a1)*(d-a2)*(d-a3);,area:=s1;,end;,BEGIN,for i:=1 to 10 do,begin,writeln(input a,b,c);,readln(a,b,c);,if(a+b=c)or(a+c=b)or(b+c0)and(not f)do,begin,e:=n mod 10;,n:=n div 10;,if e=d then f:=true;,end;,check:=f;,end;,BEGIN,writeln(input n,d);,read(a,b);,writeln(check(a,b);,END.,例,6.7,计算如图多边形的面积。,从图中可以看出，五边形的面积是三个三角形面积之和。,b1,b2,b3,b4,b5,b6,b7,程序如下：,Program ex6_7;,Var b1,b2,b3,b4,b5,b6,b7,s:real;,Function area(a,b,c:real):real;,Var P:real;,Begin,P:=(a+b+c)/2;,Area:=sqrt(p*(p-a)*(p-b)*(p-c);,End;,BEGIN ,主程序,Write(please input b1,b2,b3,b4,b5,b6,b7:);,Readln(b1,b2,b3,b4,b5,b6,b7);,S:=area(b1,b5,b6)+area(b2,b6,b7)+area(b3,b4,b7);,三次调用函数,area,Writeln(s=,s:10:3);,END.,函数课堂练习,1.,编程找出由键盘任意输入二个整数中的最大数。,2.,编程找出由键盘任意输入三个整数中的最大数。,3.,求从键盘任意输入两个自然数的最大约数。,4.,求从键盘任意输入三个自然数的最大约数。,5.,求从键盘任意输入两个自然数的最小公倍数。,6.,用函数求,1+2+3+n,的和（,n R 0,）,3.,求正整数,2,和,100,之间的完全数。,完全数：因子之和等于它本身的自然数，如,6=1+2+3,；,4.,如果一个自然数是素数,且它的数字位置经过对换后仍为素数,则称为绝对素数,例如,13,。试求出所有二位绝对素数,5.,编写程序计算表达式：,Y=x2+SH(x),，,SH(x),是双曲正弦函数,【,提示,】,在,Fp,中没有,SH(),函数，需要由用户自已定义，由数学知识知：,SH(x)=(e x e x)/2,。,第二节 过程,在,Pascal,中,自定义过程与自定义函数一样,都需要先定义后调用。函数一般用于求值，而过程一般实现某些操作，两者的本质区别就是在于：函数有一个值返回，主程序中调用时要有一个相应类型的变量来接收这个值，而过程只是完成某些操作，没有返回值，调用时可以当成完成某项功能的一条命令。,过程的说明,过程说明的一般格式为：,procedure ();/,过程首部,;,begin /,以下是过程体,end;,说明：,过程首部以关键字,procedure,开头。,过程名是用户自定义的标识符，只用来标识一个过程，不能代表任何数据，因此不能说明,过程的类型,。,形参表缺省（当然要同时省去一对括号）时，称为无参过程。,形参表的一般格式形式如下：,var,变量名,1,：类型；,；,var,变量名,n,：类型。,其中带,var,的称为变量形参，不带,var,的称为形参。在函数中，一般都 是形参，很少用变量形参（但可以使用）。例如，下列形参表中：,(x,y:real;n:integer;var w:real;var k:integer;b:real),x,、,y,、,n,、,b,为形参,而,w,、,k,为变量形参。,调用过程时，通过形参给过程提供原始数据，通过变量形参将值带回调用程序。因此，可以说，形参是过程的输入参数，变量形参是过程的输出参数。有关变量形参，这在后面内容具体叙述。,过程体与程序、函数体类似。与函数体不同的是：函数体的执行部分至少有一个语句给函数名赋值，而过程体的执行部分不能给过程名赋值，因为过程名不能代表任何数据。,过程体的说明部分可以定义只在本过程有效的标号、常量、类型、变量、子程序等。,过程的调用,过程调用是通过一条独立的过程调用语句来实现的，它与函数调用完全不同。过程调用与调用标准过程（如,write,read,等）的方式相同。调用的一般格式为：,过程名,或,过程名（实在参数表）,说明：,实参的个数、类型必须与形参一一对应。,对应于形参的实参可以是表达式，对应于变量形参的实参只能是变量。,过程调用的步骤为：计算实参的值；将值或变量的,地址,传送给对应的形参；执行过程体；返回调用处。,过程与函数有下列主要区别：,标识符不同。函数的标识符为,FUNCTION,，过程为：,PROCEDURE,。,函数在定义时一定要进行函数的类型说明，过程则不进行过程的类型说明。,函数有类型，最终要将函数值传送给函数名；过程无类型，不能给过程名赋值。,函数中一般不用变量形参，用函数名直接返回函数值；而过程如有返回值，则必须用变量形参返回。,调用方式不同。函数的调用出现在表达式中，而过程调用是一个独立的语句。,函数通常是为了求一个函数值，而过程可以得到若干个运算结果，也可用来完成一系列的数据处理，或用来完成与计算无关的各种操作；,例,6.8,输出以下一个图形,:,*,*,*,*,*,*,【,分析,】,我们前面学习可用的二重循环打印出上图形,现我们设置一个过程打印出,N,个连续的,*,号。,程序如下,：,Program ex6_8;,var i:integer;,Procedure print(n:integer);/,该过程打印出连续,n,个星号,并换行,var j:integer;,begin,for j:=1 to n do,write(*);,writeln;,end;,BEGIN,for i:=1 to 6 do,print(i);/,调用过程,第,i,行打印,i,个连续星号,END.,例,6.9,使用无参过程，输出由“”组成的矩阵的过程，该矩阵四行五列。,Procedure print;,var i,j:integer;,begin,for i:=1 to 4 do,begin,for j:=1 to 5 do,write(*);,writeln;,end;,end;,该过程就没有参数，直接执行打印一个固定矩阵的任务，而且也没返回值。,例,6.10,定义一个求,N,！的过程。,Procedure js(n:integer);,var s:longint;,i:integer;,begin,s:=1;,for i:=1 to n do,s:=s*i;,writeln(n,!=,s);,end.,在该过程中，它的值的返回形式和函数不一样：函数是由函数名返回，而过程不是由过程名返回的；在过程的首部不用对过程的类型进行说明。,例,6.11,定义过程,fa,求,N!,。,Program ex6_11;,var x:integer;t:real;,Procedure fa(n:integer);,var i:integer;,begin,t:=1;,for i:=2 to n do,t:=t*i;,end;,BEGIN,read(x);,fa(x);,writeln(x:5,t:8);,END.,这里通过全程变量,T,，将过程中计算结果传递到,T,变量中。,Fa(x),仅仅作为程序中的一条命令被执行。,变量形参,在过程定义的语句中，有个参数表，在参数表中，除了前面我们已用的形参，还有变量形参。变量形参的作用是：它可以作为过程的出口参数。我们可以把过程中求出的结果用变量形参输出到过程外，在过程外面可以调用该参数，因此，该参数是全局变量。其格式上的区别是在变量形参前加上,var,即可。那么我们现在来求,1,！,2,！,3,！,10,！？,例,6.12,求,1!+2!+10!,的值。,程序如下：,Program ex6_12;,Var j:integer;,s,m:longint;,Procedure js(n:integer;var m:longint);,Var i:integer;,begin,m:=1;,for i:=1 to n do,m:=m*i;,end;,BEGIN,s:=0;,for j:=1 to 10 do,begin,js(j,m);,s:=s+m;,end;,writeln(s=,s);,END.,在本例中。我们看到，过程,js,中用到了变量形参,m,，在过程中定义为,longint,类型；而在主程序的变量说明中也得对变量形参,m,说明为同种类型,longint,。于是，在过程中和主程序中都可以用该变量了。,形参与变量形参,（,1,）,形参：,在函数或过程定义中，没有加,VAR,说明的参数，在调用函数或过程时，调用程序将实参的值直接传递给形参，起着赋值作用。,（,2,）,变量形参：,在函数或过程定义中，加有,VAR,说明的参数，在调用函数或过程时，调用程序将实参的变量地址传递给变量形参，因此当过程或函数处理中，改变变量形参的值，则实参的变量值也随之改变。（共享同一个存储单元）,例,6.13,下列程序中的参数传递,程序如下：,Program ex6_13;,var x,n:integer;,procedure chan(x:integer;var y:integer);,begin,x:=x+5;,y:=y+5;,writeln(x=,，,x,，,y=,，,y);/,语句,end;,BEGIN /,主程序,x:=10;,n:=10;,writeln(x=,，,x,，,n=,，,n);/,语句,chan(x,，,n);,writeln(x=,，,x,，,n=,，,n);/,语句,END.,运行结果：,x=10 n=10 /,语句的结果,x=15 y=15 /,语句的结果,x=10 n=15 /,语句的结果,过程,chan,中定义了形参,x,和变量形参,y,。在调用过程时，形参,x,接受实参的值,10,，然后将它加,5,，但是形参值的改变并不影响主程序中实参的值（数值传递），所以返回主程序后，输出实参,x,的值仍为,10,，可见，实参,x,和形参,x,是两个不同的变量。,y,为变量形参，对于变量形参的操作实际上就是对相应实参,n,的操作（共享存储地址）。,y,的初值为,10,，调用过程后，值为,15,，返回主程序时，值,15,被带回主程序，故,n,也为,15,。,形参和变量形参的区别：,1,、形参,应该强调的是：,形参和对应的实参必须一一对应，包括个数和类型。,实参和形参之间数据传递是单向的，只能由实参传送给形参，相当赋值运算。,一个特殊情况是，当形参是实型变量名时，对应的实参可以是整型表达式,。,形参作为子程序的局部量，当控制返回程序后，形参的存储单元释放。,2,、变量形参,必须在形参前加关键字,var,。,应该注意的是：,与变量形参对应的实参只能是变量名，而不能是表达式。,与变量形参对应的实参可以根据需要决定是否事先有值。,变量形参与对应的实参的类型必须完全相同。,对变量形参，运行时不另外开辟存储单元，而是与对应的实参使用相同的存储单元。也就是说，调用子程序时，是将实参的地址传送给对应的变量形参。,当控制返回到调用程序后，变量形参的存储单元不释放，但变量形参本身无定义，即不得再使用。,到底是使用形参还是变量形参，应慎重考虑。形参需要另开辟存储空间，而变量形参会带来一些副作用。一般在函数中使用形参，而在过程中才使用变量形参，但也有例外。,例,6.14,写出下列两个程序的运行结果。,Program ex6_14_1;,Program ex6_14_2;,var a,b:integer;,var a,b:integer;,procedure swap(x,y:integer);,procedure swap(var x,y:integer);,var t:integer;,var t:integer;,begin,begin,t:=x;x:=y;y:=t;,t:=x;x:=y;y:=t;,end;,end;,Begin,Begin,a:=1;b:=2;,a:=1;b:=2;,writeln(a:3,b:3);,writeln(a:3,b:3);,swap(a,b);,swap(a,b);,writeln(a:3,b:3);,writeln(a:3,b:3);,End.,End.,【,分析,】,这两个程序唯一的区别是,ex6_14_1,中将,x,y,作为形参，而,ex6_14_2,中将,x,y,作为变量形参，因此在,ex6_14_2,中对,x,y,的修改实际上是对调用该过程时与它们对应的变量,a,b,的修改，故最后，,a,b,的值为,2,，,1,。而,ex6_14_1,中调用,swap,过程时，只是将,a,b,的值传递给,x,y,，之后在过程中的操作与,a,b,无关。,ex6_14_1,的运行结果为：,ex6_14_2,的运行结果为：,1 2,1 2,1 2,2 1,全程变量、局部变量及它们的作用域,全程变量：,主程序中被说明的变量。,局部变量：,在过程或函数中被说明的变量。,在程序中，局部变量、全程变量进行存取的适用范围是不一样的，即作用域不一样。,局部变量的作用域是它们所在的子程序。因形式参数也只在子程序中有效，因此也属于局部变量。,对于局部变量的作用域可以这样理解：当局部变量所在子程序被调用时，局部变量才被分配有效的存储单元；当返回调用程序时，局部变量所占的存储单元就被释放。,全程变量的作用域分为两种情况：,在全程变量和局部变量不同名时，其作用域是整个程序。,在全程变量和局部变量同名时，局部变量屏蔽了全程变量。,例,6.15,变量作用范围：,Program ex6_15;,var x,y:integer;,Procedure doit;,var x:integer;,begin,x:=2;,writeln(x,y);,end;,BEGIN,x:=1;y:=2;,writeln(x,y);,doit;,writeln(x,y);,END.,【,分析,】,程序中,x,y,是全局变量,但在过程,doit,中也定义局部变量,x,，在这种相冲突的情况下，在,doit,过程中的变量,x,是过程中所定义的局部变量。,运行结果：,1 2,2 2,1 2,过程与函数的综合应用,例,6.16,任意输入一个整数，将它变成字符串输出。如：输入数,34567,，打印出字符“,34567”,。要求用过程的方法实现。,程序如下：,Program exp7_16;,var i,k:integer;,s:string;,Procedure n_c(n:integer;var s:string);,Var l:integer;,begin,l:=abs(n);,s:=;,repeat,s:=char(l mod 10)+ord(0)+s;,l:=l div 10;,until l=0;,if n 0 then s:=-+s;,end;,BEGIN,for i:=1 to 10 do,begin,writeln(input k);,readln(k);,n_c(k,s);,writeln(the string is:,s);,end;,END.,例,6.17,编程输入十进制整数,N,（,N,：,-32767,32767,），请输出它对应的二进制、八进制、十六进制数。,【,分析,】,这是一道进行数制转换的问题，将十进制整数转换成,R,进制的数，算法是：除,R,取余，再将余数倒过来写出即是,R,进制的数。本例是要求把一个十进制数同时转换成二进制、八进制、十六进制数。因此可以设计一个过程同进处理这三种数的进制转换。,程序如下：,Program ex6_17;,var n:integer;,Procedure TurnData(n,a:integer);,var x:array1.16 of integer;,i,j,k,h:integer;,begin,writeln(n,turn into,a,:);,if n0 then write(-);/,负数的话，先输出负号再开始转,j:=abs(n);,k:=0;/,用于统计转成,a,进制数后的总位数,repeat,k:=k+1;,i:=j mod a;,j:=j div a;,xk:=i,until j=0;,for h:=k downto 1 do,if xh10 the write(xh),else write(chr(55+xh);/A,的序号是,65,，依次类推,writeln;,end;,BEGIN,readln(n);,TurnData(n,2);/n,转成,2,进制数,TurnData(n,8);/n,转成,8,进制数,TurnData(n,16);/n,转成,16,进制数,END.,这里的过程,TurnData,中的参数不需要把什么值返回给主程序，因此设为形参即可。,例,6.18,对,6,到,60,的偶数验证哥德巴赫猜想：不小于,6,的偶数可分解成两个素数之和。,【,分析,】,用布尔型函数,prime(x),判断,x,是否是素数,若是,函数值为真，否则，函数值为假。算法如下所示。,1,t:=6,2,while t60 do,3,t1:=1;,4,repeat,5,t1:=t1+2;/,找下一个素数,a,6,until prime(t1)and prime(t-t1);/,直到,a,b,都是素数,7,writeln(i,=,t1,+,t-t1);,8,t:=t+2;,9,endwhile,程序如下：,Program ex6_18;,var t,t1:integer;,function prime(x:integer):boolean;/,判断一个数是不是素数,var i:integer;,begin,if x=1 then prime:=false /1,不是素数,else,if x=2 then prime:=true /2,是一素数,else begin,prime:=true;,i:=2;/,从,2,到,x,的根号之间枚举因子,while(i0)do,i:=i+1;,if i=round(sqrt(x)then prime:=false;,end;,end;,BEGIN /,主程序,t:=6;,while t=60 do /,枚举,6,到,60,之间的数,begin,t1:=1;/,枚举其中一个因子,repeat,t1:=t1+2;,until prime(t1)and prime(t-t1);/,直到出现二个因子都是素数,writeln(t,=,t1,+,t-t1);,t:=t+2;,end;,END.,例,6.19,编写一个给一个分数约分的程序。,程序如下：,Program ex6_19;,var a,b:integer;,procedure common(var x,y:integer);/x,y,是变量参数,var i,j,k:integer;,begin /,用辗转相除法求,x,y,的最大公约数,i:=x;,j:=y;,repeat,k:=i mod j;,i:=j;,j:=k;,until k=0;,x:=x div i;/,用两者的最大公约数,i,对,x,y,进行约分,y:=y div i;,end;,BEGIN,readln(a,b);,common(a,b);,writeln(a,b:5);,END.,运行结果：,输入,:12 8,输出,:,3 2,例,6.20,从键盘读取,A,，,B,数组的元素，,A,，,B,数组均已从小到大排好序（无相同元素），现将,A,，,B,合并为数组,C,，同样要求数组,C,也是从小到大排好序（有相同元素时只保留一个）。程序中,n,表示数组,A,，,B,的长度，,i,，,j,，,k,分别表示数组,A,，,B,，,C,的取数或存数的指针,。,program ex6_20,；,const n=8,；,m=2*n,；,type arr1=array 1.n of integer,；,arr2=array 1.m of integer,；,var a,，,b:arr1,；,c:arr2,；,i,，,j,，,k :integer,；,procedure copy(x:arr1,；,var y:arr2,；,var i,，,j:integer),；,begin,i:=i+1,；,yi:=xj,；,j:=j+1,；,end,；,begin,for i:=1 to n do read(ai),；,readln,；,for i:=1 to n do read(bi),；,readln,；,i:=1,；,j:=1,；,k:=0;,while (I=n)and(j=n)do,if aibj then copy(a,，,c,，,k,，,i)/,如果,A,数组值小于,B,数组，,则将,A,赋值到,C,else if bjai then copy(b,，,c,，,k,，,j)/,将,B,赋值到,C,else begin,copy(a,，,c,，,k,，,i),；,/A,与,B,的值相同，指针均加,1,j:=j+1;,end,；,while i=n do copy(a,，,c,，,k,，,i),；,while j=3,）,Program ex6_23,var f0,f1,f2:real;,i,n:byte;,begin,readln(n);,f0:=0;,f1:=1;,for i:=3 to n do,begin,f2:=f0+f1;,f0:=f 1;f1:=f2,end;,writeln(f2:1:0),end.,【,上机练习,6.3】,1,、猴子吃枣问题：猴子摘了一堆枣，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天，又吃了剩下的一半零一个；以后每天如此。到第十天，猴子一看只剩下一个了。问最初有多少个枣子？,2,、任何一个自然数的立方都可以写成一串连续奇数之和。如：,1,3,=1,2,3,=3+5=8,3,3,=7+9+11=27,4,3,=13+15+17+19=64,.,编程输入,N,，求,N3,是由哪些奇数之和。,3,、楼梯有,N,级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递推程序，计算共有多少种不同走法？,4,、兔子在出生两个月以后，就具有生殖后代的能力。假设一对兔子，每月都能生一对兔子，生出来的每一对小兔子，在出生两个月后，也每月生一对兔子。那末，由一对刚出生的小兔子开始，连续不断地繁殖下去，在某个指定的月份有多少对兔子？,5,、骨牌铺法：,有,1n,的一个长方形，用一个,11,、,12,和,13,的骨牌铺满方格。例如当,n=3,时为,13,的方格。此时用,11,、,12,和,13,的骨牌铺满方格，共有四种铺法。如下图：,第四节 递 归,递归概念,当过程或函数的定义中，其内部操作又直接或间接地出现对自身的调用，则称这样的程序嵌套定义为递归定义。,递归是一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。,例如，在数学上，所有偶数的集合可递归地定义为：,0,是一个偶数；,一个偶数与,2,的和是一个偶数。,可见，仅需两句话就能定义一个由无穷多个元素组成的集合。在程序中，递归是通过函数或过程的调用来实现的。函数或过程直接调用其自身，称为直接递归；函数或过程间接调用其自身，称为间接递归。,递归应用,例,6.24,植树节那天，有五位同学参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；,如此，都说比另一位同学多植两棵，最后问到第五位同学时，他说自己植了,10,棵。问第一位同学到底植了多少棵树？,【,分析,】,把原问题求第一位同学的植树棵数,a1,转化为,a1=a2+2,，即求,a2,；而求,a2,又转化为,a2=a3+2;a3=a4+2;a4=a5+2,逐层转化为求,a2,a3,a4,a5,且都采用与求,a1,相同的方法，最后的,a5,为已知值，用,a5=10,返回到上一层并代入计算出,a4,；又用,a4,的值代入上一层去求,a3;,如此,直到求出,a1,。,因此：,10 (x=5),A,x,=,A,x+1,+2 (x5),其中求,Ax+1,又采用求,Ax,的方法。所以,:,定义一个处理问题的子程序,Num(x,),，如果,X 0),【,分析,】,根据数学中的定义把求,x!,定义为求,x*(x-1)!,其中求,(x-1)!,仍采用求,x!,的方法，需要定义一个求,x,！的过程或函数，逐级调用此过程或函数，即：,当,x=0,时，,x!=1,；当,x0,时，,x!=x*(x-1),！。,假设用函数,Fac(x),表示,x,的阶乘，当,x=3,时，,Fac(3),的求解方法可表示为：,Fac(3)=3*fac(2)=3*2*Fac(1)=3*2*1*Fac(0)=3*2*1*1=6,定义函数：,fac(n:integer):integer;,如果,n=0,，则,fac:=1;,如果,n0,，则继续调用函数,fac:=n*fac(n-1);,返回主程序，打印,fac(x),的结果。,它的执行流程如下图所示：,Fac(3),Fac(2),Fac(1),Fac(0),3*Fac(2),2*Fac(1),1*Fac(0),Fac(0)=1,Fac(3),采用函数编写程序如下：,Program ex ex6_25_1;,Var x:integer;,Function fac(n:integer):integer;/,函数,fac(n),求,n!,begin,if n=0 then fac:=1,else fac:=n*fac(n-1)/,调用函数,fac(n-1),递归求,(n-1)!,end;,BEGIN,readln(x);,writeln(x,!=,fac(x);/,主程序调用,fac(x),求,x!,END.,采用过程编写程序如下：,Program ex6_25_2;,var x:integer;t:longint;,Procedure fac(x:longint);,begin,if x=1 then t:=1,else begin,fac(x-1);,t:=t*x;,end;,end;,BEGIN,read(x);,fac(x);,writeln(t);,END.,例,6.26,用递归算法求,X,n,。,【,分析,】,把,X,n,分解成：,X,0,=1,(n=0),X,1,=X*X,0,(n=1),X,2,=X*X,1,(n 1),X,3,=X*X,2,(n 1),(n 1),因此将,X,n,转化为：,X*X,n-1,，其中求,X,n-1,又用求,X,n,的方法进行求解。,定义子程序,cf(n:integer),求,Xn,;,如果,n 1,则递归调用,cf(n-1),求,Xn-1,;,当递归调用到达,n=0,时终止调用,然后执行本“层”的后继语句,;,遇到子程序中的,END,就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后继语句,;,继续执行步骤，从调用中