计算机语言与程序设计函数

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,计算机程序设计基础,第五讲 函数,1,三、数组,问题：编程求解,现假定,n=6,，,k=4,我们用函数来编写这个题的程序，参考程序如下：,#include /,预编译命令,#define n 6 /,定义,n,为,6,#define k 4 /,定义,k,为,4,void main()/,主函数,/,主程序开始,printf(sum,of%,dth,powers of integers from 1 to%d=,k,n,);,/,提示信息,printf(%dn,SOP(n,k,);/,输出结果,其中,/,SOP(n,k,),为被调用函数,/,主程序结束,2,/,以下函数是被主程序调用的函数,int,SOP(m,l,)/,整型自定义函数,m,l,为形参,int,m,l,;/,形参,m,l,为整型变量,/,自定义函数体开始,int,i,sum,;/,整型变量,i,sum,sum=0;/,初始化累加器,for(i=1;i=m;i=i+1)/,计数循环,(i),/,循环体开始,sum=,sum+power,(i,l);/,累加,/,循环体开始,return(sum);/,返回值,sum,给函数,sop(n,k,),/,自定义函数体结束,/,以下函数是被函数,sop(n,k,),调用的函数,int,power(p,q,)/,整型自定义函数,int,p,q,;/,形参,p,q,为整型变量,/,自定义函数体开始,int,i,product,;/,整型变量,product=1;/,初始化累乘器,for(i,=1;i=q;i=i+1)/,计数循环,(i),/,循环体开始,(i),product=,product,*p;/,累乘,/,循环体结束,(i),return(product,);/,累乘值,product,返回给,power,/,自定义函数体结束,3,自定义函数,(),例,:,int,power(p,n,),power,为函数名，要以英文字母开头。,int,是函数值的数据类型，这里是,int,（整型）。,(,p,n,),括号中的,p,n,为函数的形式参数，形式参数也要定义其数据类型。,函数定义的一般格式：,(),为了突出重点，先学会基本东西，省略掉一些事情先不讲。,4,1,、形式参数是在定义函数时放在函数名后括号中的参数。在未进行函数调用时，并不对形式参数分配内存单元。在发生函数调用时，立刻给形式参数分配内存单元。调用结束后，释放掉行参所占的内存单元。,2,、因此，形参变量属于局部变量，其作用域在它所在的函数体内。,3,、在定义函数的时候，必须指定形参变量的类型，如何指定？有二种方法：,形式参数与实在参数,(1),int,power(p,n,),int,p,n,;,(2),int,power(int,p,int,n),有些编译系统不认识第（,2,）种形式,5,4,、实在参数是一个具有确定值的表达式。函数在调用时，将实在参数赋给形式参数。,比如，主函数调用,SOP(n,k,),，这时，,n,k,为实在参数，,n,的值为,6,，,k,的值为,4,。在被调用函数定义中，,int,SOP(m,l,),中的,m,l,为形式参数，在,SOP,被调用时，系统给,m,l,这两个形式参数分配了内存单元。之后，,n,的值,6,赋给,m,，,k,的值,4,赋给,l,。,实在参数的个数及类型应与形式参数一致。赋值时前后对应关系不会改变。下面画出主函数与,SOP,函数，调用与被调用时参数传递关系：,6,主函数执行下述语句时，,printf(“%dn”,SOP(n,k,);,传值给被调用函数,int,SOP(m,l,),n,的值,6,传给,m,k,的值,4,传给,l,。,6,和,4,为实在参数，,m,和,l,为形式参数。,被调用函数在其形式参数被赋值之后，开始执行函数体，先是让累加器初始化为,0,（,sum=0,），接着进入以,i,为控制变量的计算循环，,i,从,1,变到,m,（,m=6,），即累加,m,次（即,6,次）。循环体为,sum=,sum+power(i,l,),。当,6,次循环执行完后，实现的是,注意这里 是由另一个自定义函数,power(i,l,),实现的。,7,power(i,l,),处在,SOP(m,l,),函数中，表示,SOP,函数去调用,power,函数。其中,i,l,为实在参数，而,int,power(p,q,),中的,p,q,为形式参数。,比如，执行,SOP(6,4),时，,l=4,m=6,当,i=1,时，,sum=sum+power(1,4),这里,1,，,4,为实在参数，调用,power(p,q,),，两个形式参数,p,q,分别被赋以,1,，,4,。,8,9,递归算法,在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。,我们先从一个最简单的例子导入。,递归及其实现,用递归算法求,n!,定义：函数,fact(n,)=n!,fact(n-1)=(n-1)!,则有,fact(n,)=n fact(n-1),已知,fact(1)=1,10,为了表述得直观清晰，我们定义两个结点：,或结点,与,与结点。,图示的直观性与思维助力。,1,、或结点,A,为“或结点,”,，,A,依不同条件会有两种不同的取值,B,或,C,。结点用 表示。,11,如果有多于,2,种取值，可用下图：,条件为,Z1,Z2,Zn,，取值为,B,或,C,或,G,12,2,、与结点,与结点要涂黑，相关联的,B,与,C,之间要用弧线连起来。,A,为与结点，,A,的最终取值为,C,结点的值，但为了求得,C,的值，得先求出,B,结点的值，,C,是,B,的函数。,13,仍以求,n!,为例画出如下与或图,A,为或结点；,B,为直接可解结点，值为,1,；,C,为与结点，当,n1,时，,A,的取值即,C,的值，而,C,的值即,E,的值，为了求得,E,的值，需要先求出,D,的值。,D,值,fact(n-1),乘以,n,即为,E,的值。,14,与结点可能有多个相关联的点，这时可描述为下图,A,结点的值最终为,D,的值，但为了求,D,需先求,B,和,C,。从图上看先求左边的点才能求最右边的点的值，我们约定最右边,D,点的值就是,A,结点的值。,15,下面我们以,3,！为例来画与或结点图，目的是体会递归的含义。,C=1,D=2*C=2,B=D=2,E=3*B=3*2=6,A=E=6,16,下面画出了调用和返回的递归示意图,17,从图可以想象：,欲求,fact(3),，先要求,fact(2),；要求,fact(2),先求,fact(1),。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到,1,的阶乘，其值为,1,，到达了递归的边界。然后再用,fact(n,)=n*fact(n-1),这个普遍公式，从里向外倒推回去得到,fact(n,),的值。,为了把这个问题说得再透彻一点。我们画了如下的流程图：,18,19,为了形象地描述递归过程，将上图改画成下图,20,在这个图中“内层”与“外层”有着相同的结构。它们之间“你中有我，我中有你”，呈现相互依存的关系。,为了进一步讲清递归的概念，将,递归,与,递推,做一比较。仍以求阶乘为例。,递推,是从已知的初始条件出发，逐次去求所需要的阶乘值。,如求,3,！,初始条件,fact(1)=1,fact(2)=,2*fact(1)=2,fact(3)=3*fact(2)=6,21,这相当于从菜心“推到”外层。而,递归,算法的出发点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。,但许多实际问题不可能或不容易找到显而易见的递推关系，这时递归算法就表现出了明显的优越性。,下面我们将会看到，递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解，许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处理。下面举一个尽人皆知的例子,哈诺（,Hanoi,）塔,问题。,22,故事：相传在古代印度的,Bramah,庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把,64,个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将,64,只盘子从一个柱子移至另一个柱子上，所需时间约为,5800,亿年。,23,怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。,1,、在,A,柱上只有一只盘子，假定盘号为,1,，这时只需将该盘从,A,搬至,C,，一次完成，记为,move 1 from A to C,24,2,、在,A,柱上有二只盘子，,1,为小盘，,2,为大盘。,第（,1,）步将,1,号盘从,A,移至,B,，这是为了让,2,号盘能移动；,第（,2,）步将,2,号盘从,A,移至,C,；,第（,3,）步再将,1,号盘从,B,移至,C,；,这三步记为：,move 1 from A to B;,move 2 from A to C;,move 3 form B to C;,25,3,、在,A,柱上有,3,只盘子，从小到大分别为,1,号，,2,号，,3,号,第（,1,）步将,1,号盘和,2,号盘视为一个整体；先将二者作为整体从,A,移至,B,，给,3,号盘创造能够一次移至,C,的机会。这一步记为,move(2,A,C,B),意思是将上面的,2,只盘子作为整体从,A,借助,C,移至,B,。,第（,2,）步将,3,号盘从,A,移至,C,，一次到位。记为,move 3 from A to C,第（,3,）步处于,B,上的作为一个整体的,2,只盘子，再移至,C,。这一步记为,move(2,B,A,C),意思是将,2,只盘子作为整体从,B,借助,A,移至,C,。,所谓,借助,是什么意思，等这件事做完了不言自明。,26,27,4,、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将,1,号和,2,号盘当整体从,A,移至,B,的过程中,move(2,A,C,B),实际上是分解为以下三步,第（,1,）,.1,步：,move 1 form A to C;,第（,1,）,.2,步：,move 2 form A to B;,第（,1,）,.3,步：,move 1 form C to B;,经过以上步骤，将,1,号和,2,号盘作为整体从,A,移至,B,，为,3,号盘从,A,移至,C,创造了条件。同样，,3,号盘一旦到了,C,，就要考虑如何实现将,1,号和,2,号盘当整体从,B,移至,C,的过程了。实际上,move(2,B,A,C),也要分解为三步：,第（,3,）,.1,步：,move 1 form B to A;,第（,3,）,.2,步：,move 2 form B to C;,第（,3,）,.3,步：,move 1 form A to C;,28,5,、看,move(2,A,C,B),是说要将,2,只盼自从,A,搬至,B,，但没有,C,是不行的，因为第（,1,）,.1,步就要将,1,盘从,A,移到,C,，给,2,盘创造条件从,A,移至,B,，然后再把,1,盘从,C,移至,B,。看到这里就能明白借助,C,的含义了。因此，在构思搬移过程的参量时，要把,3,个柱子都用上。,6,、定义搬移函数,move(n,A,B,C),，物理意义是将,n,只盘子从,A,经,B,搬到,C,考虑到前面已经研究过的,(1)(2)(3),步，可以将搬移过程用如下的与或结点图表示。,29,这里用与或结点的含义是分解为,(1)(2)(3),步。这,3,步是相关的，相互依存的，而且是有序的，从