5分而治之-模块化程序设计2

高级语言程序设计第5章分而治之—模块化程序设计（2）复习函数的定义–函数的三要素–函数参数的三要素–函数应该具有单一的功能函数的调用函数的原型函数的功能测试今天要解决的问题问题3:是非问题求解问题4:递归问题求解目标进一步熟悉函数的定义、调用、原型、测试等介绍函数调用的内部过程，自动局部变量和静态局部变量的概念，了解变量的作用域和存储类型理解递归的基本思想问题3是非问题求解常常有是非判断问题：一个数是否是奇数，是否是偶数，是不是素数，是不是完数等一个字符是不是数字，是不是字母，是不是空格等这类问题的特点，把它们用一个函数来实现，作为一个工具，判断一个参数的值是否是什么，该函数的功能只回答是或者不是判断一个数是否是素数的函数函数功能：你传给它一个数，当然应该是自然数，它就会回答你那个数是素数或不是素数。入口参数：一个大于0的整型数返回值：人们所关心的“是”或“不是”这两种状态。怎么表达“是”还是“不是”呢？#includestdbool.h使用bool型或直接使用_Bool或者int/**function:isprimenumberornot?*input:apositiveintegerparameters*output:returnfalseortrue*/boolisPrime(intn){inti,k;if(n==1)returnfalse;if(n==2)returntrue;k=sqrt(n);for(i=2;i=k;i++)if(n%i==0)returnfalse;returntrue;}#includemath.h#includestdio.h#includestdbool.hboolisPrime(intn);intmain(void){intn;printf(pleaseinputanaturalnumber:);scanf(%d,&n);if(n0){if(isPrime(n))printf(%disaprimenumber\n,n);elseprintf(%disnotaprimenumber\n,n);}elseprintf(inputerr!\n);return0;}函数调用的内部过程我们知道一个函数调用另一个函数的时候,实参和形参之间有一个传递过程(单向的传值),只有经过这个过程,形参变量才有真正的值被调用函数执行之后能正确地返回到调用处继续执行下面的语句,你知道计算机内部是怎么做到这一点的吗?我们需要研究两个问题：一个是局部变量(形参变量和函数内部定义的一些变量)的基本特征—存储期(生命期)/作用域问题，另一个是函数调用堆栈的概念。先看一个小程序auto.c#includestdio.hvoidfunction(void);intmain(void){intifor(i=1;i=10;i++)function();return0;}voidfunction(void){inti=0;printf(%d\n,++i);}结果是什么？局部变量每个函数内部定义的变量称为局部变量到现在为止，我们定义的局部变量都是具有自动存储期，简称自动变量“自动”的含义是什么？当进入定义它们的程序块时自动申请内存而建立，当退出该程序块时自动撤销所申请的内存而消失。自动变量的定义方式我们熟悉的变量定义形式类型名变量名实际上省略了自动存储类别autoauto类型名变量名例如：autointnumber；省略为intnumber；存储类别(包括四种：自动auto，静态static，外部extern和寄存器register)，再看一个例子Localvariable.c在不同块中的变量s，虽然它们的名字相同，但是它们的意义截然不同。它们各自有自己的生命周期（存储期）它们有不同的作用域，在一个程序块中从变量声明语句开始到块结束为止的是该变量的作用域，以后还可以看到具有文件作用域的变量（外部变量，全局变量）当块嵌套时同名变量在外层是隐藏的，直到内层执行完毕为止如果要一个局部变量的生命周期不是在块结束时结束生命，让它的生命一直延续到程序结束时才结束怎么办呢？局部静态存储变量简称静态变量，staticintnumber;number变量就是具有静态存储期的变量它的“静”体现在从程序开始执行时就存在，一直保持到程序退出时才终止它的生命。这种类型的变量是在程序开始执行时一次性分配内存并初始化的。再看一段小程序static.c#includestdio.hvoidfunc(void);intmain(void){inti;for(i=1;i=10;i++)func();return0;}voidfunc(void){staticinttimes;printf(“%d\n,++times);}times变量在程序开始运行时就存在了,并自动初始化为0,当每次调用结束时times不会消亡,直到整个程序运行结束时它才消亡.虽然times的生命周期比较长但是它的作用域仍然是局部的全局变量变量可不可以在函数外部定义？可以全局变量从定义地方开始，后面所有已经声明的函数均可以访问全局变量自动初始化为0。例如global.c函数调用堆栈函数定义不允许嵌套，但是函数调用是可以嵌套的也就是说一个函数在调用另一个函数期间，还没返回的时候，另一个函数可以再调用第三个函数，。。。一个函数在调用另一个函数的时候会形成一个函数调用记录，其中包含：被调用函数执行完毕返回时的地址被调用函数的局部自动变量，包括形参并把这个记录压入到一个函数调用堆栈中，因此也把这个记录称为栈帧（stackframe）当一个被调用函数执行完毕返回时，会从函数调用堆栈中弹出一个栈帧，找到返回地址，丢弃被调用函数的局部自动变量（包括形参）堆栈的特点:先进后出看一个函数调用嵌套的例子已知直角三角形的两条直角边a,b,求它的斜边hypot(hypotenuse)，可以先求出斜边的平方hypot2=square(a)+square(b)把它定义为一个函数hypot2(intx,inty)这个函数在计算斜边平方的时候又嵌套调用了square函数#includestdio.h#includemath.hdoublehypot2(doublea,doubleb);doublesquare(doublea);intmain(void){doublex=3,y=4;doublez2;z2=hypot2(x,y);printf(right_angle:%.1fand%.1f,hypotenuseis%.1f,x,y,sqrt(z2));return0;}doublehypot2(doublea,doubleb){doubles,t;s=square(a);t=square(b);return(s+t);}doublesquare(doublea){return(a*a);}R1操作系统调用main()开始执行程序第一步R1intmain(void){doublex=3,y=4;h2=hypot2(x,y)…return0;}第二步R2R1doublehypot2(doublea,doubleb){s=square(a);t=square(b);return(s+t);}第三步R2R3doublesquare(doublea){return(a*a);}第四步被调用函数square执行完毕返回时，从调用堆栈弹出记录R3找到返回地址，释放形参和局部变量。在调用main函数时，先把函数调用记录R1压入堆栈被调用函数hypot执行完毕后，先从调用堆栈弹出记录R2找到返回地址，释放形参和局部变量。在执行main时,又调用hypot2函数，同样先把函数调用记录R2压入堆栈被调用函数main执行完毕后，先从调用堆栈弹出记录R1找到返回地址，释放形参和局部变量。在执行hypot2时又调用square函数，同样先把函数调用记录R3压入堆栈函数调用过程注意程序中是两次调用square，也就是调用square有两次栈帧入栈，两次栈帧出栈，图中只画了一次问题4：递归问题求解很多问题可以通过反复迭代来解决也可以通过逐步递归来解决例如：阶乘计算n!=1×2×3×…×(n-1)×n的迭代公式是fac=fac×i，i=1，2，3，…,n测试阶乘问题的递归描述阶乘问题的递归定义如下递归定义由两部分组成特殊情况：n=0时为1，是非常简单的情况，结果很显然，称为基本情况；一般情况：n0时，n!计算转换为一个比原始问题规模较小与原始问题类似的（n-1）！与n的乘积5.4.2递归函数printf(“%lld\n”,fact(3));分析上例迭代的次数递归与迭代的比较–递归调用的过程，调用堆栈趣味题：汉诺塔(Hanoi)问题传说在远东的一个寺庙里，有三根木桩，其中一个木桩上套有64个盘子，它们从下到上一个比一个小，僧侣们要把它们移动到另一个木桩上去，要求每次只能移动一个盘子，而且保证小的在上大的在下，移动时可以借助第三根木桩。僧侣们最初遇到这个问题时陷入了困境，无法解决，互相推卸任务，最后到推导了寺庙的住持身上。聪明的住持对副住持说，你只要能把前63个盘子由第一个移到第二根上，我就可以完成64个盘子的移动。副住持对另一个僧侣说，你只要能把前62个盘子由第一个桩移到第二根上，我就可以完成63个盘子的移动。……第63个僧侣对第64个僧侣说，你能把1个盘子由第一个桩移到第二根上，我就能实现2个盘子的移动。第64个僧侣很容易地实现了将1个盘子由第一个桩移到第二根上的任务，第63个僧侣也很容易的实现了将2个盘子由第一个桩移到第二根上的任务，……，最后寺庙的住持就很容易地实现了将64个盘子由第一个桩移到第二根上的任务。ABCABCABCABC第一步:n-1个盘子借助B从A到C第三步:n-1个盘子借助A从C到B第二步:第n个盘子从A到B图5.28汉诺塔递归移动过程思考题把下列问题用递归描述1.假设只知道加法运算，计算6*4？2.把一组单词倒排如helloworld变成worldhello。