1、41 函数的定义与调用函数的定义与调用 4 5 作用域与存储类型作用域与存储类型 44 函数调用机制函数调用机制 43 全局变量和局部变量全局变量和局部变量 42 函数的参数传递函数的参数传递,返回值及函数原型说明返回值及函数原型说明 410 编译预处理编译预处理 4 9 头文件与多文件结构头文件与多文件结构 4 8 C+的系统库函数的系统库函数 4 7 函数的一些高级议题函数的一些高级议题 4 6 函数的递归调用函数的递归调用 4.1.1 函数概述函数概述4.1.2 函数的定义函数的定义4.1.3 函数的调用函数的调用 main()fun2()fun1()fun3()Fun1_1()Fun2
2、_1()Fun2_2()图图4.1 函数调用层次关系函数调用层次关系1.无参函数无参函数2.有参函数有参函数 定义格式为:定义格式为:(void)(void)例例:下面函数的功能是打印一个表头下面函数的功能是打印一个表头void TableHead()cout*endl;cout*example *endl;cout*endl;有参函数的定义格式为有参函数的定义格式为(,例例:下面函数的功能是返回两个整数中较大一个的值下面函数的功能是返回两个整数中较大一个的值 max(int a,int b)return(a=b?a:b);无参函数的调用格式为:无参函数的调用格式为:()()有参函数的调用格式
3、为:有参函数的调用格式为:(实际参数表实际参数表)main()函函数数调用调用max(2.5,4.7)函数函数max(2.5,4.7)return 4.7 主程序后续主程序后续语句语句【例【例41】输入两个实数,输出其中较大的数。其中求两个实数中的较大数用输入两个实数,输出其中较大的数。其中求两个实数中的较大数用函数完成。函数完成。程序如下:程序如下:/文件名:文件名:Ex4_1.cpp#includefloat max(float x,float y)return(x=y?x:y);void main()float x,y;cout输入两个实数:输入两个实数:xy;coutx和和y中较大数为
4、中较大数为max(x,y)endl;421 函数的参数传递及传值调用函数的参数传递及传值调用 423 函数原型说明函数原型说明422 函数返回值函数返回值 调用调用power(4.6,3)函数函数power(4.6,3)return 97.336 主程序后续语主程序后续语句句【例【例42】说明实参和形参对应关系的示例。说明实参和形参对应关系的示例。/文件名:文件名:Ex4_2.cpp#include#includefloat power(float x,int n)/求求x的的n次幂次幂float pow=1;while(n-)pow*=x;return pow;void main()int
5、n=3;float x=4.6;char c=a;coutpower(x,n)=power(x,n)endl;coutpower(c,n)=power(c,n)endl;coutpower(n,x)=power(n,x)endl;调用调用power(a,3)函数函数power(a,3)return 912673 主程序后续语主程序后续语句句【例【例42】说明实参和形参对应关系的示例。说明实参和形参对应关系的示例。/文件名:文件名:Ex4_2.cpp#include#includefloat power(float x,int n)/求求x的的n次幂次幂float pow=1;while(n-)
6、pow*=x;return pow;void main()int n=3;float x=4.6;char c=a;coutpower(x,n)=power(x,n)endl;coutpower(c,n)=power(c,n)endl;coutpower(n,x)=power(n,x)endl;调用调用power(3,4.6)函数函数power(3,4.6)return 81 主程序后续语主程序后续语句句【例【例42】说明实参和形参对应关系的示例。说明实参和形参对应关系的示例。/文件名:文件名:Ex4_2.cpp#include#includefloat power(float x,int n
7、)/求求x的的n次幂次幂float pow=1;while(n-)pow*=x;return pow;void main()int n=3;float x=4.6;char c=a;coutpower(x,n)=power(x,n)endl;coutpower(c,n)=power(c,n)endl;coutpower(n,x)=power(n,x)endl;return语句的一般格式为:语句的一般格式为:return;【例【例43】设计函数,根据三角形的三边长求面积。如果不能构成三角形,给出提示】设计函数,根据三角形的三边长求面积。如果不能构成三角形,给出提示信息。信息。分析:分析:函数为计
8、算三角形面积,一般三角形返回面积值,若不能构成三角形则返回函数为计算三角形面积,一般三角形返回面积值,若不能构成三角形则返回-1。设计一个主函数完成函数测试。根据返回值情况输出相应结果。设计一个主函数完成函数测试。根据返回值情况输出相应结果。程序如下:程序如下:/文件名:文件名:Ex4_3.cpp#include#include调用调用TriangleArea(3,4,5)函数函数TriangleArea(3,4,5)return 6 area=6三角形三角形(3,4,5)面积为面积为6float TriangleArea(float a,float b,float c)if(a+b=c)|(
9、a+c=b)|(b+c=a)return-1;float s;s=(a+b+c)/2;return sqrt(s*(s-a)*(s-b)*(s-c);void main()float a,b,c,area;cout输入三角形三边输入三角形三边a,b,c:abc;area=TriangleArea(a,b,c);if(area=-1)cout(a,b,c)不能构成三角形!不能构成三角形!endl;elsecout三角形三角形(a,b,c)面积为:面积为:areaendl;调用调用TriangleArea(3,4,8)函数函数TriangleArea(3,4,8)return-1 area=-1(
10、3,4,8)不能构不能构成三角形成三角形float TriangleArea(float a,float b,float c)if(a+b=c)|(a+c=b)|(b+c=a)return-1;float s;s=(a+b+c)/2;return sqrt(s*(s-a)*(s-b)*(s-c);void main()float a,b,c,area;cout输入三角形三边输入三角形三边a,b,c:abc;area=TriangleArea(a,b,c);if(area=-1)cout(a,b,c)不能构成三角形!不能构成三角形!endl;elsecout三角形三角形(a,b,c)面积为:面积
11、为:areaendl;函数原型是一条以分号结束的语句,实际上函数原型是一条以分号结束的语句,实际上就是所定义函数的函数头,形如:就是所定义函数的函数头,形如:()下面是一个使用结构化程序设计思想开发的企业管理报表下面是一个使用结构化程序设计思想开发的企业管理报表程序的框架。程序的框架。#include void menu_print();void account_report();void engineering_report();void marketing_report();void main()int choice;do menu_print();cinchoice;while(choi
12、ce=0);switch(choice)case 1:account_report();break;case 2:engineering_report();break;case 3:marketing_report();break;void menu_print()cout”系统功能:系统功能:”endl;cout”1财务报表财务报表”endl;cout”2工程报表工程报表”endl;cout”3市场报表市场报表”endl;cout”选择业务序号:选择业务序号:”;void account_report()/生成财务报表生成财务报表 void engineering_report()/生成工程
13、报表生成工程报表 void marketing_report()/生成实常报表;生成实常报表;【例【例44】输出所有满足下列条件的正整数输出所有满足下列条件的正整数m:10m1000且且m、m2、m3均为回文数。均为回文数。分析:分析:回文指左右对称的序列。如回文指左右对称的序列。如121、353等就是回文数。判断整等就是回文数。判断整数是否回文数用函数实现,其思想是将该数各位拆开后反向组成新的数是否回文数用函数实现,其思想是将该数各位拆开后反向组成新的整数,如果该整数与原数相等则为回文数。整数,如果该整数与原数相等则为回文数。程序如下:程序如下:/文件名:文件名:Ex4_4.cpp#incl
14、ude#includebool palindrome(int);/函数原型函数原型bool palindrome(int n)int digit10;int m=n,i=0;do digiti=n%10;n/=10;i+;while(n0);for(intj=0;ji;j+)n=n*10+digitj;return(n=m);m m*m m*m*mm=11调用调用palindrom(11)函数函数palindrom(11)为真为真return 真真 11 121 1331调用调用palindrom(121)函数函数palindrom(121)为真为真return 真真调用调用palindrom
15、(1331)函数函数palindrom(1331)为真为真return 真真打印打印,循环循环void main()coutsetw(10)msetw(20)m*msetw(20)m*m*mendl;for(int m=11;m1000;m+)if(palindrome(m)&palindrome(m*m)&palindrome(m*m*m)coutsetw(10)msetw(20)m*msetw(20)m*m*0);for(intj=0;ji;j+)n=n*10+digitj;return(n=m);void main()coutsetw(10)msetw(20)m*msetw(20)m*m
16、*mendl;for(int m=11;m1000;m+)if(palindrome(m)&palindrome(m*m)&palindrome(m*m*m)coutsetw(10)msetw(20)m*msetw(20)m*m*0);forint=0;ji;j+)n=n*10+digitj;return(n=m);void main()coutsetw(10)msetw(20)m*msetw(20)m*m*mendl;for(int m=11;m1000;m+)if(palindrome(m)&palindrome(m*m)&palindrome(m*m*m)coutsetw(10)mset
17、w(20)m*msetw(20)m*m*m。要求阶乘和组和数均用函数实现。要求阶乘和组和数均用函数实现。程序名:程序名:Ex4_6.cpp#includefac(int);combination(int,int);n=5m=2调用调用combination(5,2)函数函数combination(5,2)120/2*6=10return10打印打印结束结束调用调用fan(2)fan(5)fan(3)函数函数fan(2)fan(5)fan(3)return fan(2)=2;fan(3)=6fan(5)=120void main()int n,m;docout输入两个整数输入两个整数n,m:nm
18、;while(n=0|m=0|n=m);coutC(n,m)=combination(n,m)endl;combination(int n,int m)return fac(n)/(fac(m)*fac(n-m);fac(int n)int factorial=1;for(int i=1;i=n;i+)factorial*=i;return factorial;堆区堆区(动态数据动态数据)栈区栈区(函数局部数据)(函数局部数据)(main()函数局部数据)函数局部数据)静态数据区静态数据区(全局、静态变量全局、静态变量)代码区代码区(程序代码)(程序代码)操作系统为一个操作系统为一个C+C+程
19、序的运行所分配的内存分为程序的运行所分配的内存分为四个区域,如图四个区域,如图4.34.3 程序在内存中的区域程序在内存中的区域所示:所示:i=0调用调用sqrt(0)函数函数sqrt(0)return 0 打印打印n+=1 i+=1继续循环继续循环n=011【例【例47】使用全局变量的例子。】使用全局变量的例子。/文件名文件名:Ex4_7.cppint n=0;#include#includevoid main()for(int i=0;i5;i+)coutsqrt(n)endl;n+;i=1调用调用sqrt(1)函数函数sqrt(1)return 1 打印打印n+=2 i+=2继续循环继续
20、循环n=122【例【例47】使用全局变量的例子。】使用全局变量的例子。/文件名文件名:Ex4_7.cppint n=0;#include#includevoid main()for(int i=0;i5;i+)coutsqrt(n)endl;n+;i=2调用调用sqrt(2)函数函数sqrt(2)return 1.41421 打印打印n+=3 i+=3继续循环继续循环n=233【例【例47】使用全局变量的例子。】使用全局变量的例子。/文件名文件名:Ex4_7.cppint n=0;#include#includevoid main()for(int i=0;i5;i+)coutsqrt(n)e
21、ndl;n+;i=3调用调用sqrt(3)函数函数sqrt(3)return 1.73205 打印打印n+=4 i+=4继续循环继续循环n=344【例【例47】使用全局变量的例子。】使用全局变量的例子。/文件名文件名:Ex4_7.cppint n=0;#include#includevoid main()for(int i=0;i5;i+)coutsqrt(n)endl;n+;i=4调用调用sqrt(4)函数函数sqrt(4)return 2 打印打印n+=5 i+=5结束结束n=455【例【例47】使用全局变量的例子。】使用全局变量的例子。/文件名文件名:Ex4_7.cppint n=0;#
22、include#includevoid main()for(int i=0;i5;i+)coutsqrt(n)endl;n+;打印打印200调用调用func(200)函数函数func(200)200*2=400return400 打印打印400n=100n=100*2=200【例【例48】多个函数使用全局变量的例子。多个函数使用全局变量的例子。/文件名:文件名:Ex4_8.cppint n=100;#includevoid func()n*=2;void main()n*=2;coutnendl;func();coutnendl;打印打印t=3.5调用调用fun()函数函数fun()打印打印t
23、=5 打印打印t=3.5t =5【例【例49】使用局部变量的例子。使用局部变量的例子。/文件名:文件名:Ex4_9.cpp#includevoid fun()auto int t=5;/fun()中的局部变量,中的局部变量,auto可省略可省略coutfun()中的中的t=tendl;void main()float t=3.5;/main()函数中的局部变量函数中的局部变量coutmain()中的中的t=tendl;fun();coutmain()中的中的t=t3即即bat=335a=3 b=5a=5 b=3【例【例410】输入两数,将两数按从大到小的顺序保存,并输出结果。输入两数,将两数按
24、从大到小的顺序保存,并输出结果。/文件名:文件名:Ex4_10.cpp#includevoid main()int a,b;/函数内定义局部变量,具有函数作用域函数内定义局部变量,具有函数作用域cout输入两整数:输入两整数:ab;couta=atb=b=a)/使使a中保存大数,中保存大数,b中保存小数中保存小数int t;/块中定义局部变量,具有块作用域块中定义局部变量,具有块作用域t=a;a=b;b=t;/交换交换a,b的值的值couta=atb=bendl;【例例411】设计函数完成两数交换,用主函数进行】设计函数完成两数交换,用主函数进行测试。测试。/文件名:文件名:Ex4_11.cp
25、p#includevoid swap(int,int);调用前调用前:实参实参a=3,b=5调用中调用中形参形参a=3形参形参b=5t=交换前交换前:形参形参a=3,b=5353交换后交换后:形参形参a=5,b=3调用后调用后:实参实参a=3,b=5void main()int a,b;/a,b作用域为main()cout输入两整数:ab;c o u t 调 用 前:实 参a=a,b=bendl;swap(a,b);c o u t 调 用 后:实 参a=a,b=bendl;void swap(int a,int b)/a,b作用域为swap()cout调用中endl;c o u t 交 换 前
26、:形 参a=a,b=bendl;int t;t=a;a=b;b=t;/交换a,b的值c o u t 交 换 后:形 参a=a,b=bendl;100 200 300内内 i=500内内 j=600内内n=500+600 =11001100 500 600100200+300=500500 500 200 300【例【例412】显示同名变量可见性的例子。显示同名变量可见性的例子。/文件名:文件名:Ex4_12.cppint n=100;#includevoid main()int i=200,j=300;cout ntitjendl;/内部块内部块int i=500,j=600,n;n=i+j;
27、cout ntitj endl;/输出局部变量输出局部变量ncout:nendl;/输出全局变量输出全局变量nn=i+j;/修改全局变量修改全局变量cout ntitj endl;函数原型不是定义函数,在作函数原型声函数原型不是定义函数,在作函数原型声明时,其中的形参作用域只在原型声明中,明时,其中的形参作用域只在原型声明中,即作用域结束于右括号。正是由于形参不能即作用域结束于右括号。正是由于形参不能被程序的其他地方引用,所以通常只要声明被程序的其他地方引用,所以通常只要声明形参个数和类型,形参名可省略。形参个数和类型,形参名可省略。文件作用域也称全局作用域。定义在所有函数之外文件作用域也称全
28、局作用域。定义在所有函数之外的标识符,具有文件作用域,作用域为从定义处到的标识符,具有文件作用域,作用域为从定义处到整个源文件结束。文件中定义的全局变量和函数都整个源文件结束。文件中定义的全局变量和函数都具有文件作用域。具有文件作用域。如果某个文件中说明了具有文件作用域的标识符,如果某个文件中说明了具有文件作用域的标识符,该文件又被另一个文件包含,则该标识符的作用域该文件又被另一个文件包含,则该标识符的作用域延伸到新的文件中。如延伸到新的文件中。如cincin和和coutcout是在头文件是在头文件iostream.hiostream.h中说明的具有文件作用域的标识符,它中说明的具有文件作用域
29、的标识符,它们的作用域也延伸到嵌入们的作用域也延伸到嵌入iostream.hiostream.h的文件中。的文件中。1 2 3 4 5st()static int t=100;/局部静态变量局部静态变量t+;return t;at()int t=100;/自动变量自动变量t+;return t;101101101101101【例【例413】自动变量与局部静态变量的自动变量与局部静态变量的区别。区别。/文件名:文件名:Ex4_13.cpp#include st();at();void main()int i;for(i=0;i5;i+)coutat()t;coutendl;for(i=0;i5;
30、i+)coutst()t;coutendl;1 21013 4 5102103104105st()static int t=100;/局部静态变量局部静态变量t+;return t;at()int t=100;/自动变量自动变量t+;return t;【例【例413】自动变量与局部静态变量的自动变量与局部静态变量的区别。区别。/文件名:文件名:Ex4_13.cpp#include st();at();void main()int i;for(i=0;i5;i+)coutat()t;coutendl;for(i=0;i5;i+)coutst()t;coutendl;1.外部存储类型外部存储类型2
31、.静态存储类型静态存储类型【例【例414】外部存储类型的例子。假定程序包含两个源程序文件外部存储类型的例子。假定程序包含两个源程序文件Ex4_14_1.cpp和和Ex4_14_2.cpp,程序结构如下:,程序结构如下:/*Ex4_14_1.cpp,由,由main()和和fun1()组成组成*/#include void fun1();/外部函数声明,等价于外部函数声明,等价于extern void fun1();void fun2();/外部函数声明,等价于外部函数声明,等价于extern void fun2();int n;/全局变量定义全局变量定义n=1调用调用fun1()函数函数fun1
32、()returnn=3 打印打印n=3调用调用fun2()函数函数fun2()return n=3 3void main()n=1;fun1();/fun1()定义在本文件中定义在本文件中coutn=nendl;void fun1()fun2();/fun2()定义在文件定义在文件Ex4_14_2.cpp中中/*Ex4_14_2.cpp,由,由fun2()组成组成*/extern int n;/外部变量声明,外部变量声明,n定义在文件定义在文件Ex4_13_1.cpp中中void fun2()/fun2()被文件被文件Ex4_14_1.cpp中的函数调用中的函数调用n=3;【例【例415】静态
33、存储类型的例子。假定一个程序由两个源程序文件静态存储类型的例子。假定一个程序由两个源程序文件Ex4_15_1.cpp和和Ex4_15_2.cpp组成。程序结构如下:组成。程序结构如下:/*文件名:文件名:Ex4_15_1.cpp,由,由main()组成组成*/#includeint n=10;/定义全局变量定义全局变量/void fun1();/错误的外部函数声明错误的外部函数声明void fun2();/外部函数声明外部函数声明void main()coutn=nendl;/fun1();/错误错误fun2();/使用外部函数使用外部函数 /*文件名:文件名:Ex4_15_2.cpp,由,由
34、fun2()和静态函数和静态函数fun1()组成组成*/#includestatic int n=5;/定义静态变量定义静态变量static void fun1()/定义静态函数定义静态函数coutfun1()是静态函数是静态函数endl;void fun2()coutn=nendl;fun1();coutfun2()是外部函数是外部函数endl;1.生命期生命期2.可见性可见性 静态生命期指的是标识符从程序开始运行时静态生命期指的是标识符从程序开始运行时存在,即具有存储空间,到程序运行结束时消亡,存在,即具有存储空间,到程序运行结束时消亡,即释放存储空间。具有静态生命期的标识符存放即释放存储
35、空间。具有静态生命期的标识符存放在静态数据区,属于静态存储类型,如全局变量、在静态数据区,属于静态存储类型,如全局变量、静态全局变量、静态局部变量。具有静态生命期静态全局变量、静态局部变量。具有静态生命期的标识符在未被用户初始化的情况下,系统会自的标识符在未被用户初始化的情况下,系统会自动将其初始化为动将其初始化为0 0。函数驻留在代码区,也具有静态生命期。所函数驻留在代码区,也具有静态生命期。所有具有文件作用域的标识符都具有静态生命期。有具有文件作用域的标识符都具有静态生命期。在函数内部或块中定义的标识符具有局部生命在函数内部或块中定义的标识符具有局部生命期,其生命期开始于执行到该函数或块的
36、标识符声期,其生命期开始于执行到该函数或块的标识符声明处,结束于该函数或块的结束处。具有静态生命明处,结束于该函数或块的结束处。具有静态生命期的标识符存放在栈区。具有局部生命期的标识符期的标识符存放在栈区。具有局部生命期的标识符如果未被初始化,其内容是随机的,不可用。如果未被初始化,其内容是随机的,不可用。具有局部生命期的标识符必定具有局部作用域;具有局部生命期的标识符必定具有局部作用域;但反之不然,静态局部变量具有局部作用域,但却但反之不然,静态局部变量具有局部作用域,但却具有静态生命期。具有静态生命期。具有动态生命期的标识符由特定的函数调具有动态生命期的标识符由特定的函数调用或运算来创建和
37、释放,如调用用或运算来创建和释放,如调用mallocmalloc()()或用或用newnew运算符为变量分配存储空间时,变量的生命运算符为变量分配存储空间时,变量的生命期开始,而调用期开始,而调用free()free()或用或用deletedelete运算符释放运算符释放空间或程序结束时,变量生命期结束。具有动空间或程序结束时,变量生命期结束。具有动态生命期的变量存放在堆区。关于态生命期的变量存放在堆区。关于newnew运算和运算和deletedelete运算将在职真一章介绍。运算将在职真一章介绍。下面的程序段和图示显示作用域与可见性。下面的程序段和图示显示作用域与可见性。int m,floa
38、t x作用域作用域int m可见可见float m不不可见可见x可见可见 int m=1;float x;float m=3.5;float m作用域作用域float m可见可见int m不可见不可见x可可见见x=5.5;m+;int m,float x作用域作用域int m可见可见float m不可见不可见x可见可见float m作用域作用域float m可见可见int m不可见不可见x可见可见1n 1)!-(n*n1n 1 0n 0 n 递归是一种描述问题的方法,或称算法。递递归是一种描述问题的方法,或称算法。递归的思想可以简单地描述为归的思想可以简单地描述为“自己用自己自己用自己”。例。
39、例如用如下方法定义阶乘:如用如下方法定义阶乘:n=4cout4;y=4*fac(3);4!=【例【例416】求求4!/文件名:文件名:Ex4_16.cpp#include int fac(int n)int y;coutnt;if(n=0|n=1)y=1;else y=n*fac(n-1);coutyt;return y;void main()coutn4!=fac(4)endl;n=4cout4;y=4*fac(3);4!=n=3cout3;y=3*fac(2);【例【例416】求求4!/文件名:文件名:Ex4_16.cpp#include int fac(int n)int y;coutn
40、t;if(n=0|n=1)y=1;else y=n*fac(n-1);coutyt;return y;void main()coutn4!=fac(4)endl;n=4cout4;y=4*fac(3);4!=cout2;y=2*fac(1);n=2 n=3cout3;y=3*fac(2);【例【例416】求求4!/文件名:文件名:Ex4_16.cpp#include int fac(int n)int y;coutnt;if(n=0|n=1)y=1;else y=n*fac(n-1);coutyt;return y;void main()coutn4!=fac(4)endl;n=4cout4;
41、y=4*fac(3);4!=cout2;y=2*fac(1);n=2cout1;y=1;cout1;return 1;n=1 n=3cout3;y=3*fac(2);【例【例416】求求4!/文件名:文件名:Ex4_16.cpp#include int fac(int n)int y;coutnt;if(n=0|n=1)y=1;else y=n*fac(n-1);coutyt;return y;void main()coutn4!=fac(4)endl;n=4cout4;y=4*fac(3);4!=cout2;y=2*fac(1);n=2cout1;y=1;cout1;return 1;n=1
42、 n=3cout3;y=3*fac(2);cout2;return 2;【例【例416】求求4!/文件名:文件名:Ex4_16.cpp#include int fac(int n)int y;coutnt;if(n=0|n=1)y=1;else y=n*fac(n-1);coutyt;return y;void main()coutn4!=fac(4)endl;n=4cout4;y=4*fac(3);4!=cout2;y=2*fac(1);n=2cout1;y=1;cout1;return 1;n=1 n=3cout3;y=3*fac(2);cout6;return 6;cout2;retur
43、n 2;【例【例416】求求4!/文件名:文件名:Ex4_16.cpp#include int fac(int n)int y;coutnt;if(n=0|n=1)y=1;else y=n*fac(n-1);coutyt;return y;void main()coutn4!=fac(4)endl;n=4cout4;y=4*fac(3);4!=cout2;y=2*fac(1);n=2cout1;y=1;cout1;return 1;n=1 n=3cout3;y=3*fac(2);cout24;return 24;cout6;return 6;cout2;return 2;24【例【例416】求
44、求4!/文件名:文件名:Ex4_16.cpp#include int fac(int n)int y;coutnt;if(n=0|n=1)y=1;else y=n*fac(n-1);coutyt;return y;void main()coutn4!=fac(4)endl;【例【例417】汉诺塔问题。有汉诺塔问题。有A、B、C三根柱子,三根柱子,A柱上有柱上有n个大小不等的盘子,个大小不等的盘子,大盘在下,小盘在上。要求将所有盘子由大盘在下,小盘在上。要求将所有盘子由A柱搬动到柱搬动到C柱上,每次只能搬动一个盘子,柱上,每次只能搬动一个盘子,搬动过程中可以借助任何一根柱子,但必须满足大盘在下,
45、小盘在上。打印出搬动搬动过程中可以借助任何一根柱子,但必须满足大盘在下,小盘在上。打印出搬动的步骤。的步骤。A柱柱B柱柱C柱柱分析:分析:1 A柱只有一个盘子的情况:柱只有一个盘子的情况:A柱柱C柱;柱;2 A柱有两个盘子的情况:小盘柱有两个盘子的情况:小盘A柱柱B柱,大盘柱,大盘A柱柱C柱,小盘柱,小盘B柱柱C柱。柱。3 A柱有柱有n个盘子的情况:将此问题看成上面个盘子的情况:将此问题看成上面n-1个盘子和最下面第个盘子和最下面第n个盘子的情况。个盘子的情况。n-1个盘子个盘子A柱柱B柱,第柱,第n个盘子个盘子A柱柱C柱,柱,n-1个盘子个盘子B柱柱C柱。问题转化成搬柱。问题转化成搬动动n-
46、1个盘子的问题,同样,将个盘子的问题,同样,将n-1个盘子看成上面个盘子看成上面n-2个盘子和下面第个盘子和下面第n-1个盘子个盘子的情况,进一步转化为搬动的情况,进一步转化为搬动n-2个盘子的问题,个盘子的问题,类推下去,一直到最后成为搬,类推下去,一直到最后成为搬动一个盘子的问题。动一个盘子的问题。这是一个典型的递归问题,递归结束于只搬动一个盘子。算法可以描述为:这是一个典型的递归问题,递归结束于只搬动一个盘子。算法可以描述为:1 n-1个盘子个盘子A柱柱B柱,借助于柱,借助于C柱;柱;2 第第n个盘子个盘子A柱柱C柱;柱;3 n-1个盘子个盘子B柱柱C柱,借助于柱,借助于A柱;柱;其中步
47、骤其中步骤1和步骤和步骤3继续递归下去,直至搬动一个盘子为止。由此,可以定义两个函继续递归下去,直至搬动一个盘子为止。由此,可以定义两个函数,一个是递归函数,命名为数,一个是递归函数,命名为hanoi(int n,char source,char temp,char target),实现将,实现将n个盘子从源柱个盘子从源柱source借助中间柱借助中间柱temp搬到目标柱搬到目标柱target;另一;另一个命名为个命名为move(char source,char target),用来输出搬动一个盘子的提示信息。,用来输出搬动一个盘子的提示信息。程序如下:程序如下:/文件名:文件名:Ex4_17
48、.cpp#include void move(char,char);void hanoi(int,char,char,char);void main()int n;cout输入盘子数:输入盘子数:n;hanoi(n,A,B,C);void hanoi(int n,char source,char temp,char target)if(n=1)move(source,target);elsehanoi(n-1,source,target,temp);/将将n-1个盘子搬到中间柱个盘子搬到中间柱move(source,target);/将最后一个盘子搬到目标柱将最后一个盘子搬到目标柱hanoi(
49、n-1,temp,source,target);/将将n-1个盘子搬到目标柱个盘子搬到目标柱 void move(char source,char target)coutsourcetargetChanoi(3,),)void hanoi(int n,char source,char temp,char target)if(n=1)move(source,target);elsehanoi(n-1,source,target,temp);/将将n-1个盘子搬到中间柱个盘子搬到中间柱move(source,target);/将最后一个盘子搬到目标柱将最后一个盘子搬到目标柱hanoi(n-1,te
50、mp,source,target);/将将n-1个盘子搬到目标柱个盘子搬到目标柱 void move(char source,char target)coutsourcetargetCA-Bhanoi(3,),)A柱柱B柱柱C柱柱调用调用hanoi(,),)hanoi(1,A,B,C)move(A,B)hanoi(1,C,A,B)A-CA-BC-Bhanoi(3,),)void hanoi(int n,char source,char temp,char target)if(n=1)move(source,target);elsehanoi(n-1,source,target,temp);/将