《第8讲模块程序设计(下)概要》由会员分享，可在线阅读，更多相关《第8讲模块程序设计(下)概要（54页珍藏版）》请在金锄头文库上搜索。
1、第8讲 模块程序设计-函数(下） 黄永峰 2016.11.11,参考教材第4章中4.10-4.16,让真实的问题来驱动学习，让认知的逻辑代替学科轨道，让思维训练优先于技巧的训练,重要通知,第10周（14号开始）。分组及其考试时间按二级选课时间(5个单元时间）安排。下午13：30准备，14：00正式开考； 晚上18：30准备，19：00正式开考；考试为1小时，最多延时半小时，到时间必须交卷 范围：1-6讲中的内容（到分支结构和循环结构为止 ）。2道题 评分标准：1小时内正确10分，可多次验收但每验收错误一次扣一分；1小时后每延时15分钟扣1分，延时半小时未完成酌情给分,本讲内容 函数递归调用 变
2、量的存储类型 文件包含 宏定义,8.1 递归调用算法,例. 求Fibonacci数列：1，1，2，3，5，8，的前40个数，即：F1 = 1(n = 1)，F2 = 1(n = 2)。 Fn = Fn-1 + Fn-2(n3) 算法：,使用循环结构设计递推算法,f3,f4,f5,递推法：从初值出发，根据新值与旧值之间关系,通过循环计算得出最后值,因此,一般通过循环控制结构来实现（循环的终值是最后值）,8.1 递归调用算法 -回顾程序执行过程,8.1 递归调用算法,函数调用时：主调函数出现断点，保存断点信息（压栈），转入到执行被调函数；当被调函数执行完，返回到主调函数断点恢复断点(弹栈），继续执
3、行主调函数,函数调用时的断点保护与恢复,8.1 递归调用算法,递归调用的概念 直接递归：func函数自己调用函数本身 间接递归：f1函数调用f2函数，而f2函数又调用f1,8.1 递归调用算法,函数递归调用必须有退出机制。如果没有退出机制，函数的递归调用将导致无终止的自身调用，最终导致函数调用堆栈溢出而死机 递归程序2个条件：边界条件和递归关系。递归关系实现函数自我调用；边界条件保证递归调用是有限次数终止 递归法：从假设结果出发，归纳出后一结果与前一结果直到初值为止所存在的关系（断点保护）；然后通过断点恢复，根据初始值和关系，反推出真实结果 许多实际问题不可能或不容易找到显而易见的递推关系，因
4、此，无法使用递推算法，这时递归算法就表现出了明显的优越性 几乎所有的循环结构都可以用递归实现。在某些语言中甚至没有循环语句，只有递归,8.1 递归调用算法,生活中的递归,中国老祖宗的递归思想,古之欲明明德于天下者，先治其国；欲治其国者，先齐其家；欲齐其家者，先修其身；欲修其身者，先正其心；欲正其心者，先诚其意；欲诚其意者，先致其知，致知在格物。物格而后知至，知至而后意诚，意诚而后心正，心正而后身修，身修而后家齐，家齐而后国治，国治而后天下平,GNUs Not Unix,8.1 递归调用算法,8.1递归算法,递归算法程序,8.1递归算法,递归编程一般格式,边界条件,递归关系,8.1递归算法,如求
5、n！ 初始条件 1 ！ = 1 2 ！ = 2*1 = 2 3 ！ = 3*2 ！ = 6 . n!=(n-1)!*n Main() int i,n=5; long int fct; for(i=1,fct=1;1=n;i+) fct=fct*i; printf(“%ld”,fct); ,递推法求n!,8.1递归算法,n!=(n1)! n（假设函数f(n)能求n!的值（假设结果），则f(n-1)就能求(n-1)!的值，且f(n)= n f(n-1) ） (n1)!= (n2)! (n1) f(n-1)= n f(n-2) (n2)!= (n3)! (n2) f(n-2)= n f(n-3) (
6、n3)!= (n4)! (n3) 2!=12（边界条件） 递归程序的两阶段执行过程： 回推调用（压栈）：欲求n! 先求 (n-1)! (n-2)! 1!。若1！已知，回推结束 回代计算（弹栈）：知道1！2！3！ n！ 因此：设计一个函数（递归函数），这个函数不断使用下一级值调用自身，直到到达边界条件（结果已知处）,用递归法求n！,8.1递归算法,用递归算法求n! 定义：函数 fact(n) = n! fact(n-1) = (n-1)! 则有fact(n) = n*fact(n-1)(递推关系) 已知fact(1) = 1(边界条件),下面是函数调用和返回的递归示意图（体会函数调用的断点压栈保
7、护和恢复的概念）,断点1,断点2,Fact(n)函数发生3次递归调用，产生了2次断点,从图可以想象：欲求fact(3)，先要求fact(2)；要求fact(2)先求fact(1)。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到1的阶乘，其值为1，到达了递归的边界。然后再用fact(n) =n*fact(n-1)这个普遍公式，从里向外倒推回去得到fact(n)的值。 为了把这个问题说得再透彻一点。我们画了如下的流程图：,8.1递归算法,8.1递归算法,断点,断点,8.1递归算法,函数调用调试界面,8.1递归算法,【例】有5个人，第5个人说他比第4个人大2岁，第4个人说他比第3个人大2岁
8、，第3个人说他比第2个人大2岁，第2个人说他比第1个人大2岁，第1个人说他10岁。求第5个人多少岁。 分析： 10 (n=1) age(n)= age(n-1)+2 (n1),8.1递归算法,【例】反向输出一个整数。 非数值问题不容易像数值问题那样能得出一个边界条件和递归函数关系，但思路是相同的。分析方法： 简化问题：设要输出的正整数只有1位，则“反向输出”问题可简化为输出1位整数。（边界条件） 对大于10的正整数，逻辑上可分为两部分：个位数字和个位以前的全部数字。将个位以前的全部数字看成一个整体，则为了反向输出这个大于10的正整数，可按以下步骤： a.输出个位上的数字； b.将个位除外的数字
9、作为一个新的整数，重复上述步骤。 因此,b问题只是对原问题在规模上进行了缩小递归。所以，可将反向输出一个正整数的算法归纳为： if （n为一位整数） 输出n； else 输出n的个位数字； 对剩余数字组成的新整数重复“反向输出”操作；,8.1递归算法,8.1递归算法,#include rev() char c; c=getchar(); if (c=$) printf(“%c“,c); else rev(); printf(“%c“,c); main() rev();,若输入AB$CDE 则输入结果为：?,分析下列程序的结果,8.1递归算法,分析结果：$BA,3.5.4 循环嵌套,计算sin(
10、x) = x - x3/3! + x5/5! - x7/7! + 直到最后一项的绝对值小于10-7时,停止计算。x由键盘输入 基本思想： 设自变量为x，和为sum，每一项为 temp 定义常量为eps，其值为：10-7 由计算公式可知，第N项为(-1）N+1*x2N-1/(2N-1）！ 第N-1项为(-1）N * x 2N-3 /（2N-3）！ 两相之间相差一个因子：-x2 /(2N-2)*(2N-3) 算法重点:内、外循环条件和循环体的设计,3.5.4 循环嵌套,#include #include double sin(double); double nResult(double,doubl
11、e); int main() double x=0; scanf(“%lf“,double sin(double x) /sin(x)=x-x3/3!+x5/5!- +(-1)(n2n+1)/(2n+1)!+ int i=0; double result=0,n=0; while(fabs(n=nResult(x,2*+i-1) ) 0e-5 ) result+=(i%2=1)?n:-n; return result;,double nResult(double x, double n) return n=1?x:nResult(x,n-1)*x/n;,递归：(n2n+1)/(2n+1)!=n
12、/1*n/2*n/3*n/4*.n/(2n+1),8.2 变量的存储类型,变量和函数的两个基本属性 数据类型：int, char, float 存储类型:auto, statc, register, extern 变量定义的完整格式： 存储类别 数据类型 变量名 如 static int x,y ; 用户程序在内存中分三个区域存储：,8.2 变量的存储类型,register型:变量值存放在运算器的寄存器中存取速度快.且限于char型和int型，通常用于循环变量 auto型:变量值存放在主存储器的动态存储区,在运行中动态分配和释放 static型：变量值存放在主存储器的静态存储区，程序执行开始至
13、结束其值都存在，始终占用存储空间 extern型（外部变量型）：同static，其值可供其他源文件使用 未说明存储类别时，函数内定义的变量为auto型，函数外定义的变量为extern型,存储类别标识符,8.2 变量的存储类型,存储类型：决定变量存储区域的分配方式(静态或动态)、变量生命周期，及变量初始化值及方式 生命周期：变量存储单元存在的周期，即时间有效性（何时分配和释放） 初始化值：是否有缺省值 变量定义位置：决定了变量的作用域（文件域、函数域和复合语句域） 全局变量：函数外定义 局部变量：函数或块内定义 变量定义位置与存储类型相关；也可以用存储类别标识符来指明存储类型,【例】编函数将以秒
14、为单位的时间值转化成“时：分：秒”形式。要求:输入和输出在主函数完成,转换由该函数完成,算法重点:全局变量的初始化和作用-函数间通信 提问：回顾一下，犀利哥编写的游戏程序中为什么需要使用全局变量：win_count;lost_count;tie_count?,8.2 变量的存储类型,算法重点:全局（外部）变量引用说明,算法重点:局部变量的作用范围和生存期,8.2 变量的存储类型,a i b c f(a) 2 0 01 4 7 1 01 5 8 2 01 6 9,8.2 变量的存储类型小结,算法重点：说明静态全局变量与全局变量的区别,提问：如要得到该结果，如何修改？,提问：为什么出错？,8.2
15、变量的存储类型小结,auto（默认）:局部变量，所在函数调用分配空间，结束时自动释放 Static+局部变量。用来改变变量存储类型。函数调用结束时，其值仍保留。作用范围局限定义的语句块内。在第一次进入该块时执行一次，且仅执行一次初始化；如不赋初值，取初值为0或空格 static +全局变量:用来限定全局变量作用域。静态全局变量，函数调用结束时，其值仍保留，但只限本源文件中使用 extern（默认）+全局变量:用来扩展全局变量作用域。允许本源文件中其他函数及其他源文件的函数使用。如果要将作用范围扩展到其他源文件，只需在使用这些变量的文件中对变量用extern引用说明,编辑,执行,连接,编译,键盘
16、输入,f 1. cpp f2.cpp,磁盘文件,f1.obj f2.obj,huang. exe,图：编程的4部曲,1.3 C+程序基本结构（回顾）,f1.obj+f2.obj+标准函数huang.exe,huang.vsproj f1.cpp f2.cpp,8.3 文件包含,文件包含 一个C+程序由若干个源文件组成，而一个源文件还可将另一个源文件的全部内容包含进来，二者合为一个大的文件 这个包含进来的文件只是一个文件名，在编译时先进行展开 一般形式为： include include 文件名,提示：回顾一下犀利哥编写的游戏程序中game.h,预处理命令 在编译前预先处理的命令 宏定义、文件包含和条件编译,8.3 文件包含,一般#include命令用于包含扩展
