资源描述
第5章 函数(hnsh)第1页/共174页第一页，共174页。第5章 函数(hnsh) 第2页/共174页第二页，共174页。/ */ * 程 序：6_3.cpp（验证素数程序） */ * 作 者：wuwh */ * 编制时间：2002年10月20日 */ * 主要功能：可验证某数是否为素数 */ *#include / 预编译命令#include / 预编译命令int checkprime( int );/ 子函数声明int main()/ 主函数int a=0;/ 定义整型变量，初始化为0cout a;/ 键盘输入一个整数/ 用实参a调用(dioyng)子函数，该子函数的/ 返回值作为if语句的分支条件if ( checkprime(a) ) / checkprime(a)为1cout a 是素数 endl;else/ checkprime(a)为0cout a 不是素数 endl;/ 主函数结束第第5章章 函数函数(hnsh)第3页/共174页第三页，共174页。/ 用实参 a 调用子函数，该子函数的/ 返回值作为 if 语句的分支条件if ( checkprime( a ) ) / checkprime( a ) 为 1cout a 是素数(s sh) endl;else / checkprime( a ) 为 0 cout a 不是素数(s sh) endl;/ 主函数结束第5章 函数(hnsh)第4页/共174页第四页，共174页。 T checkprime( a ) F cout a cout a 是素数(s sh) endl; 不是素数(s sh) endl 第5章 函数(hnsh)第5页/共174页第五页，共174页。bool checkprime(int b)/ 子函数，子函数，b为形式参数为形式参数int k=0; / 定义整型变量，并初始化定义整型变量，并初始化for (k=2; k=sqrt(double)b); k+)/ 循环循环if (b%k = 0)/ 如果如果b能够能够(nnggu)被被k整除，则整除，则返回返回0/ 可理解为可理解为“抢先抢先”返回返回0，有了，有了 return 0，/ 后面的后面的 return 1 不起作用了不起作用了return 0;return 1;/ b不能被不能被k整除，则返回整除，则返回1第5章 函数(hnsh)第6页/共174页第六页，共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章 函数(hnsh)第7页/共174页第七页，共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 / 说明说明(shumng) b 是质数是质数第5章 函数(hnsh)第8页/共174页第八页，共174页。 讲这一程序的目的：讲这一程序的目的：如何定义一个函数如何定义一个函数主函数怎样主函数怎样(znyng)调用子函数调用子函数实在参数和形式参数实在参数和形式参数返回值是什么意思返回值是什么意思第9页/共174页第九页，共174页。 主函数与子函数的配合: 主函数通过(tnggu)实参去调用子函数将实参赋给子函数中的形参； 子函数运算之后，又将调用结果返回给主函数一个值，这个值作为主函数判断该实参是素数与否的根据。 两者配合得天衣无缝。第5章 函数(hnsh)第10页/共174页第十页，共174页。 在checkprime( int b ) 函数中，有return 0 和 return 1 两处不同。如果先有return 0了，后面(hu mian)一条return 1 就不起作用了。不会既执行 return 0 又执行 return 1。第5章 函数(hnsh)第11页/共174页第十一页，共174页。 函数的说明(shumng) 放在主函数之前，告诉系统有 自定义的子函数可以被调用。 例： bool checkprime( int );第12页/共174页第十二页，共174页。 函数的定义函数返回值的类型(lixng) 函数名(类型(lixng)名 形式参数1，类型(lixng)名 形式参数2，. . . )/ 函数体 说明部分 语句部分第13页/共174页第十三页，共174页。 形式参数和实在参数 bool checkprime( int af ); /定义 af 是形式参数， 特点： 1.未被调用不占内存单元； 2.被调用后系统为其分配内存单元； 3.调用结束( jish)释放内存单元； 4.作用域限定在子函数内，属于局部变量。第14页/共174页第十四页，共174页。 被调用函数(hnsh)嵌套在 if 语句中，a 是实在参数 if ( checkPrime( a ) )主函数(hnsh) 调用 checkPrime( af ) 子函数(hnsh) 形式参数第15页/共174页第十五页，共174页。 实在参数是一个具有确定(qudng)值的表达式 一个函数在调用子函数时，要将实在参数赋给形式参数 调用时 17 17 实在参数 a 形式参数 af第16页/共174页第十六页，共174页。 调用 输入a 子函数 if (checkPrime(a) checkPrime(af) 执行(zhxng) if 语句 for: i=2,3 =1 =0 af%i=0 !=0 输出 输出 return 0 return 1 a是质数 a不是质数 返回第17页/共174页第十七页，共174页。 int main()int a=0; cout a;if ( checkprime(a) ) 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 是素数(s sh) endl; elsecout a 不是素数(s sh) endl; 第18页/共174页第十八页，共174页。 美声唱法歌手大奖赛 裁判人数 n=10, 打分范围 60= x = 100, 10人中(rnzhng)打分的最大值 max 10人中(rnzhng)打分的最小值 min 10人打分总和为 sum 选手最后得分为: ( sum Max Min )/ ( N 2 )第19页/共174页第十九页，共174页。/ */ * 程 序：6_2.cpp * / * 作 者：wuwh * / * 编制时间：2002年10月20日 */ * 主要(zhyo)功能：给歌手打分 */ *第20页/共174页第二十页，共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页第二十一页，共174页。 for ( i = 1; i=10; i = i+1 ) cout“请第” i “位裁判给分” x ; p = Max( x, p ); q = Min( x, q ); sum = sum + x ; cout“选手(xunshu)得分 ”b ) return a ; else return b ; int Min( int c , int d ) if ( c d ) return c ; else return d ; 第23页/共174页第二十三页，共174页。 1nkxx4444441 2 3 4 5 6 p o w e r ( , )li li i=1,2,n l = k第24页/共174页第二十四页，共174页。 让 l = 4 , i = 1,2, . . . , 6这个函数(hnsh)可以表示4441 , 2, 61SOP( , )power( , )mim li l第25页/共174页第二十五页，共174页。/ */ * 程 序：6_2.cpp */ * 作 者：wuwh */ * 编制时间：2002年10月12日 */ * 主要功能(gngnng)：求幂函数的和（介绍函数） */ *第26页/共174页第二十六页，共174页。#include / 预编译命令const int n = 6; / 定义常量 n 为 6const int k = 4; / 定义常量 k 为 4int SOP(int m, int l); / 声明(shngmng)函数SOPint power(int p, int q);/ 声明(shngmng)函数power第27页/共174页第二十七页，共174页。/ 输出(shch)结果, 其中SOP(n,k)为被调用函数int main()/ 主函数cout Sum of k / 提示信息 from th powers of integers 1 to n is SOP(n,k) endl;第28页/共174页第二十八页，共174页。/以下(yxi)函数是被主程序调用的函数/ 功能：计算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页第二十九页，共174页。/ 以下(yxi)函数是被函数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页第三十页，共174页。 int SOP(int m, int l) 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页第三十一页，共174页。数据类型 函数(hnsh)名( 形式参数表 )例例: int power(int p, int n)power 为函数名，要以英文字母开头为函数名，要以英文字母开头(ki tu)。int 是函数值的数据类型，这里是是函数值的数据类型，这里是int（整型）。（整型）。(int p, int n) 括号中的括号中的 p, n为函数的形式参数，形式参数为函数的形式参数，形式参数也要定义其数据类型。也要定义其数据类型。第32页/共174页第三十二页，共174页。函数定义的一般(ybn)格式： ()第33页/共174页第三十三页，共174页。形式参数与实在(shzi)参数1、形式参数是在定义函数时放在函数名后括号中的参数。在未进、形式参数是在定义函数时放在函数名后括号中的参数。在未进行函数调用时，并不对形式参数分配内存单元。在发生函数调用行函数调用时，并不对形式参数分配内存单元。在发生函数调用时，立刻给形式参数分配内存单元。调用结束后，释放掉行参所时，立刻给形式参数分配内存单元。调用结束后，释放掉行参所占的内存单元。占的内存单元。2、因此，形参变量属于局部变量，其作用域在它所在的函数体内。、因此，形参变量属于局部变量，其作用域在它所在的函数体内。3、在定义函数的时候、在定义函数的时候(sh hou)，必须指定形参变量的类型，如下所，必须指定形参变量的类型，如下所示示int power(int p, int n) / 函数函数(hnsh)体体 c第34页/共174页第三十四页，共174页。4、实在参数是一个具有确定值的表达式。函数在调用时，将实在参数赋给形式参数。比如，主函数调用SOP(n,k)，这时，n,k为实在参数，n的值为6，k的值为4。在被调用函数定义中，int SOP(m,l) 中的 m, l 为形式参数，在SOP被调用时，系统给 m, l 这两个形式参数分配(fnpi)了内存单元。之后，n 的值 6 赋给 m; k 的值 4 赋给 l。第35页/共174页第三十五页，共174页。power( i, l ) 处在 SOP( m, l ) 函数中，表示SOP函数去调用(dioyng) 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 为实在参数，调用(dioyng)power( p, q )，两个形式参数 p, q 分别被赋以 1，4 。第36页/共174页第三十六页，共174页。 执行执行 SOP(6,4) l=4 sum=0 i=1: sum = sum + power(i,l) = 0 + 1 = 1 i=2: sum = sum + power(i,l) = 1 + 16 = 17 i=3: sum = sum + power(i,l) = 17 + 81 = 98 i=4: sum = sum + power(i,l) = 98 + 256 = 354 i=5: sum = sum + power(i,l) = 354 + 625 = 979 i=6: sum = sum + power(i,l) = 979 + 1296 = 2275 return (sum) 2275 返回返回 执行执行 power(1, 4): product = 1*1*1*1 return(1) = 1 调用 返回 执行执行 power(2, 4): product = 2*2*2*2 return(16) = 16 调用 返回 执行执行 power(3, 4): product = 3*3*3*3 return(81) = 81 调用 返回 执行执行 power(4, 4): product = 4*4*4*4 return(256) = 256 调用 返回 执行执行 power(5, 4): product = 5*5*5*5 return(625) = 625 调用 返回 执行执行 power(6, 4): product = 6*6*6*6 return(1296) = 1296 调用 返回 SOP(n,k) 调用调用 第37页/共174页第三十七页，共174页。递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单运算，充分发挥计算机长于重复处理的特点(tdin)，现举一例递递 推推第38页/共174页第三十八页，共174页。第39页/共174页第三十九页，共174页。第40页/共174页第四十页，共174页。写成一般(ybn)式fish i = ( fish i - 1 1 ) * 4 / 5i = 2, 3, ,5这个公式可用于知 A 看到的鱼数去推算 B 看到的，再推算 C 看到的，.。现在要求的是 A 看到的，能否倒过来，先知 E 看到的再反推 D 看到的，直到A看到的。为此将上式改写为：fish i-1 = fish i * 5 / 4 +1i = 5, 4,2第41页/共174页第四十一页，共174页。分析上式. 当 i = 5 时，fish 5 表示 E 醒来所看到的鱼数，该数应满足(mnz)被整除后余，即fish 5 % 5 = 1 2. 当 i = 5 时，fish i-1 表示 D 醒来所看到的鱼数，这个数既要满足(mnz)fish 4 = fish 5 * 5 / 4 + 1 又要满足(mnz)fish 4 % 5 = 1显然，fish 4 不能不是整数，这个结论同样可以用至 fish 3 , fish 2 和 fish 1 第42页/共174页第四十二页，共174页。3 . 按题意要求 5 人合伙捕到的最少鱼数，可以从小往大枚举，可以先让 E 所看到的鱼数最少为 6 条，即 fish 5 初始化为 6 来试，之后每次增加 5 再试，直至递推到 fish 1 得整数(zhngsh)且除以 5 之后的余数为 1。根据上述思路，我们可以构思如下的程序框图：第43页/共174页第四十三页，共174页。 定义数组 fish6，并初始化为 1； 定义循环控制变量 i，并初始化为 0。 输出计算结果 fish1至 fish5 do while(i=1); fish5=fish5+5; / .1 for ( i=4; i=1; i- ) / .2 fishi+1%4 != 0 true false break; /退出 for 循环 fishi = fishi+1*5/4+1; 第44页/共174页第四十四页，共174页。该图可分为三部分该图可分为三部分(1) 是说明部分：包含定义数组是说明部分：包含定义数组 fish6，并初始化为，并初始化为 1 和定义和定义循环控制变量循环控制变量 i，并初始化为，并初始化为 0。(2) 是是 do.while 直到型循环，其循环体又含两块：直到型循环，其循环体又含两块：(2).1 是枚举过程中的是枚举过程中的 fish5 的初值设置的初值设置(shzh)，一开始，一开始 fish5=1+5; 以后每次增以后每次增 5。(2).2 是一个是一个 for 循环，循环，i 的初值为的初值为 4，终值为，终值为 1，步长为，步长为 -1，该循环的循环体是一个分支语句，该循环的循环体是一个分支语句， 如果如果 fishi+1不能被不能被 4 整除，则跳出整除，则跳出 for 循环（使用循环（使用 break 语句）语句）; 否则，从否则，从 fishi+1 算出算出 fishi。第45页/共174页第四十五页，共174页。当由 break 语句让程序退出(tuch)循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令fish 5 加 5 后再试，即重新进入直到型循环 do while 的循环体。当着正常退出(tuch) for 循环时，一定是控制变量 i 从初值 4，一步一步执行到终值 1，每一步的鱼数均为整数，最后 i = 0，表示计算完毕，且也达到了退出(tuch)直到型循环的条件。(3) 输出计算结果第46页/共174页第四十六页，共174页。/*/* 程 序 名：5_3.c（五人合伙捕鱼） */* 作 者：wuwh */* 编制时间：2002年10月2日 */* 主要功能：递推算法的实现 */*#include / 预编译(biny)命令void main() /主函数 int fish6=1,1,1,1,1,1; / 整型数组，记录每人醒来后看到的鱼数 int i=0; do fish5=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 的值。的值。A fact(n)Bfact(1)=1Cn1n=1Dfact(n-1)En*fact(n-1)第55页/共174页第五十五页，共174页。与结点与结点(ji din)可能有多个相关联的点，这时可描述为下图可能有多个相关联的点，这时可描述为下图A 结点的值最终为结点的值最终为 D 的值，但为了求的值，但为了求 D 需先求需先求 B 和和 C。从图上看。从图上看, 先求左边先求左边(zu bian)的点才能求最右的点才能求最右边的点的值，我们约定最右边边的点的值，我们约定最右边 D 点的值就是点的值就是 A 结点的结点的值。值。ABDC第56页/共174页第五十六页，共174页。下面我们以下面我们以3！为例来画与或结点图，目的是体会！为例来画与或结点图，目的是体会(thu)递归的含义。递归的含义。C = 1D = 2*C = 2B = D = 2E = 3*B = 3*2 = 6A = E = 61=1131Bfact(2)3*fact(2)fact(3)Cfact(1)D2*fact(1)AE21第57页/共174页第五十七页，共174页。下面画出了调用下面画出了调用(dioyng)和返回的递归示意图和返回的递归示意图 Bfact(2)fact(2)=2*fact(1)=2*fact(1)=2*1=2*1=2=2返回返回 DAfact(3)fact(3)=3*fact(2)=3*fact(2)=3*2=3*2=6=6E E返回返回 Cfact(1)=1调用调用调用调用第58页/共174页第五十八页，共174页。从图可以想象：从图可以想象：欲求欲求 fact( 3 )，先要求，先要求 fact( 2 )；要求；要求 fact( 2 ) 先求先求 fact( 1 )。就象剥一颗圆白菜，从外向里，一层层剥下来，。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到到了菜心，遇到 1 的阶乘的阶乘(ji chn)，其值为，其值为1，到达了递，到达了递归的边界。然后再用归的边界。然后再用 fact( n )=n*fact( n-1 ) 这个普遍公式，这个普遍公式，从里向外倒推回去得到从里向外倒推回去得到 fact( n ) 的值。的值。为了把这个问题说得再透彻一点。我们画了如下的流为了把这个问题说得再透彻一点。我们画了如下的流程图：程图：第59页/共174页第五十九页，共174页。 31 fact(3) 真真 假假 调调用用 fact(2) 计计算算 3*fact(2) fact(2) fact(1) 21 真真 假假 调调用用 fact(1) 计计算算 2*fact(1) 11 真真 假假 fact(1) 1 返返回回 返返回回 第60页/共174页第六十页，共174页。为了形象地描述为了形象地描述(mio sh)递归过程，将上图改画成下递归过程，将上图改画成下图图 fact(3) 真真 假假 3=1 调调用用 fact(2) 真真 假假 假假 真真 2=1 1=1 fact(2)=2*fact(1) 返返回回 fact(3)=3*fact(2) 返返回回 调调用用 fact(1) fact(1) =1 返返回回 第61页/共174页第六十一页，共174页。在这个图中在这个图中“内层内层”与与“外层外层”有着相同的结构。它们之有着相同的结构。它们之间间“你中有我，我中有你你中有我，我中有你”，呈现相互依存的关系。，呈现相互依存的关系。为了进一步讲清递归的概念为了进一步讲清递归的概念(ginin)，将递归与递推，将递归与递推做一比较。仍以求阶乘为例。做一比较。仍以求阶乘为例。递推是从已知的初始条件出发，逐次去求所需要的阶递推是从已知的初始条件出发，逐次去求所需要的阶乘值。乘值。如求如求 3！初始条件初始条件 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2fact( 3 ) = 3 * fact( 2 ) = 6第62页/共174页第六十二页，共174页。这相当于从菜心这相当于从菜心“推到推到”外层。而递归算法的出发外层。而递归算法的出发点不放在初始条件上，而放在求解点不放在初始条件上，而放在求解(qi ji)的目标上，的目标上，从所求的未知项出发逐次调用本身的求解从所求的未知项出发逐次调用本身的求解(qi ji)过过程，直到递归的边界（即初始条件）。就本例而言，程，直到递归的边界（即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。读者会认为递归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的递但许多实际问题不可能或不容易找到显而易见的递推关系，这时递归算法就表现出了明显的优越性。推关系，这时递归算法就表现出了明显的优越性。下面我们将会看到，递归算法比较符合人的思维方下面我们将会看到，递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解，许多看来相当复杂，或难好的可读性，易于理解，许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题以下手的问题，如果能够使用递归算法就会使问题变得易于处理。下面举一个尽人皆知的例子哈诺变得易于处理。下面举一个尽人皆知的例子哈诺（Hanoi）塔问题。）塔问题。第63页/共174页第六十三页，共174页。故事：故事：相传在古代印度的相传在古代印度的 Bramah 庙中，有位僧人整天把三根庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把柱子上的金盘倒来倒去，原来他是想把64个一个比一个个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面落在小盘上面(shng min)。有人会觉得这很简单，真。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将照上述规则将64只盘子从一个柱子移至另一个柱子上，只盘子从一个柱子移至另一个柱子上，所需时间约为所需时间约为5800亿年。亿年。 第64页/共174页第六十四页，共174页。怎样编写这种程序？思路上还是怎样编写这种程序？思路上还是(hi shi)先从最简单的情况分先从最简单的情况分析起，搬一搬看，慢慢理出思路。析起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盘子，假定柱上只有一只盘子，假定(jidng)盘号为盘号为1，这时，这时只需将该盘从只需将该盘从A搬至搬至C，一次完成，记为，一次完成，记为move 1 from A to C (演示演示)ABC1第65页/共174页第六十五页，共174页。2、在、在A柱上有二只盘子，柱上有二只盘子，1为小盘，为小盘，2为大盘。为大盘。第（第（1）步将）步将1号盘从号盘从A移至移至B，这是为了，这是为了(wi le)让让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页第六十六页，共174页。3、在、在A柱上有柱上有3只盘子，从小到大分别只盘子，从小到大分别(fnbi)为为1号，号，2号，号，3号号第（第（1）步）步 将将1号盘和号盘和2号盘视为一个整体；先将二者作号盘视为一个整体；先将二者作为整体从为整体从A移至移至B，给，给3号盘创造能够一次移至号盘创造能够一次移至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页/共174页第六十七页，共174页。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (2, B, A, C)ABC213演示：移动演示：移动3 3个盘子个盘子(pn zi)(pn zi)的分解的分解第68页/共174页第六十八页，共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页第六十九页，共174页。4、从题目的约束条件看，大盘上可以随便摞小盘，、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将相反则不允许。在将1号和号和2号盘当整体号盘当整体(zhngt)从从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页第七十页，共174页。经过以上步骤，将经过以上步骤，将 1 号和号和 2 号盘作为整体号盘作为整体从从 A 移至移至 B，为，为 3 号盘从号盘从 A 移至移至 C 创造创造(chungzo)了条件。同样，了条件。同样，3号盘一旦到了号盘一旦到了 C，就要考虑如何实现将就要考虑如何实现将 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页第七十一页，共174页。5、看、看 move(2, A, C, B) 是说要将是说要将 2 只盘子从只盘子从 A 搬至搬至 B，但没有，但没有 C 是不行的，因为是不行的，因为(yn wi)第（第（1）.1步就要将步就要将 1 盘从盘从 A 移到移到 C，给，给 2 盘创造条件从盘创造条件从 A 移至移至 B，然后再把，然后再把 1 盘从盘从 C 移至移至 B。看到这里就。看到这里就能明白借助能明白借助 C 的含义了。因此，在构思搬移过程的含义了。因此，在构思搬移过程的参量时，要把的参量时，要把 3 个柱子都用上。个柱子都用上。第72页/共174页第七十二页，共174页。6、定义搬移、定义搬移(bn y)函数函数 move(n, A, B, C)，物理，物理意义是将意义是将 n 只盘子从只盘子从 A 经经 B 搬到搬到 C输出n:A to Cmove(n-1,A,C,B)move(n-1,B,A,C)move(n,A,B,C)考虑到前面考虑到前面(qin mian)已经已经研究过的研究过的(1)(2)(3)步，可步，可以将搬移过程用以将搬移过程用如下的与或结点如下的与或结点图表示。图表示。第73页/共174页第七十三页，共174页。这里用与或结点的含义是分解为这里用与或结点的含义是分解为(1)(2)(3)步。这步。这3步步是相关的，相互依存的，而且是有序的，从左至右执行。是相关的，相互依存的，而且是有序的，从左至右执行。move(n, A, B, C) 分解为分解为3步步(1)move(n-1, A, C, B)理解为将上面的理解为将上面的n-1只盘子只盘子(pn zi)作为作为一个整体从一个整体从A经经C移至移至B；(2)输出输出n：A to C，理解将，理解将n号盘从号盘从A移至移至C，是直接可解结，是直接可解结点；点；(3)Move(n-1, B, A, C)理解为将上面的理解为将上面的n-1只盘子只盘子(pn zi)作作为一个整体从为一个整体从B经经A移至移至C。第74页/共174页第七十四页，共174页。这里显然是一种递归定义，当着解这里显然是一种递归定义，当着解 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)；下面下面(xi mian)，我们还是以，我们还是以3只盘子为例画出递归的与只盘子为例画出递归的与或图。或图。第75页/共174页第七十五页，共174页。这个图很象一颗倒置着的树，结点这个图很象一颗倒置着的树，结点move(3, A, B, C)是树是树根，与结点是树的分枝，叶子根，与结点是树的分枝，叶子(y zi)都是直接可解结都是直接可解结点。点。输出1:A to C1:A to C输出3:A to Cmove(2,A,C,B)move(2,B,A,C)move(3,A,B,C)输出2:A to B2:A to B输出1:C to B1:C to B输出1:B to A1:B to A输出2:B to C2:B to C输出1:A to C1:A to Cmove(1,A,B,C) move(1,C,A,B) move(1,B,C,A) move(1,A,B,C)第76页/共174页第七十六页，共174页。 move(3,A,B,C) move(2,A,C,B) 输输出出 3: A to C move(2,B,A,C) move(2,A,C,B) 调调用用 move(1,A,B,C) move(2,B,A,C) 调调用用 move(1,B,C,A) 返返回回 返返回回 调调用用 调调用用 返返回回 move(1,A,B,C) 输输出出 2: A to B move(1,C,A,B) move(1,B,C,A) 输输出出 2: B to C move(1,A,B,C) 输输出出 1: A to C 输输出出 1: B to A 输输出出 1: C to B 输输出出 1: A to C 4 1 3 2 5 7 6 调调用用 调调用用 返返回回 返返回回 调调用用 move (1,C,A,B) move (1,A,B,C) 第77页/共174页第七十七页，共174页。 输出输出 3: A to C 调用调用 move(1,C,A,B) 输出：输出：1: C to B 输出：输出：2: A to B move(1,C,A,B) 调用调用 move(1,A,B,C) 输出输出 1: A to C move(1,A,B,C) move(2,A,C,B) 调用调用 move(2,A,C,B) 调用调用 move(2,B,A,C) 调用调用 move(1,A,B,C) 输出输出 1: A to C 输出：输出：2: B to C 调用调用 move(1,B,C,A) 输出输出 1: B to A move(1,B,C,A) move(2,B,A,C) move(1,A,B,C) move(3,A,B,C) 1 2 3 4 5 6 7 第78页/共174页第七十八页，共174页。/ */ * 程程 序：序：6_hanoi2002.cpp */ * 作作 者：者：wuwh */ * 编制时间：编制时间：2002年年10月月13日日 */ * 主要功能：用递归求解主要功能：用递归求解Hanoi问题问题 */ *#include / 预编译命令预编译命令int step=1;/ 整型全局变量整型全局变量,预置预置1,步数步数void move(int m, char p, char q, char r);/ 声明要用到的被调用函数声明要用到的被调用函数void main()/ 主函数主函数/ 主程序开始主程序开始(kish)int n;/ 整型变量整型变量,n为盘数为盘数,printf( 请输入盘数请输入盘数 n=“);/ 提示信息提示信息scanf(“/%d”),&n);/ 输入正整数输入正整数nprintf( 在在3根柱子上移根柱子上移%d只盘的步骤为只盘的步骤为:“,n); / 输出提示信息输出提示信息 move(n,a,b,c);/ 调用函数调用函数 move(n,a,b,c)/ 主函数结束主函数结束第79页/共174页第七十九页，共174页。/ 以下函数是被主程序调用的函数以下函数是被主程序调用的函数/ 函数名：函数名：move/ 输输 入：入：m，整型变量，表示盘子数目，整型变量，表示盘子数目/ p，q，r为字符型变量，表示柱子标号为字符型变量，表示柱子标号/ 返回值：无返回值：无void move(int m, char p, char q, char r)/ 自定义函数体开始自定义函数体开始if (m=1)/ 如果如果m为为1,则为直接可解结点则为直接可解结点(ji din),/ 直接可解结点直接可解结点(ji din),输出移盘信息输出移盘信息printf(%d move 1# from p to r”, step); step+;/ 步数加步数加1else/ 如果不为如果不为1,则要调用则要调用move(m-1)move(m-1,p,r,q);/ 递归调用递归调用move(m-1)/直接可解结点直接可解结点(ji din),输出移盘信息输出移盘信息 printf(%d move %d from p to r”, step,m); step+;/ 步数加步数加1move(m-1,q,p,r);/ 递归调用递归调用move(m-1)/自定义函数体结束自定义函数体结束第80页/共174页第八十页，共174页。1111,125;123nmnnnmmmnm nmmnCmnCCCCC习题：已知表示从 个元素中取 个的组合数，又知、试画出符合上述关系的与或结合图；、指出哪个是直接可解结点；、画出求解结点图；4、写出递归程序求解组合问题。第81页/共174页第八十一页，共174页。 mn| n=1 c(m,n)m=0|n=0 n=m n!=m 第82页/共174页第八十二页，共174页。/ */ * 程程 序：序：6_7.cpp * / * 编制时间编制时间(shjin)：2002年年10月月28日日 * / * 主要功能：计算组和数主要功能：计算组和数C(m,n) */ *#include / 预编译命令预编译命令Using namespace std;第83页/共174页第八十三页，共174页。/ 计算( j sun)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页/共174页第八十四页，共174页。int main()/ 主函数主函数(hnsh)开始开始/ 测试一些结果测试一些结果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；S SY Y5 54 46 6L LR R1 12 23 37 78 89 91#2#4#3#3#1#2#1#1#第91页/共174页第九十一页，共174页。表一表一第92页/共174页第九十二页，共174页。 为了将过河过程描述得更清楚，我们给出了表为了将过河过程描述得更清楚，我们给出了表1 1。表中。表中L1 L1 L2 L3 L4L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。表示左岸石柱上落在一起的青蛙的高度位置。L1 L1 在最在最上面，上面，L4 L4 在最下面的位置。引入这个信息就可比较容易地看出在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理对青蛙占位的约束条件。同理R1 R2 R3 R4R1 R2 R3 R4也是如此也是如此(rc)(rc)。对。对水中石柱水中石柱S S，也分成两个高度位置，也分成两个高度位置S1 S2S1 S2。对荷叶。对荷叶Y Y无须分层，因无须分层，因为它只允许一只青蛙落在其上。为它只允许一只青蛙落在其上。t=0t=0为初始时刻，青蛙从小到大为初始时刻，青蛙从小到大落在石柱落在石柱L L上。上。t=1t=1为第一步：为第一步：1#1#从从L L跳至荷叶跳至荷叶Y Y上；上；L L上只剩上只剩2# 2# 3# 4#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上。这一过上。这一过程是一分为二的过程。即将程是一分为二的过程。即将L L上的一队青蛙，分解为两个队，每上的一队青蛙，分解为两个队，每队各二只，且将上面的二只转移到了队各二只，且将上面的二只转移到了S S上。这时我们可以考虑形上。这时我们可以考虑形成两个系统，一个是成两个系统，一个是L L，Y Y，R R系统，一个是系统，一个是S S，Y Y，R R系统。前者系统。前者二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。从第五步到第九步可以看出的确是这么做的。第93页/共174页第九十三页，共174页。 2YRSL31第94页/共174页第九十四页，共174页。L-Y-S ,将 L上的一半青蛙(qngw)转移到 S 上L-Y-R,将 L上的青蛙(qngw)转移到 R 上S-Y-R,将 S 上的青蛙(qngw)转移到 R 上对于LYR系统，相当于Jump(0,1)对于SYR系统，相当于Jump(0,1)两个系统之和为2*Jump(0,1)，因此有：Jump(1,1)=2*Jump(0,1)=2*2=4 第95页/共174页第九十五页，共174页。现在再看现在再看S=2，y=1 Jump(2,1) 我们将河中的两个石柱称作我们将河中的两个石柱称作S1和和S2，荷，荷叶叫叶叫y，考虑先将，考虑先将L上的青蛙上的青蛙(qngw)的的一半借助于一半借助于S2和和y转移到转移到S1上，当然是上，当然是一半小号的青蛙一半小号的青蛙(qngw)在在S1上，大的上，大的留在留在L上。上。y yLR RS1S1S2S2第96页/共174页第九十六页，共174页。S=2, y=1: S=S1+S2 S1=S2=S-1 L Y R S2 S1 2 3 1 第97页/共174页第九十七页，共174页。1.L-S2-Y-S1 以S1为跳转的目的地，从L经S2Y到S1,相当于JAMP（1，1）=4, 即S1 上有4 只青蛙(qngw)，L上还保留4 只。2. 13. 2 Y4. 35. 46. 5 17. 6 28. L 7 S2 1 3 S19. 8 2 4第98页/共174页第九十八页，共174页。LRYS2876543S1214321第99页/共174页第九十九页，共174页。 Y R L S2 S1LS2YR S1S2YR第100页/共174页第一百页，共174页。这样这样 L S1 S2 y R 系统系统(xtng)分解为分解为 ： （L S2 y R 系统系统(xtng)） + （S1 S2 y R 系统系统(xtng)）= 2 * （L S2 y R 系统系统(xtng)）= 2 * Jump(1,1)用归纳法用归纳法Jump(S, y)=2*Jump(S-1, y)第101页/共174页第一百零一页，共174页。5. 将上述分析出来将上述分析出来(ch li)的规律写成递归形式的与或结点图为：的规律写成递归形式的与或结点图为：Jump(S,y)y+1S!=0S=0Jump(S-1,y)2*Jump(S-1,y)第102页/共174页第一百零二页，共174页。举例(j l)：S=3，y=4，算 Jump(3,4)A=Jump(2,4)2*B2*10=20Jump(3,4)2*A2*20=402*C2*5=10C=Jump(0,4)S=04+1 5B=Jump(1,4)3(3,4)2 (1)2 (4 1)40SJumpy第103页/共174页第一百零三页，共174页。/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 编制时间：编制时间：2002年年10月月20日日 */ * 主要功能：青蛙过河主要功能：青蛙过河 */ *#include /预编译命令预编译命令int Jump(int, int);/声明声明(shngmng)有被调用函数有被调用函数void main()/主函数主函数/主程序开始主程序开始int s=0,y=0,sum=0;/整型变量整型变量,s为河中石柱数为河中石柱数,y为荷叶数为荷叶数cout s;/输入正整数输入正整数scout y;/输入正整数输入正整数ysum = Jump ( s , y ) ;/Jump(s,y)为被调用函数为被调用函数cout Jump( s , /输出结果输出结果 y )= sum endl;/主程序结束主程序结束第104页/共174页第一百零四页，共174页。/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 编制时间：编制时间：2002年年10月月20日日 */ * 主要功能主要功能(gngnng)：青蛙过河：青蛙过河(递归递归) */ *第105页/共174页第一百零五页，共174页。#include /预编译命令预编译命令int Jump(int, int);/声明有被调用函数声明有被调用函数(hnsh)int main()/主函数主函数(hnsh) int s=0,y=0,sum=0; cout s;/输入正整数输入正整数s cout y;/输入正整
展开阅读全文