《计算机程序设计：第8讲模块程序设计(下)》由会员分享，可在线阅读，更多相关《计算机程序设计：第8讲模块程序设计(下)（50页珍藏版）》请在金锄头文库上搜索。
1、1第8讲 模块程序设计-函数(下）让让真真实实的的问问题题来来驱驱动动学学习习，让让认认知知的的逻逻辑辑代代替替学科轨道，让思维训练优先于技巧的训练学科轨道，让思维训练优先于技巧的训练2重要通知l第10周全周的上机实验时间进行分组机考。分组及其考试时间按二级选课时间(5个单元时间）安排l范围：1-6讲中的内容（到分支结构和循环结构为止 ）。两道题，10分l请相互通知3主要内容l函数递归调用l变量的存储类型l文件包含l宏定义48.1 8.1 递归调用算法递归调用算法例例. . 求求FibonacciFibonacci数列：数列：1 1，1 1，2 2，3 3，5 5，8 8，.的前的前4040个
2、个数，即：数，即：F1 = 1(n = 1)F1 = 1(n = 1)F2 = 1(n = 2).Fn = Fn-1 + Fn-2(n3)F2 = 1(n = 2).Fn = Fn-1 + Fn-2(n3)算法：算法：p使用循环结构设计递推算法使用循环结构设计递推算法f3f4f55n递推法递推法：从初值出发，根据新值与旧值之间：从初值出发，根据新值与旧值之间关系关系, ,通过通过循环计算循环计算得出最后值得出最后值, ,因此因此, ,一般通过循环控制结构来实一般通过循环控制结构来实现（循环的终值是最后值）现（循环的终值是最后值）68.1 8.1 递归调用算法递归调用算法- -回顾程序执行过程回
3、顾程序执行过程78.1 8.1 递归调用算法递归调用算法p函数调用时：主调函数出现断点，函数调用时：主调函数出现断点，保存断点信息保存断点信息（压栈）（压栈），转入到执行被调函数；当被调函数执行完，返回到主，转入到执行被调函数；当被调函数执行完，返回到主调函数断点调函数断点恢复断点恢复断点(弹栈）弹栈），继续执行主调函数，继续执行主调函数p函数调用时的函数调用时的断点断点保护与恢复保护与恢复main()main()断点断点调用压栈调用压栈main()main()断点断点调用压栈调用压栈foo()foo()断点断点main()main()断点断点调用弹栈调用弹栈foo()foo()断点断点mai
4、n()main()断点断点调用弹栈调用弹栈88.1 8.1 递归调用算法递归调用算法p递归调用的概念递归调用的概念直直接接递递归归：funcfunc函函数数自自己己调调用函数本身用函数本身间间接接递递归归：f1f1函函数数调调用用f2f2函函数，而数，而f2f2函数又调用函数又调用f1f198.1 8.1 递归调用算法递归调用算法p函函数数递递归归调调用用必必须须有有退退出出机机制制。如如果果没没有有退退出出机机制制，函函数数的的递递归归调调用用将将导导致致无无终终止止的的自自身身调调用用，最最终终导导致致函函数数调调用用堆堆栈栈溢出而死机溢出而死机p递递归归程程序序2个个条条件件：边边界界条
5、条件件和和递递归归关关系系。递递归归关关系系实实现现函函数数自我调用自我调用；边界条件保证递归调用是；边界条件保证递归调用是有限次数终止有限次数终止p递递归归法法：从从假假设设结结果果出出发发，归归纳纳出出后后一一结结果果与与前前一一结结果果直直到到初初值值为为止止所所存存在在的的关关系系（断断点点保保护护）；然然后后通通过过断断点点恢恢复复，根据根据初始值和关系初始值和关系，反推出，反推出真实结果真实结果p许许多多实实际际问问题题不不可可能能或或不不容容易易找找到到显显而而易易见见的的递递推推关关系系，因因此此，无无法法使使用用递递推推算算法法，这这时时递递归归算算法法就就表表现现出出了了明
6、明显显的的优优越性越性p几乎所有的循环结构都可以用递归实现。在某些语言中甚至几乎所有的循环结构都可以用递归实现。在某些语言中甚至没有循环语句，只有递归没有循环语句，只有递归108.1 8.1 递归调用算法递归调用算法n生活中的递归118.1 8.1 递归调用算法递归调用算法128.18.1递归算法递归算法p递归算法程序递归算法程序138 8. .1 1递归算法递归算法n递归编程一般格式递归编程一般格式边界条件边界条件递归关系递归关系148.18.1递归算法递归算法如求如求n！初始条件初始条件 1 ！ = 12 ！ = 2*1 = 23 ！ = 3*2 ！ = 6. n!=(n-1)!*nMai
7、n()int i,n=5;long int fct; for(i=1,fct=1;11)228.18.1递归算法递归算法23【例】反向输出一个整数。 非数值问题不容易像数值问题那样能得出一个边界条件和递归函数关系，但思路是相同的。分析方法：简化问题：设要输出的正整数只有1位，则“反向输出”问题可简化为输出1位整数。（边界条件）对大于10的正整数，逻辑上可分为两部分：个位数字和个位以前的全部数字。将个位以前的全部数字看成一个整体，则为了反向输出这个大于10的正整数，可按以下步骤： a.输出个位上的数字； b.将个位除外的数字作为一个新的整数，重复上述步骤。 因此,b问题只是对原问题在规模上进行了
8、缩小递归。所以，可将反向输出一个正整数的算法归纳为： if （n为一位整数） 输出n； else 输出n的个位数字； 对剩余数字组成的新整数重复“反向输出”操作；8.1递归算法递归算法248.1递归算法递归算法25#include rev() char c; c=getchar(); if (c=$) printf(%c,c); else rev(); printf(%c,c); main()rev();l若输入AB$CDE则输入结果为：?p分析下列程序的结果8.1递归算法递归算法分析结果：$BA268.2 变量的存储类型l变量和函数的两个基本属性变量和函数的两个基本属性数据类型：数据类型：i
9、nt, char, floatint, char, float存储类型存储类型:auto, statc, register, extern:auto, statc, register, externl变量定量定义的完整格式：的完整格式： 存储类别存储类别 数据类型数据类型 变量名变量名 如如 static int x,ystatic int x,y ; ;l用户程序在内存中分三个区域存储：用户程序在内存中分三个区域存储：代码区代码区静态数据区静态数据区动态数据区动态数据区278.2 变量的存储类型registerregister型型: :变变量量值值存存放放在在运运算算器器的的寄寄存存器器中中
10、存存取取速速度度快快. .且限于且限于charchar型和型和intint型，通常用于循环变量型，通常用于循环变量autoauto型型: :变变量量值值存存放放在在主主存存储储器器的的动动态态存存储储区区, ,在在运运行行中中动态分配和释放动态分配和释放 staticstatic型型：变变量量值值存存放放在在主主存存储储器器的的静静态态存存储储区区，程程序序执行开始至结束其值都存在，始终占用存储空间执行开始至结束其值都存在，始终占用存储空间externextern型型（外外部部变变量量型型）：同同staticstatic，其其值值可可供供其其他他源源文件使用文件使用未未说说明明存存储储类类别别
11、时时，函函数数内内定定义义的的变变量量为为autoauto型型，函函数数外定义的变量为外定义的变量为externextern型型l存储类别标识符288.2 变量的存储类型l存储类型：决定变量存储区域的分配方式(静态或动态)、变量生命周期，及变量初始化值及方式 生命周期：变量存储单元存在的周期，即时间有效性（何时分配和释放）初始化值：是否有缺省值l变量定义位置：决定了变量的作用域（文件域、函数域和复合语句域）全局变量：函数外定义局部变量：函数或块内定义l变量定义位置与存储类型相关；也可以用存储类别标识符来指明存储类型29【例】编函数将以秒为单位的时间值转化成“时：分：秒”形式。要求:输入和输出在
12、主函数完成,转换由该函数完成p算法重点算法重点:全局变量的初始化和作用全局变量的初始化和作用-函数间通信函数间通信p提问：回顾一下，犀利哥编写的游戏程序中为什么需要使用全局变量：提问：回顾一下，犀利哥编写的游戏程序中为什么需要使用全局变量：win_count;lost_count;tie_count?win_count;lost_count;tie_count?308.2 变量的存储类型p算法重点:全局（外部）变量引用说明31p算法重点:局部变量的作用范围和生存期328.2 变量的存储类型a i b c f(a) 2 0 01 4 7 1 01 5 8 2 01 6 9338.2 变量的存储类
13、型小结p算法重点：说明静态全局变量与全局变量的区别提问：如要得到该结果，提问：如要得到该结果，如何修改？如何修改？提问：为什么出错？提问：为什么出错？34 8.2 变量的存储类型小结pautoauto（默认）（默认）: :局部变量，所在函数调用分配空间，结束时局部变量，所在函数调用分配空间，结束时自动释放自动释放 pStatic+Static+局局部部变量量。用用来来改改变变量量存存储类型型。函函数数调用用结束束时，其其值仍仍保保留留。作作用用范范围围局局限限定定义义的的语语句句块块内内。在在第第一一次次进进入入该该块块时时执执行行一一次次，且且仅仅执执行行一一次次初初始始化化；如如不不赋赋初
14、初值值，取初值为取初值为0 0或空格或空格pstatic static + +全全局局变量量: :用用来来限限定定全全局局变变量量作作用用域域。静静态态全全局局变变量，量，函数函数调用用结束束时，其，其值仍保留，但只限本源文件中使用仍保留，但只限本源文件中使用pexternextern（默默认）+ +全全局局变量量: :用用来来扩扩展展全全局局变变量量作作用用域域。允允许本本源源文文件件中中其其他他函函数数及及其其他他源源文文件件的的函函数数使使用用。如如果果要要将将作作用用范范围围扩扩展展到到其其他他源源文文件件，只只需需在在使使用用这这些些变变量量的的文文件件中中对变量用对变量用exter
15、nextern引用说明引用说明35编辑执行连接编译键盘输入f 1. cppf2.cpp磁盘文件f1.objf2.objhuang. exe图：编程的4部曲1.3 C+程序基本结构（回顾）程序基本结构（回顾）f1.obj+f2.obj+标准函标准函数数huang.exehuang.vsprojf1.cppf2.cpp预编译预编译文法、语法检查文法、语法检查.368.3 8.3 文件包含文件包含 p文件包含文件包含一一个个C+程程序序由由若若干干个个源源文文件件组组成成，而而一一个个源源文文件件还还可可将将另另一一个个源源文文件件的的全全部部内内容容包包含含进进来来，二二者者合合为为一一个个大大的
16、的文件文件这这个个包包含含进进来来的的文文件件只只是是一一个个文文件件名名，在在编编译译时时先先进进行行展开展开一般形式为：一般形式为： include include 文件名文件名 p提示：回顾一下犀利哥编写的游戏程序中提示：回顾一下犀利哥编写的游戏程序中game.hgame.hp预处理命令预处理命令在编译前预先处理的命令在编译前预先处理的命令宏定义、文件包含和条件编译宏定义、文件包含和条件编译378.3 文件包含文件包含 一般#include命令用于包含扩展名为.h的“头文件”，如stdio.h，math.h等。在这些文件中，一般定义符号常量、宏，或声明函数原型；c+头文件没有.hALLO
17、C.HASSERT.HBIOS.HCONIO.HCTYPE.HDIR.HDOS.HERRNO.H FCNTL.HFLOAT.HGRAPHICS.H IO.HLIMITS.HMALLOC.HMATH.HMEM.HPROCESS.HSETJMP.HSHARE.HSIGNAL.HSTDARG.H STDDEF.H STDIO.HSTDLIB.HSTRING.HTIME.HVALUES.H38说明明一个一个includeinclude命令只能指定一个被包含文件，如命令只能指定一个被包含文件，如果要包含果要包含n n个文件，用个文件，用n n个个includeinclude命令命令#include#in
18、clude命令的文件名，可使用两种括号，差异：命令的文件名，可使用两种括号，差异：#include file2.h #include file2.h 先在引用被包含文件的目先在引用被包含文件的目录查找找file2.hfile2.h文件，若没有，再到文件，若没有，再到系统指定的目录查找找 #include #include 仅在系在系统指定的目指定的目录查找文件找文件file2.hfile2.hVCVC中中系统指定目录在在Tools/option/directory/includeTools/option/directory/include中中设置置8.3 文件包含文件包含 39nVC20080
19、系统指定的目录408.4 宏-不带参数的宏l不带参数宏一般形式:#define 标识符(宏名）字符串 如：#define PI 3.14159l在预编译时，将源程序中出现的宏名PI将替换为字符串“3.14159”。该替换过程称为“宏展开”l#define：宏定义命令418.4 宏-不带参数的宏428.4 宏-不带参数的宏l#undef:终止宏定义命令l提问：为什么编译出错？438.4 宏-不带参数的宏p注意：宏不扩展引号中的宏448.4 宏-带参数的宏l带参数的宏一般形式： #define 宏名（参数表） 字符串l带参数的宏在展开时，不是进行简单的字符串替换，而是进行参数替换。l例如：458.
20、4宏-带参数的宏468.4 宏-带参数的宏带参数的宏l例如：例如：#define S(r) PI*r*r#define S(r) PI*r*r area = S(a+b); area = S(a+b); area = PI*a+b*a+b;( area = PI*a+b*a+b;(错误）错误）l带参数的宏展开时，用实参字符串替换形参带参数的宏展开时，用实参字符串替换形参字符串。注意可能发生的错误。比较好的办字符串。注意可能发生的错误。比较好的办法是宏定义的形参加括号法是宏定义的形参加括号l例如例如 #define S(r) PI*(r)*(r)#define S(r) PI*(r)*(r) a
21、rea = S(a+b); area = S(a+b); area = PI*(a+b)*(a+b area = PI*(a+b)*(a+b）；）；478.4 宏-带参数的宏例题：计算机函数值：f(x,y)=x3+x2(y+1)3+(y+1)2,要求从键盘输入x、y#include “stdio.h”#define F(x) (x)*(x)*(x)+(x)*(x)main( )double f,x;coutxy;f=F(x)*F(y+1);cout“f=”f; 提问：是否有问题？提问：是否有问题？p结论：在使用带参数的宏定义时，一般应该将宏定义字符串中的参数和整个 字符串也括起来, 即：#de
22、fine F(x) （(x)*(x)*(x)+(x)*(x)）48本讲重点l递归和递推方法的区别递归和递推方法的区别; ;l变量的存储类型：局部和全局，静态和外部变量的存储类型：局部和全局，静态和外部l文件包含的意义、使用和配置方法、带参数宏文件包含的意义、使用和配置方法、带参数宏49第7次作业练习第第1 1题题: :【约瑟夫问题约瑟夫问题】39 39 个犹太人与约瑟夫躲到山洞，个犹太人与约瑟夫躲到山洞，3939个犹太人决定宁死也不要个犹太人决定宁死也不要被敌人抓到，于是决定了自杀方式，被敌人抓到，于是决定了自杀方式，4040个人排成一个圆圈，由第个人排成一个圆圈，由第1 1个人开始报数，每个
23、人开始报数，每报到第报到第3 3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而约瑟夫并不想死，他站在某个位置上，最终逃过了这场死亡游戏。试问：这个然而约瑟夫并不想死，他站在某个位置上，最终逃过了这场死亡游戏。试问：这个位置是哪编号？要求：位置是哪编号？要求：1.1.分别采用递归和递推法来编程；分别采用递归和递推法来编程；2.2.采用采用或或头文件中的头文件中的clock()clock()来分析这两种方法的来分析这两种方法的CPUCPU耗时，指出耗时，指出 哪种方法更快，并分析其原因。说明：哪种方法更快
24、，并分析其原因。说明： clock()clock()使用参见使用参见“课外资料之三课外资料之三”3.3.调试递归程序，截屏调试递归程序，截屏“调用窗口。调用窗口。第第2 2题：改编犀利哥故事之题：改编犀利哥故事之8 8：筹备彩礼。筹备彩礼。要求：要求：1.1.分别采用函数递归方法编写两个函数（指数模型和分别采用函数递归方法编写两个函数（指数模型和FibonacciFibonacci数列模型），计算需数列模型），计算需要多少月才能筹备齐彩礼要多少月才能筹备齐彩礼2.2.由于羊价格波动大，在程序中引入宏定义来表示羊的价格，便于程序修改由于羊价格波动大，在程序中引入宏定义来表示羊的价格，便于程序修改
25、3.3.在主函数中通过条件编译来选择采用哪个函数来计算彩礼；提交代码和执行结果在主函数中通过条件编译来选择采用哪个函数来计算彩礼；提交代码和执行结果50选做题（1）. 有一群鸡和一群兔，两种动物只数相同。两种动物的脚的总数都是三位数，且这两个三位数的六个数字分别是0，1，2，3，4，5。编程求鸡和兔的只数是多少？ 它们的脚数各是多少？ 答案：（2）编程计算n=50下列两式的值，并比较大小 如果SNS,输出1，S=NS，输出0，SNS，输出-1;答案笑话一则笑话一则p学生问：老师，递归好难啊，如何正确理解递归呀？学生问：老师，递归好难啊，如何正确理解递归呀？p老师答：老师答：要理解递归，你先要理解递归要理解递归，你先要理解递归
