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

1,计算机程序设计基础,第五讲函数,2,三、数组,问题：编程求解,现假定n=6，k=4我们用函数来编写这个题的程序，参考程序如下：,#include/预编译命令#definen6/定义n为6#definek4/定义k为4voidmain()/主函数/主程序开始printf(sumof%dthpowersofintegersfrom1to%d=,k,n);/提示信息printf(%dn,SOP(n,k);/输出结果,其中/SOP(n,k)为被调用函数/主程序结束,3,/以下函数是被主程序调用的函数intSOP(m,l)/整型自定义函数,m,l为形参intm,l;/形参m,l为整型变量/自定义函数体开始inti,sum;/整型变量i,sumsum=0;/初始化累加器for(i=1;i=m;i=i+1)/计数循环(i)/循环体开始sum=sum+power(i,l);/累加/循环体开始return(sum);/返回值sum给函数sop(n,k)/自定义函数体结束/以下函数是被函数sop(n,k)调用的函数intpower(p,q)/整型自定义函数intp,q;/形参p,q为整型变量/自定义函数体开始inti,product;/整型变量product=1;/初始化累乘器for(i=1;i1时，A的取值即C的值，而C的值即E的值，为了求得E的值，需要先求出D的值。D值fact(n-1)乘以n即为E的值。,15,与结点可能有多个相关联的点，这时可描述为下图,A结点的值最终为D的值，但为了求D需先求B和C。从图上看先求左边的点才能求最右边的点的值，我们约定最右边D点的值就是A结点的值。,16,下面我们以3！为例来画与或结点图，目的是体会递归的含义。,C=1D=2*C=2B=D=2E=3*B=3*2=6A=E=6,17,下面画出了调用和返回的递归示意图,18,从图可以想象：欲求fact(3)，先要求fact(2)；要求fact(2)先求fact(1)。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到1的阶乘，其值为1，到达了递归的边界。然后再用fact(n)=n*fact(n-1)这个普遍公式，从里向外倒推回去得到fact(n)的值。为了把这个问题说得再透彻一点。我们画了如下的流程图：,19,20,为了形象地描述递归过程，将上图改画成下图,21,在这个图中“内层”与“外层”有着相同的结构。它们之间“你中有我，我中有你”，呈现相互依存的关系。为了进一步讲清递归的概念，将递归与递推做一比较。仍以求阶乘为例。递推是从已知的初始条件出发，逐次去求所需要的阶乘值。如求3！初始条件fact(1)=1fact(2)=2*fact(1)=2fact(3)=3*fact(2)=6,22,这相当于从菜心“推到”外层。而递归算法的出发点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的递推关系，这时递归算法就表现出了明显的优越性。下面我们将会看到，递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解，许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处理。下面举一个尽人皆知的例子哈诺（Hanoi）塔问题。,23,故事：相传在古代印度的Bramah庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将64只盘子从一个柱子移至另一个柱子上，所需时间约为5800亿年。,24,怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。,1、在A柱上只有一只盘子，假定盘号为1，这时只需将该盘从A搬至C，一次完成，记为move1fromAtoC,25,2、在A柱上有二只盘子，1为小盘，2为大盘。第（1）步将1号盘从A移至B，这是为了让2号盘能移动；第（2）步将2号盘从A移至C；第（3）步再将1号盘从B移至C；这三步记为：move1fromAtoB;move2fromAtoC;move3formBtoC;,26,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，一次到位。记为move3fromAtoC第（3）步处于B上的作为一个整体的2只盘子，再移至C。这一步记为move(2,B,A,C)意思是将2只盘子作为整体从B借助A移至C。所谓借助是什么意思，等这件事做完了不言自明。,27,28,4、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将1号和2号盘当整体从A移至B的过程中move(2,A,C,B)实际上是分解为以下三步第（1）.1步：move1formAtoC;第（1）.2步：move2formAtoB;第（1）.3步：move1formCtoB;经过以上步骤，将1号和2号盘作为整体从A移至B，为3号盘从A移至C创造了条件。同样，3号盘一旦到了C，就要考虑如何实现将1号和2号盘当整体从B移至C的过程了。实际上move(2,B,A,C)也要分解为三步：第（3）.1步：move1formBtoA;第（3）.2步：move2formBtoC;第（3）.3步：move1formAtoC;,29,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)步，可以将搬移过程用如下的与或结点图表示。,30,这里用与或结点的含义是分解为(1)(2)(3)步。这3步是相关的，相互依存的，而且是有序的，从左至右执行。move(n,A,B,C)分解为3步(1)move(n-1,A,C,B)理解为将上面的n-1只盘子作为一个整体从A经C移至B；(2)输出n：AtoC，理解将n号盘从A移至C，是直接可解结点；(3)Move(n-1,B,A,C)理解为将上面的n-1只盘子作为一个整体从B经A移至C。,31,这里显然是一种递归定义，当着解move(n-1,A,C,B)时又可想到，将其分解为3步：第1步：将上面的n-2只盘子作为一个整体从A经B到C，move(n-2,A,B,C)；第2步：第n-1号盘子从A直接移至B，即n-1:AtoB；第3步：再将上面的n-2只盘子作为一个整体从C经A移至B，move(n-2,C,A,B)；下面，我们还是以3只盘子为例画出递归的与或图。,32,这个图很象一颗倒置着的树，结点move(3,A,B,C)是树根，与结点是树的分枝，叶子都是直接可解结点。,33,34,35,#include/预编