《算法语言与数据结构第5章.pptx》由会员分享，可在线阅读，更多相关《算法语言与数据结构第5章.pptx（174页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第5章 函数第1页/共174页第5章 函数 IntroductionIntroduction1 1 Main titleMain title2 2 ExamplesExamples3 3 ConclusionConclusion4 4第2页/共174页/*/*程 序：6_3.cpp（验证素数程序）*/*作 者：wuwh */*编制时间：2002年10月20日 */*主要功能：可验证某数是否为素数 */*#include/预编译命令#include /预编译命令int checkprime(int);/子函数声明int main()/主函数int a=0;/定义整型变量，初始化为0cout a;
2、/键盘输入一个整数/用实参a调用子函数，该子函数的/返回值作为if语句的分支条件if(checkprime(a)/checkprime(a)为1cout a 是素数 endl;else/checkprime(a)为0cout a 不是素数 endl;/主函数结束第第5章章 函数函数第3页/共174页/用实参 a 调用子函数，该子函数的/返回值作为 if 语句的分支条件if(checkprime(a)/checkprime(a)为 1cout a 是素数 endl;else /checkprime(a)为 0 cout a 不是素数 endl;/主函数结束第5章 函数第4页/共174页 T ch
3、eckprime(a)F cout a cout a 是素数 endl;不是素数 endl 第5章 函数第5页/共174页bool checkprime(int b)/子函数，子函数，b为形式参数为形式参数int k=0;/定义整型变量，并初始化定义整型变量，并初始化for(k=2;k=sqrt(double)b);k+)/循环循环if(b%k=0)/如果如果b能够被能够被k整除，则返回整除，则返回0/可理解为可理解为“抢先抢先”返回返回0，有了，有了 return 0，/后面的后面的 return 1 不起作用了不起作用了return 0;return 1;/b不能被不能被k整除，则返回整除
4、，则返回1第5章 函数第6页/共174页bool checkprime(int b)int k=0;for(k=2;k=sqrt(double)b);k+)if(b%k=0)return 0;return 1;第5章 函数第7页/共174页 bool checkprime(int b)/子函数子函数 int k=0;形式参数形式参数for(k=2;k=sqrt(double)b);k=K+1)if(b%k=0)return 0;return 1;/b不能被不能被k整除，则返回整除，则返回1 /说明说明 b 是质数是质数第5章 函数第8页/共174页 讲这一程序的目的：讲这一程序的目的：1.如何
5、定义一个函数如何定义一个函数2.主函数怎样调用子函数主函数怎样调用子函数3.实在参数和形式参数实在参数和形式参数4.返回值是什么意思返回值是什么意思第9页/共174页 主函数与子函数的配合:主函数通过实参去调用子函数将实参赋给子函数中的形参；子函数运算之后，又将调用结果返回给主函数一个值，这个值作为主函数判断该实参是素数与否的根据。两者配合得天衣无缝。第5章 函数第10页/共174页 在checkprime(int b)函数中，有return 0 和 return 1 两处不同。如果先有return 0了，后面一条return 1 就不起作用了。不会既执行 return 0 又执行 retur
6、n 1。第5章 函数第11页/共174页 函数的说明 放在主函数之前，告诉系统有 自定义的子函数可以被调用。例：bool checkprime(int);第12页/共174页 函数的定义函数返回值的类型 函数名(类型名 形式参数1，类型名 形式参数2，.)/函数体 说明部分 语句部分第13页/共174页 形式参数和实在参数 bool checkprime(int af);/定义 af 是形式参数，特点：1.未被调用不占内存单元；2.被调用后系统为其分配内存单元；3.调用结束释放内存单元；4.作用域限定在子函数内，属于局部变量。第14页/共174页 被调用函数嵌套在 if 语句中，a 是实在参数
7、 if(checkPrime(a)主函数 调用 checkPrime(af)子函数 形式参数第15页/共174页 实在参数是一个具有确定值的表达式 一个函数在调用子函数时，要将实在参数赋给形式参数 调用时 17 17 实在参数 a 形式参数 af第16页/共174页 调用 输入a 子函数 if(checkPrime(a)checkPrime(af)执行 if 语句 for:i=2,3 =1 =0 af%i=0 !=0 输出 输出 return 0 return 1 a是质数 a不是质数 返回第17页/共174页 int main()int a=0;cout a;if(checkprime(a)
8、bool checkprime(int b)int k=0;for(k=2;k=sqrt(double)b);k+)if(b%k=0)return 0;return 1;cout a 是素数 endl;elsecout a 不是素数 endl;第18页/共174页 美声唱法歌手大奖赛 裁判人数 n=10,打分范围 60=x=100,10人中打分的最大值 max 10人中打分的最小值 min 10人打分总和为 sum 选手最后得分为:(sum Max Min)/(N 2)第19页/共174页/*/*程 序：6_2.cpp */*作 者：wuwh */*编制时间：2002年10月20日 */*主要
9、功能：给歌手打分 */*第20页/共174页#include#include int Max(int,int)int Min(int,int)int main()int p=0;int q=100;int sum=0，x=0;int i=1;第21页/共174页 for(i=1;i=10;i=i+1)cout“请第”i“位裁判给分”x;p=Max(x,p);q=Min(x,q);sum=sum+x;cout“选手得分”b)return a;else return b;int Min(int c,int d)if (c d)return c;else return d;第23页/共174页 问题
10、：编程求解问题：编程求解现假定现假定现假定现假定 n=6n=6，k=4k=4思路：思路：思路：思路：1 1、该式可分解为、该式可分解为、该式可分解为、该式可分解为 2 2、定义一个函数、定义一个函数、定义一个函数、定义一个函数 i=1,2,n l=k第24页/共174页 让 l=4,i=1,2,.,6这个函数可以表示3 3、再定义一个函数、再定义一个函数、再定义一个函数、再定义一个函数 让让让让 m=nm=n，i=1,2,mi=1,2,m，即可得解，即可得解，即可得解，即可得解第25页/共174页/*/*程 序：6_2.cpp */*作 者：wuwh */*编制时间：2002年10月12日 *
11、/*主要功能：求幂函数的和（介绍函数）*/*第26页/共174页#include /预编译命令const int n=6;/定义常量 n 为 6const int k=4;/定义常量 k 为 4int SOP(int m,int l);/声明函数SOPint power(int p,int q);/声明函数power第27页/共174页/输出结果,其中SOP(n,k)为被调用函数int main()/主函数cout Sum of k/提示信息 from th powers of integers 1 to n is SOP(n,k)endl;第28页/共174页/以下函数是被主程序调用的函数/
12、功能：计算1,2,.,m的l次幂的和int SOP(int m,int l)/,m,l 为形参 int i,sum;sum=0;/初始化累加器for(i=1;i=m;i+)sum=sum+power(i,l);/累加return sum;/返回值第29页/共174页/以下函数是被函数sop(n,k)调用的函数/功能：计算p的q次幂int power(int p,int q)int i,product;product=1;/初始化累乘器for(i=1;i=q;i+)product=product*p;/累乘return product;第30页/共174页 int SOP(int m,int l
13、)m 6 l 4 power(1,l)1 int power(int p,int q)power(2,l)1 16 int power(int p,int q)16 power(m,l)1296 int power(int p,int q)2275 1296第31页/共174页数据类型 函数名(形式参数表)例例:int power(int p,int n)power 为函数名，要以英文字母开头。为函数名，要以英文字母开头。int 是函数值的数据类型，这里是是函数值的数据类型，这里是int（整型）。（整型）。(int p,int n)括号中的括号中的 p,n为函数的形式参数，形式为函数的形式参数
14、，形式参数也要定义其数据类型。参数也要定义其数据类型。第32页/共174页函数定义的一般格式：()第33页/共174页形式参数与实在参数1、形式参数形式参数是在定义函数时放在函数名后括号中的参数。在是在定义函数时放在函数名后括号中的参数。在未进行函数调用时，并不对形式参数分配内存单元。在发生未进行函数调用时，并不对形式参数分配内存单元。在发生函数调用时，立刻给形式参数分配内存单元。调用结束后，函数调用时，立刻给形式参数分配内存单元。调用结束后，释放掉行参所占的内存单元。释放掉行参所占的内存单元。2、因此，形参变量属于局部变量，其作用域在它所在的函数、因此，形参变量属于局部变量，其作用域在它所在
15、的函数体内。体内。3、在定义函数的时候，必须指定形参变量的类型，如下所示、在定义函数的时候，必须指定形参变量的类型，如下所示int power(int p,int n)/函数体函数体 c第34页/共174页4、实在参数是一个具有确定值的表达式。函数在调用时，将实在参数赋给形式参数。比如，主函数调用SOP(n,k)，这时，n,k为实在参数，n的值为6，k的值为4。在被调用函数定义中，int SOP(m,l)中的 m,l 为形式参数，在SOP被调用时，系统给 m,l 这两个形式参数分配了内存单元。之后，n 的值 6 赋给 m;k 的值 4 赋给 l。第35页/共174页power(i,l)处在 S
16、OP(m,l)函数中，表示SOP函数去调用 power 函数。其中 i,l 为实在参数，而 int power(p,q)中的 p,q 为形式参数。比如，执行 SOP(6,4)时，l=4,m=6,当 i=1 时，sum=sum+power(1,4)这里 1，4 为实在参数，调用power(p,q)，两个形式参数 p,q 分别被赋以 1，4。第36页/共174页第37页/共174页递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单运算，充分发挥计算机长于重复处理的特点，现举一例递递 推推第38页/共174页【例例例例5.35.3】A A、B B、C C、D D、E E五人合伙
17、夜间捕鱼，凌晨时五人合伙夜间捕鱼，凌晨时五人合伙夜间捕鱼，凌晨时五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在河边的树丛中找地方睡着了，都疲惫不堪，各自在河边的树丛中找地方睡着了，都疲惫不堪，各自在河边的树丛中找地方睡着了，都疲惫不堪，各自在河边的树丛中找地方睡着了，日上三竿，日上三竿，日上三竿，日上三竿，A A第一个醒来，他将鱼平分作五份，把第一个醒来，他将鱼平分作五份，把第一个醒来，他将鱼平分作五份，把第一个醒来，他将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回家去了，多余的一条扔回湖中，拿自己的一份回家去了，多余的一条扔回湖中，拿自己的一份回家去了，多余的一条扔回湖中，拿自己的一份回家
18、去了，B B第二个醒来，也将鱼平分为五份，扔掉多余的一条，第二个醒来，也将鱼平分为五份，扔掉多余的一条，第二个醒来，也将鱼平分为五份，扔掉多余的一条，第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份，接着只拿走自己的一份，接着只拿走自己的一份，接着只拿走自己的一份，接着C C、D D、E E依次醒来，也依次醒来，也依次醒来，也依次醒来，也都按同样的办法分鱼。问五人至少合伙捕到多少条都按同样的办法分鱼。问五人至少合伙捕到多少条都按同样的办法分鱼。问五人至少合伙捕到多少条都按同样的办法分鱼。问五人至少合伙捕到多少条鱼？每个人醒来后看到的鱼数是多少条？鱼？每个人醒来后看到的鱼数是多少条
19、？鱼？每个人醒来后看到的鱼数是多少条？鱼？每个人醒来后看到的鱼数是多少条？第39页/共174页解题思路解题思路:假定假定假定假定A A、B B、C C、D D、E E 五人的编号分别为五人的编号分别为五人的编号分别为五人的编号分别为1 1、2 2、3 3、4 4、5 5，整数数组，整数数组，整数数组，整数数组 fishk fishk 表示第表示第表示第表示第 k k 个人所个人所个人所个人所看到的鱼数。看到的鱼数。看到的鱼数。看到的鱼数。fish1 fish1 表示表示表示表示A A所看到的鱼数，所看到的鱼数，所看到的鱼数，所看到的鱼数，fish2 fish2 表示表示表示表示 B B 所看到
20、的鱼数所看到的鱼数所看到的鱼数所看到的鱼数fish1 fish1 为五人合伙捕鱼的总鱼数为五人合伙捕鱼的总鱼数为五人合伙捕鱼的总鱼数为五人合伙捕鱼的总鱼数fish2=(fish1-1)*4/5fish2=(fish1-1)*4/5fish3=(fish2-1)*4/5fish3=(fish2-1)*4/5fish4=(fish3-1)*4/5fish4=(fish3-1)*4/5fish5=(fish4-1)*4/5fish5=(fish4-1)*4/5第40页/共174页写成一般式fish i =(fish i -1 1)*4/5i=2,3,5这个公式可用于知 A 看到的鱼数去推算 B 看到
21、的，再推算 C 看到的，.。现在要求的是 A 看到的，能否倒过来，先知 E 看到的再反推 D 看到的，直到A看到的。为此将上式改写为：fish i-1 =fish i *5/4+1i=5,4,2第41页/共174页分析上式.当 i=5 时，fish 5 表示 E 醒来所看到的鱼数，该数应满足被整除后余，即fish 5%5 =1 2.当 i=5 时，fish i-1 表示 D 醒来所看到的鱼数，这个数既要满足fish 4 =fish 5 *5/4+1 又要满足fish 4%5=1显然，fish 4 不能不是整数，这个结论同样可以用至 fish 3,fish 2 和 fish 1 第42页/共17
22、4页3.按题意要求 5 人合伙捕到的最少鱼数，可以从小往大枚举，可以先让 E 所看到的鱼数最少为 6 条，即 fish 5 初始化为 6 来试，之后每次增加 5 再试，直至递推到 fish 1 得整数且除以 5 之后的余数为 1。根据上述思路，我们可以构思如下的程序框图：第43页/共174页第44页/共174页该图可分为三部分该图可分为三部分(1)是说明部分：包含定义数组是说明部分：包含定义数组 fish6，并初始化为，并初始化为 1 和和定义循环控制变量定义循环控制变量 i，并初始化为，并初始化为 0。(2)是是 do.while 直到型循环，其循环体又含两块：直到型循环，其循环体又含两块：
23、(2).1 是枚举过程中的是枚举过程中的 fish5 的初值设置，一开始的初值设置，一开始 fish5=1+5;以后每次增以后每次增 5。(2).2 是一个是一个 for 循环，循环，i 的初值为的初值为 4，终值为，终值为 1，步长，步长为为-1，该循环的循环体是一个分支语句，该循环的循环体是一个分支语句，如果如果 fishi+1不能被不能被 4 整除，则跳出整除，则跳出 for 循环（使用循环（使用 break 语句）语句）;否则，从否则，从 fishi+1 算出算出 fishi。第45页/共174页当由 break 语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令
24、fish 5 加 5 后再试，即重新进入直到型循环 do while 的循环体。当着正常退出 for 循环时，一定是控制变量 i 从初值 4，一步一步执行到终值 1，每一步的鱼数均为整数，最后 i=0，表示计算完毕，且也达到了退出直到型循环的条件。(3)输出计算结果第46页/共174页/*/*程 序 名：5_3.c（五人合伙捕鱼）*/*作 者：wuwh */*编制时间：2002年10月2日 */*主要功能：递推算法的实现 */*#include /预编译命令void main()/主函数 int fish6=1,1,1,1,1,1;/整型数组，记录每人醒来后看到的鱼数 int i=0;do f
25、ish5=fish5+5;/让E看到的鱼数增5。for(i=4;i=1;i-)if(fishi+1%4!=0)break;/跳出for循环elsefishi=fishi+1*5/4+1;/计算第i人看到的鱼数 while(i=1);/当 i=1 继续做do循环 /输出计算结果 for(i=1;i1 时，时，A 的取值即的取值即 C 的值，而的值，而 C 的值即的值即 E 的值，为了求得的值，为了求得 E 的值，需要先求出的值，需要先求出 D 的值。的值。D 值值 fact(n-1)乘以乘以 n 即为即为 E 的值。的值。第55页/共174页与结点可能有多个相关联的点，这时可描述为下图与结点可能
26、有多个相关联的点，这时可描述为下图A 结点的值最终为结点的值最终为 D 的值，但为了求的值，但为了求 D 需先求需先求 B 和和 C。从图上看。从图上看,先求左边的点才能求最右边的点的先求左边的点才能求最右边的点的值，我们约定最右边值，我们约定最右边 D 点的值就是点的值就是 A 结点的值。结点的值。第56页/共174页下面我们以下面我们以3！为例来画与或结点图，目的是体！为例来画与或结点图，目的是体会递归的含义。会递归的含义。C=1D=2*C=2B=D=2E=3*B=3*2=6A=E=6第57页/共174页下面画出了调用和返回的递归示意图下面画出了调用和返回的递归示意图第58页/共174页从
27、图可以想象：从图可以想象：欲求欲求 fact(3)，先要求，先要求 fact(2)；要求；要求 fact(2)先先求求 fact(1)。就象剥一颗圆白菜，从外向里，一层层。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到剥下来，到了菜心，遇到 1 的阶乘，其值为的阶乘，其值为1，到达，到达了递归的边界。然后再用了递归的边界。然后再用 fact(n)=n*fact(n-1)这个这个普遍公式，从里向外倒推回去得到普遍公式，从里向外倒推回去得到 fact(n)的值。的值。为了把这个问题说得再透彻一点。我们画了如下为了把这个问题说得再透彻一点。我们画了如下的流程图：的流程图：第59页/共174
28、页第60页/共174页为了形象地描述递归过程，将上图改画成下图为了形象地描述递归过程，将上图改画成下图第61页/共174页在这个图中在这个图中“内层内层”与与“外层外层”有着相同的结构。它有着相同的结构。它们之间们之间“你中有我，我中有你你中有我，我中有你”，呈现相互依存的关，呈现相互依存的关系。系。为了进一步讲清递归的概念，将递归与递推做一比较。为了进一步讲清递归的概念，将递归与递推做一比较。仍以求阶乘为例。仍以求阶乘为例。递推是从已知的初始条件出发，逐次去求所需要的阶递推是从已知的初始条件出发，逐次去求所需要的阶乘值。乘值。如求如求 3！初始条件初始条件 fact(1)=1fact(2)=
29、2*fact(1)=2fact(3)=3*fact(2)=6第62页/共174页这相当于从菜心这相当于从菜心“推到推到”外层。而递归算法的出外层。而递归算法的出发点不放在初始条件上，而放在求解的目标上，从所发点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。就本例而言，读者会认为递的边界（即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。但许多实际问归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的递推关系，这时递题不可能或不容易找到显而易
30、见的递推关系，这时递归算法就表现出了明显的优越性。下面我们将会看到，归算法就表现出了明显的优越性。下面我们将会看到，递归算法比较符合人的思维方式，逻辑性强，可将问递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解，题描述得简单扼要，具有良好的可读性，易于理解，许多看来相当复杂，或难以下手的问题，如果能够使许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处理。下面举一个尽用递归算法就会使问题变得易于处理。下面举一个尽人皆知的例子哈诺（人皆知的例子哈诺（Hanoi）塔问题。）塔问题。第63页/共174页故事：故事：相传在古代印度的相
31、传在古代印度的 Bramah 庙中，有位僧人整天把三庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把根柱子上的金盘倒来倒去，原来他是想把64个一个比个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将照上述规则将64只盘子从一个柱子移至另一个柱子上，只盘
32、子从一个柱子移至另一个柱子上，所需时间约为所需时间约为5800亿年。亿年。第64页/共174页怎样编写这种程序？思路上还是先从最简单的情况分析怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盘子，假定盘号为柱上只有一只盘子，假定盘号为1，这时只，这时只需将该盘从需将该盘从A搬至搬至C，一次完成，记为，一次完成，记为move 1 from A to C (演示演示)ABC1第65页/共174页2、在、在A柱上有二只盘子，柱上有二只盘子，1为小盘，为小盘，2为大盘。为大盘。第（第（1）步将）步将1号盘从号盘从A移至移至
33、B，这是为了让，这是为了让2号盘能移动；号盘能移动；第（第（2）步将）步将2号盘从号盘从A移至移至C；第（第（3）步再将）步再将1号盘从号盘从B移至移至C；这三步记为（演示）：这三步记为（演示）：ABC21move 1 from A to B;move 2 from A to C;move 3 form B to C;第66页/共174页3、在、在A柱上有柱上有3只盘子，从小到大分别为只盘子，从小到大分别为1号，号，2号，号，3号号第（第（1）步）步 将将1号盘和号盘和2号盘视为一个整体；先将二者作号盘视为一个整体；先将二者作为整体从为整体从A移至移至B，给，给3号盘创造能够一次移至号盘创造能
34、够一次移至C的机会。的机会。这一步记为这一步记为 move(2,A,C,B)意思是将上面的意思是将上面的2只盘子作为整体从只盘子作为整体从A借助借助C移至移至B。第（第（2）步）步 将将3号盘从号盘从A移至移至C，一次到位。记为，一次到位。记为 move 3 from A to C第（第（3）步）步 处于处于B上的作为一个整体的上的作为一个整体的2只盘子，再移至只盘子，再移至C。这一步记为这一步记为 move(2,B,A,C)意思是将意思是将2只盘子作为整体从只盘子作为整体从B借助借助A移至移至C。所谓借助是什么意思，等这件事做完了不言自明。所谓借助是什么意思，等这件事做完了不言自明。第67页
35、/共174页move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(2,B,A,C)ABC213演示：移动演示：移动3 3个个盘子盘子的分解的分解第68页/共174页move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(1,A,C,B)move(1,C,A,B)move(1,A,B,C)move(2,B,A,C)move(1,B,C,A)move(1,B,A,C)move(1,A,B,C)ABC213第69页/共174页4、从题目的约束条件看，大盘上可以随便摞小、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将盘，相
36、反则不允许。在将1号和号和2号盘当整体从号盘当整体从A移至移至B的过程中的过程中 move(2,A,C,B)实际上是分实际上是分解为以下三步解为以下三步第（第（1）.1步：步：move 1 form A to C;第（第（1）.2步：步：move 2 form A to B;第（第（1）.3步：步：move 1 form C to B;第70页/共174页经过以上步骤，将经过以上步骤，将 1 号和号和 2 号盘作为整体号盘作为整体从从 A 移至移至 B，为，为 3 号盘从号盘从 A 移至移至 C 创造了条创造了条件。同样，件。同样，3号盘一旦到了号盘一旦到了 C，就要考虑如何，就要考虑如何实现
37、将实现将 1 号和号和 2 号盘当整体从号盘当整体从 B 移至移至 C 的过的过程了。实际上程了。实际上 move(2,B,A,C)也要分解为三也要分解为三步：步：第（第（3）.1步：步：move 1 form B to A;第（第（3）.2步：步：move 2 form B to C;第（第（3）.3步：步：move 1 form A to C;第71页/共174页5、看、看 move(2,A,C,B)是说要将是说要将 2 只盘子从只盘子从 A 搬至搬至 B，但没有，但没有 C 是不行的，因为第（是不行的，因为第（1）.1步就要将步就要将 1 盘从盘从 A 移到移到 C，给，给 2 盘创造条
38、件盘创造条件从从 A 移至移至 B，然后再把，然后再把 1 盘从盘从 C 移至移至 B。看。看到这里就能明白借助到这里就能明白借助 C 的含义了。因此，在的含义了。因此，在构思搬移过程的参量时，要把构思搬移过程的参量时，要把 3 个柱子都用上。个柱子都用上。第72页/共174页6、定义搬移函数、定义搬移函数 move(n,A,B,C)，物理意义是，物理意义是将将 n 只盘子从只盘子从 A 经经 B 搬到搬到 C考虑到前面已考虑到前面已经研究过的经研究过的(1)(2)(3)步，可步，可以将搬移过程以将搬移过程用如下的与或用如下的与或结点图表示。结点图表示。第73页/共174页这里用与或结点的含义
39、是分解为这里用与或结点的含义是分解为(1)(2)(3)步。这步。这3步是相关的，相互依存的，而且是有序的，从左至右步是相关的，相互依存的，而且是有序的，从左至右执行。执行。move(n,A,B,C)分解为分解为3步步(1)move(n-1,A,C,B)理解为将上面的理解为将上面的n-1只盘子作为一只盘子作为一个整体从个整体从A经经C移至移至B；(2)输出输出n：A to C，理解将，理解将n号盘从号盘从A移至移至C，是直接可，是直接可解结点；解结点；(3)Move(n-1,B,A,C)理解为将上面的理解为将上面的n-1只盘子作为一只盘子作为一个整体从个整体从B经经A移至移至C。第74页/共17
40、4页这里显然是一种递归定义，当着解这里显然是一种递归定义，当着解 move(n-1,A,C,B)时又可想到，将其分解为时又可想到，将其分解为 3 步：步：第第1步：将上面的步：将上面的n-2只盘子作为一个整体从只盘子作为一个整体从A经经B到到C，move(n-2,A,B,C)；第第2步：第步：第n-1号盘子从号盘子从A直接移至直接移至B，即，即n-1:A to B；第第3步：再将上面的步：再将上面的n-2只盘子作为一个整体从只盘子作为一个整体从C经经A移至移至B，move(n-2,C,A,B)；下面，我们还是以下面，我们还是以3只盘子为例画出递归的与或图。只盘子为例画出递归的与或图。第75页/
41、共174页这个图很象一颗倒置着的树，结点这个图很象一颗倒置着的树，结点move(3,A,B,C)是树是树根，与结点是树的分枝，叶子都是直接可解结点。根，与结点是树的分枝，叶子都是直接可解结点。第76页/共174页第77页/共174页第78页/共174页/*/*程程 序：序：6_hanoi2002.cpp */*作作 者：者：wuwh */*编制时间：编制时间：2002年年10月月13日日 */*主要功能：用递归求解主要功能：用递归求解Hanoi问题问题 */*#include/预编译命令预编译命令int step=1;/整型全局变量整型全局变量,预置预置1,步数步数void move(int
42、m,char p,char q,char r);/声明要用到的被调用函数声明要用到的被调用函数void main()/主函数主函数/主程序开始主程序开始int n;/整型变量整型变量,n为盘数为盘数,printf(请输入盘数请输入盘数 n=“);/提示信息提示信息scanf(“/%d”),&n);/输入正整数输入正整数nprintf(在在3根柱子上移根柱子上移%d只盘的步骤为只盘的步骤为:“,n);/输出提示信息输出提示信息 move(n,a,b,c);/调用函数调用函数 move(n,a,b,c)/主函数结束主函数结束第79页/共174页/以下函数是被主程序调用的函数以下函数是被主程序调用的
43、函数/函数名：函数名：move/输输 入：入：m，整型变量，表示盘子数目，整型变量，表示盘子数目/p，q，r为字符型变量，表示柱子标号为字符型变量，表示柱子标号/返回值：无返回值：无void move(int m,char p,char q,char r)/自定义函数体开始自定义函数体开始if(m=1)/如果如果m为为1,则为直接可解结点则为直接可解结点,/直接可解结点直接可解结点,输出移盘信息输出移盘信息printf(%d move 1#from p to r”,step);step+;/步数加步数加1else/如果不为如果不为1,则要调用则要调用move(m-1)move(m-1,p,r,
44、q);/递归调用递归调用move(m-1)/直接可解结点直接可解结点,输出移盘信息输出移盘信息 printf(%d move%d from p to r”,step,m);step+;/步数加步数加1move(m-1,q,p,r);/递归调用递归调用move(m-1)/自定义函数体结束自定义函数体结束第80页/共174页第81页/共174页 mn|n=1 c(m,n)m=0|n=0 n=m n!=m c(m-1,n)c(m-1,n-1)c(m-1,n)+c(m-1,n)c(m-1,n-1)c(m-1,n)+c(m-1,n-1)c(m-1,n-1)0 m 10 m 1第82页/共174页/*/*
45、程程 序：序：6_7.cpp */*编制时间：编制时间：2002年年10月月28日日 */*主要功能：计算组和数主要功能：计算组和数C(m,n)*/*#include /预编译命令预编译命令Using namespace std;第83页/共174页/计算C(m,n)，即从m个数中取n个数的组合数int C(int m,int n)if(m0|n0|mn)return 0;if(m=n)/C(m,m)=1return 1;if(n=1)/C(m,1)=mreturn m;/C(m,n)=C(m-1,n)+C(m-1,n-1)return C(m-1,n)+C(m-1,n-1);第84页/共17
46、4页int main()/主函数开始主函数开始/测试一些结果测试一些结果cout C(6,0)=Cmn(6,0)endl;cout C(6,1)=Cmn(6,1)endl;cout C(6,2)=Cmn(6,2)endl;cout C(6,6)=Cmn(6,6)Y Y；2#2#青蛙从青蛙从 L L S S；1#1#青蛙从青蛙从 Y Y S S；3#3#青蛙从青蛙从 L L Y Y；4#4#青蛙从青蛙从 L L R R；3#3#青蛙从青蛙从 Y Y R R；1#1#青蛙从青蛙从 S S Y Y；2#2#青蛙从青蛙从 S S R R；1#1#青蛙从青蛙从 Y Y R R；第91页/共174页t t
47、L LS SY YRRL4L4L3L3L2L2L1L1S2S2S1S1R4R4R3R3R2R2R1R10 01 12 23 34 45 56 67 78 89 94 44 44 44 44 43 33 33 33 32 22 21 12 22 22 22 22 21 11 11 11 11 13 31 11 14 44 44 44 44 43 33 33 33 32 22 21 1表一表一第92页/共174页 为了将过河过程描述得更清楚，我们给出了表为了将过河过程描述得更清楚，我们给出了表1 1。表。表中中L1 L2 L3 L4L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。表示
48、左岸石柱上落在一起的青蛙的高度位置。L1 L1 在最上面，在最上面，L4 L4 在最下面的位置。引入这个信息就可比在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理较容易地看出对青蛙占位的约束条件。同理R1 R2 R3 R4R1 R2 R3 R4也也是如此。对水中石柱是如此。对水中石柱S S，也分成两个高度位置，也分成两个高度位置S1 S2S1 S2。对荷。对荷叶叶Y Y无须分层，因为它只允许一只青蛙落在其上。无须分层，因为它只允许一只青蛙落在其上。t=0t=0为初为初始时刻，青蛙从小到大落在石柱始时刻，青蛙从小到大落在石柱L L上。上。t=1t=1为第一步：为第一步：1
49、#1#从从L L跳至荷叶跳至荷叶Y Y上；上；L L上只剩上只剩2#3#4#2#3#4#。T=2 T=2 为第二步；为第二步；2#2#从从L L跳跳至石柱至石柱S S上，处在上，处在S2S2位置上，位置上，L L上只剩上只剩3#3#和和4#4#。T=3T=3为第三步，为第三步，1#1#从从Y Y跳至跳至S S，将，将Y Y清空。这时你看，清空。这时你看，S S上有上有1#1#、2#2#，L L上有上有3#3#、4#4#，好象是原来在，好象是原来在L L上的上的4 4只青蛙，分成了上下两部分，上只青蛙，分成了上下两部分，上面的面的2 2只通过荷叶只通过荷叶y y转移到了转移到了S S上。这一过程
50、是一分为二的过上。这一过程是一分为二的过程。即将程。即将L L上的一队青蛙，分解为两个队，每队各二只，且上的一队青蛙，分解为两个队，每队各二只，且将上面的二只转移到了将上面的二只转移到了S S上。这时我们可以考虑形成两个系上。这时我们可以考虑形成两个系统，一个是统，一个是L L，Y Y，R R系统，一个是系统，一个是S S，Y Y，R R系统。前者二只系统。前者二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。从第五步到第九步可以看出的确是这么做的。第93页/共174页 2YRSL31第94页/共