计算机程序设计基础_第七章(2)

计算机程序设计基础计算机程序设计基础计算机程序设计基础计算机程序设计基础教师：文迪教师：文迪Email: Email: [e-mail]@tsinghua.edu.cn清华大学电子工程系清华大学电子工程系清华大学电子工程系清华大学电子工程系智能图文信息处理实验室智能图文信息处理实验室第七章第七章模块及函数设计（二）模块及函数设计（二）第七章第七章模块及函数设计（二）模块及函数设计（二）1.1.基于函数的模块化程序设计基于函数的模块化程序设计22函数函数的递归调用的递归调用函数的递归调用为我们带来什么样的编程灵活性？什么是内联函数？内联函2.2.函数函数的递归调用的递归调用3.3.预处理命令预处理命令什么是内联函数？内联函数与普通函数、宏定义的区别在哪里？什么是函数的重载？在什么情况下函数可以重载？如何规定函数的默认参数？如何规定函数的默认参数？基于函数的模块化程序设计基于函数的模块化程序设计基于函数的模块化程序设计基于函数的模块化程序设计••上节课，我们了解了程序模块的概上节课，我们了解了程序模块的概上节课，我们了解了程序模块的概上节课，我们了解了程序模块的概念，及其在念，及其在CC语言中的实现手段语言中的实现手段————函数函数InOut.cppCalc.cppInOuthCalch••有了函数的支持，我们就可以把软有了函数的支持，我们就可以把软件程序设计分散为独立的件程序设计分散为独立的模块设计模块设计在在们们.h.h••在在CC语言中，我们通常用不同语言中，我们通常用不同的的..cppcpp文件存放不同文件存放不同的的函数模块，函数模块，然后用然后用hh头文件存放它们的声明头文件存放它们的声明Calc.hInOut.hInOut.cppCalc.cpp然后用然后用.h.h头文件存放它们的声明，头文件存放它们的声明，便于管理便于管理Progcpp.cppmain()Calc.hInOut.hInOut.cppCalc.cppProg.cppmain()基于函数的程序运行基于函数的程序运行基于函数的程序运行基于函数的程序运行••在运行时，程序每次都会调用在运行时，程序每次都会调用mainmain()()函数函数————所有所有在运行时，程序每次都会调用在运行时，程序每次都会调用()()函数函数所有所有C/C++C/C++语言程序的入口，也是第一个被调用的函数语言程序的入口，也是第一个被调用的函数编译、链接在通常情况下，main()函数是C/C++程序的int  main (void)  // 主函数{exe可执行程序C/C++程序的入口，从main函数中return就等于结束整}//main可执行程序就等于结束整个程序。} // main} // main调入操作调入操作系统运行函数的嵌套调用函数的嵌套调用函数的嵌套调用函数的嵌套调用••从从main()main()函数开始，整个函数开始，整个C/C++C/C++程序就是一部函数调程序就是一部函数调从从()()函数开始，整个函数开始，整个//程序就是部函数调程序就是部函数调用的历史用的历史int  main (void)  // 主函数{...void  func1(void){...boolfunc2(intn){main()func2(n)func1();...if ( func2(a) ){...}...return true;...函数调用函数调用堆栈堆栈func1()main()函数调用函数调用func1()main()函数调用函数调用堆栈堆栈}...} // func1} // func2函数调用函数调用堆栈堆栈堆栈堆栈} // main函数调用的原理函数调用的原理函数调用的原理函数调用的原理••C/C++C/C++语言编译器通过在函数语言编译器通过在函数调用调用和和返回返回时的固定操时的固定操作来实现函数调用在函数调用时作来实现函数调用在函数调用时作来实现函数调用，在函数调用时：作来实现函数调用，在函数调用时：1.1.保存原执行函数的寄存器现场；保存原执行函数的寄存器现场；22进行参数传递；进行参数传递；2.2.进行参数传递；进行参数传递；3.3.指令控制转向调用函数的入口处；指令控制转向调用函数的入口处；在函数返回时：在函数返回时：func()在函数返回时：在函数返回时：1.1.传递返回值；传递返回值；2.2.指令控制返回调用函数的下一条语句处；指令控制返回调用函数的下一条语句处；func()...函数调用函数调用3.3.恢复原执行函数的寄存器现场。恢复原执行函数的寄存器现场。每当一个函数被调用时，编译器都会为其分配一个堆每当一个函数被调用时，编译器都会为其分配一个堆函数调用函数调用堆栈堆栈栈空间置于栈顶，用来保存该函数所有参数、局部栈空间置于栈顶，用来保存该函数所有参数、局部变量和寄存器现场。函数堆栈随函数的嵌套调用而变量和寄存器现场。函数堆栈随函数的嵌套调用而逐层增加函数退出时则从栈顶开始逐层弹出逐层增加函数退出时则从栈顶开始逐层弹出逐层增加，函数退出时则从栈顶开始逐层弹出逐层增加，函数退出时则从栈顶开始逐层弹出函数的递归调用函数的递归调用函数的递归调用函数的递归调用••基于上述原理，基于上述原理，C/C++C/C++语言支持函数的递归调用语言支持函数的递归调用————即即基于上述原理，基于上述原理，//语言支持函数的递归调用语言支持函数的递归调用即即在某个函数的函数体中出现调用自己的语句在某个函数的函数体中出现调用自己的语句func(inta){func(a/2){...func(a/2);func()...数数func(a)...函数调用函数调用堆栈堆栈...}函数调用函数调用堆栈堆栈堆栈堆栈直接的递归调用函数的递归调用函数的递归调用函数的递归调用函数的递归调用••另一种类似于递归调用的情况另一种类似于递归调用的情况————函数的循环调用函数的循环调用另种类似于递归调用的情况另种类似于递归调用的情况函数的循环调用函数的循环调用f1(a/2-3)f2(a/2)f1(a)f1(inta){f1(a)...函数调用函数调用堆栈堆栈f2(inta){f2(a/2)f1(a)...f2(a/2);...}f1(a)...函数调用函数调用堆栈堆栈...f1(a-3);...}...函数调用函数调用堆栈堆栈}堆栈堆栈}间接的递归调用间接的递归调用有限次数有终止的递归调用有限次数有终止的递归调用有限次数、有终止的递归调用有限次数、有终止的递归调用••如果没有退出机制，函数的递归调用将导致无终止的如果没有退出机制，函数的递归调用将导致无终止的如果没有退出机制，函数的递归调用将导致无终止的如果没有退出机制，函数的递归调用将导致无终止的自身调用，最终导致函数调用堆栈溢出错误。所以，自身调用，最终导致函数调用堆栈溢出错误。所以，必须加上条件判断，必须加上条件判断，只有满足条件才进行递归调用，只有满足条件才进行递归调用，否则将终止否则将终止，让函数逐层退出，让函数逐层退出，才能保证，才能保证递归调用是递归调用是有限次数、有终止的。有限次数、有终止的。f2()f()f()f2()f1()f2()f1()...函数调用函数调用堆栈堆栈f1()函数调用函数调用堆栈堆栈递归的基本思想及其用途递归的基本思想及其用途递归的基本思想及其用途递归的基本思想及其用途••人们在解决一些复杂的问题时，为了降低问题的复杂人们在解决一些复杂的问题时，为了降低问题的复杂人们在解决些复杂的问题时，为了降低问题的复杂人们在解决些复杂的问题时，为了降低问题的复杂度，度，有时有时会采用会采用逆向思维过程逆向思维过程（又称（又称分析法分析法）：即将）：即将问题逐层分解，最后归结为一些最简单的问题逐层分解，最后归结为一些最简单的问题，当这问题，当这些些最简单的最简单的问题得到解决后问题得到解决后，再沿着原来分解，再沿着原来分解的路径的路径逐步逐步回朔回朔。（这与。（这与通常的正向通常的正向思维思维————综合法综合法相反）相反）••在程序设计中，递归思想同样是一种很在程序设计中，递归思想同样是一种很有用的工具有用的工具，，可以通过函数递归调用实现。可以通过函数递归调用实现。对于一些比较复杂的问对于一些比较复杂的问题，若将算法设计成递归结构，代码量少，思路清晰，题，若将算法设计成递归结构，代码量少，思路清晰，可读性强。可读性强。约瑟夫问题约瑟夫问题约瑟夫问题约瑟夫问题••3939个犹太人与约瑟夫及他的朋个犹太人与约瑟夫及他的朋个犹太人与约瑟夫及他的朋个犹太人与约瑟夫及他的朋友躲到一个洞中，友躲到一个洞中，3939个犹太人个犹太人决定宁死也不要被敌人抓到，决定宁死也不要被敌人抓到，于是决定了个自杀方式于是决定了个自杀方式1241于是决定了一个自杀方式，于是决定了一个自杀方式，4141个人排成一个圆圈，由第个人排成一个圆圈，由第11个人个人开始报数每报到第开始报数每报到第33人该人就人该人就2340开始报数，每报到第开始报数，每报到第33人该人就人该人就必须自杀，然后再由下一个重必须自杀，然后再由下一个重新报数，直到所有人都自杀身新报数，直到所有人都自杀身439新报数，直到所有人都自杀身新报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋亡为止。然而约瑟夫和他的朋友并不想遵从，他将朋友与自友并不想遵从，他将朋友与自38537己安排在两个位置上，最终逃己安排在两个位置上，最终逃过了这场死亡游戏。试问：这过了这场死亡游戏。试问：这两个位置是哪两个？两个位置是哪两个？37两个位置是哪两个？两个位置是哪两个？思路思路22思路思路22••如果只需要求解如果只需要求解最后一个幸存者最后一个幸存者原来所站的位置，那原来所站的位置，那如果只需要求解如果只需要求解最后个幸存者最后个幸存者原来所站的位置，那原来所站的位置，那么不需要把整个游戏过程都模拟出来。因为，假设我么不需要把整个游戏过程都模拟出来。因为，假设我们已经知道们已经知道4040人游戏最后一个幸存者的位置人游戏最后一个幸存者的位置J(40,3)J(40,3)为为那么那么在在人游戏时对应的位置人游戏时对应的位置和和之间存在之间存在为为XX，那么，那么XX在在4141人游戏时对应的位置人游戏时对应的位置X’X’和和XX之间存在之间存在着简单的对应关系。着简单的对应关系。1123414039401383734403941人游戏12373640人游戏5X’?3XX’=f(X)?X=J(40,3)X思路思路22思路思路22••因为因为4141人游戏的第一个出局者是人游戏的第一个出局者是33，，33号出局后从号出局后从44号号因为因为人游戏的第个出局者是人游戏的第个出局者是，，号出局后从号出局后从号号开始重新报数。若规定此时所有人自开始重新报数。若规定此时所有人自44号开始重新按照号开始重新按照11～～4040编号，则两次编号之间有以下对应关系：编号，则两次编号之间有以下对应关系：1245X(41)(X(40)+3)%4123...56...X(41)=(X(40)+3)%41if(X(40)+3==41)3839404112X(41)=4140人游戏41人游戏402时的编号时的编号思路思路22思路思路22••以此类推，因为以此类推，因为4040人游戏的第一个出局者还是人游戏的第一个出局者还是33，再，再以此类推，因为以此类推，因为人游戏的第个出局者还是人游戏的第个出局者还是，再，再次自次自44号起重新报数号起重新报数......因此可以得出因此可以得出nn人游戏和人游戏和nn--11人游戏的号码对应关系为：人游戏的号码对应关系为：X(n)=(X(n-1)+3)%n()if(X(n-1)+3==n)X()X(n)=n思路思路22思路思路22••显然，还剩下显然，还剩下22人时，出局者编号为人时，出局者编号为11，即幸存者编号：，即幸存者编号：显然，还剩下显然，还剩下人时，出局者编号为人时，出局者编号为，即幸存者编号，即幸存者编