算法语言与数据结构第5章学习教案

1、会计学1算法语言算法语言(sun f y yn)与数据结构第与数据结构第5章章第一页，共174页。 第2页/共174页第二页，共174页。/ */ * 程 序：6_3.cpp（验证素数程序） */ * 作 者：wuwh */ * 编制时间：2002年10月20日 */ * 主要功能：可验证某数是否为素数 */ *#include / 预编译命令#include / 预编译命令int checkprime( int );/ 子函数声明int main()/ 主函数int a=0;/ 定义整型变量，初始化为0cout a;/ 键盘输入一个整数/ 用实参a调用子函数，该子函数的/ 返回值作为if语句

2、的分支条件if ( checkprime(a) ) / checkprime(a)为1cout a 是素数 endl;else/ checkprime(a)为0cout a 不是(b shi)素数 endl;/ 主函数结束第3页/共174页第三页，共174页。n/ 用实参 a 调用子函数(hnsh)，该子函数(hnsh)的n/ 返回值作为 if 语句的分支条件nif ( checkprime( a ) ) n/ checkprime( a ) 为 1ncout a 是素数 endl;nnelsen / checkprime( a ) 为 0n cout a 不是素数 endl;nn/ 主函数(

3、hnsh)结束第第5章章 函数函数(hnsh)第4页/共174页第四页，共174页。第第5章章 函数函数(hnsh)第5页/共174页第五页，共174页。bool checkprime(int b)/ 子函数，子函数，b为形式参数为形式参数int k=0; / 定义整型变量，并初始化定义整型变量，并初始化for (k=2; k=sqrt(double)b); k+)/ 循环循环(xnhun)if (b%k = 0)/ 如果如果b能够被能够被k整除，则整除，则返回返回0/ 可理解为可理解为“抢先抢先”返回返回0，有了，有了 return 0，/ 后面的后面的 return 1 不起作用了不起作用

4、了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

5、( b % k = 0 ) return 0; return 1; / b不能被不能被k整除整除(zhngch)，则返回，则返回1 / 说明说明 b 是质数是质数第第5章章 函数函数(hnsh)第8页/共174页第八页，共174页。 讲这一程序的目的：讲这一程序的目的：如何定义一个函数如何定义一个函数主函数怎样调用子函数主函数怎样调用子函数实在参数和形式参数实在参数和形式参数返回值是什么返回值是什么(shn me)意思意思第9页/共174页第九页，共174页。第第5章章 函数函数(hnsh)第10页/共174页第十页，共174页。第第5章章 函数函数(hnsh)第11页/共174页第十一页，共

6、174页。第12页/共174页第十二页，共174页。第13页/共174页第十三页，共174页。第14页/共174页第十四页，共174页。第15页/共174页第十五页，共174页。第16页/共174页第十六页，共174页。输出(shch) 输出(shch) 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

7、) return 0; return 1; cout a 是素数(s sh) endl; elsecout a 不是素数(s sh) endl; 第18页/共174页第十八页，共174页。第19页/共174页第十九页，共174页。第20页/共174页第二十页，共174页。第21页/共174页第二十一页，共174页。 第22页/共174页第二十二页，共174页。第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页。4441 , 2, 61SOP( ,

8、 )power( , )mim li l第25页/共174页第二十五页，共174页。第26页/共174页第二十六页，共174页。int power(int p, int q);/ 声明函数power第27页/共174页第二十七页，共174页。第28页/共174页第二十八页，共174页。for(i=1; i=m; i+ )sum=sum+power( i, l );/ 累加return sum; / 返回值第29页/共174页第二十九页，共174页。第30页/共174页第三十页，共174页。第31页/共174页第三十一页，共174页。例例:int power(int p, int n)power

9、 为函数为函数(hnsh)名，要以英文字母开头。名，要以英文字母开头。int 是函数是函数(hnsh)值的数据类型，这里是值的数据类型，这里是int（整（整型）。型）。(int p, int n) 括号中的括号中的 p, n为函数为函数(hnsh)的形式参数，的形式参数，形式参数也要定义其数据类型。形式参数也要定义其数据类型。第32页/共174页第三十二页，共174页。函数定义的一般(ybn)格式： ()第33页/共174页第三十三页，共174页。形式参数与实在(shzi)参数1、形式参数是在定义函数时放在函数名后括号中的参数。在未、形式参数是在定义函数时放在函数名后括号中的参数。在未进行进行

10、(jnxng)函数调用时，并不对形式参数分配内存单元。在函数调用时，并不对形式参数分配内存单元。在发生函数调用时，立刻给形式参数分配内存单元。调用结束发生函数调用时，立刻给形式参数分配内存单元。调用结束后，释放掉行参所占的内存单元。后，释放掉行参所占的内存单元。2、因此，形参变量属于局部变量，其作用域在它所在的函数体、因此，形参变量属于局部变量，其作用域在它所在的函数体内。内。3、在定义函数的时候，必须指定形参变量的类型，如下所示、在定义函数的时候，必须指定形参变量的类型，如下所示int power(int p, int n) / 函数函数(hnsh)体体 c第34页/共174页第三十四页，共

11、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函数去调用 power 函数。其中 i, l 为实在(shzi)参数，而 int power( p, q

12、 )中的 p, q 为形式参数。比如，执行 SOP( 6, 4 )时，l=4, m=6,当 i=1 时，sum = sum + power( 1, 4 )这里 1，4 为实在(shzi)参数，调用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 + 8

13、1 = 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):

14、 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页。递递 推推第38页/共174页第三十八页，共174页。第39页/共174页第三十九

15、页，共174页。第40页/共174页第四十页，共174页。写成一般式fish i = ( fish i - 1 1 ) * 4 / 5i = 2, 3, ,5这个公式可用于知 A 看到的鱼数去推算(tu sun) B 看到的，再推算(tu sun) 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)被整除后余，即

16、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 人合伙捕到的最少鱼数，可以从小往大枚举(mi j)，可以先让 E 所看到的鱼数最少为 6 条，即 fish 5 初始化为 6 来试，之后每次增加 5 再试，直至递推到 fish 1 得整数且除以 5

17、 之后的余数为 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) 是说明部分：包含定义数组是说明部

18、分：包含定义数组 fish6，并初始化为，并初始化为 1 和定和定义循环控制变量义循环控制变量 i，并初始化为，并初始化为 0。(2) 是是 do.while 直到型循环，其循环体又含两块：直到型循环，其循环体又含两块：(2).1 是枚举过程是枚举过程(guchng)中的中的 fish5 的初值设置，的初值设置，一开始一开始 fish5=1+5; 以后每次增以后每次增 5。(2).2 是一个是一个 for 循环，循环，i 的初值为的初值为 4，终值为，终值为 1，步长，步长为为 -1，该循环的循环体是一个分支语句，该循环的循环体是一个分支语句， 如果如果 fishi+1不能被不能被 4 整除，

19、则跳出整除，则跳出 for 循环（使用循环（使用 break 语句）语句）; 否则，从否则，从 fishi+1 算出算出 fishi。第45页/共174页第四十五页，共174页。当由 break 语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令fish 5 加 5 后再试，即重新进入直到型循环 do while 的循环体。当着正常退出 for 循环时，一定是控制变量 i 从初值 4，一步一步执行到终值 1，每一步的鱼数均为整数，最后 i = 0，表示计算(j sun)完毕，且也达到了退出直到型循环的条件。(3) 输出计算(j sun)结果第46页/共174页第四十六页，

20、共174页。/*/* 程 序 名：5_3.c（五人合伙捕鱼） */* 作 者：wuwh */* 编制时间：2002年10月2日 */* 主要功能：递推算法(sun f)的实现 */*#include / 预编译命令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人看到的鱼数 w

21、hile( i=1 ); / 当 i=1 继续做do循环 / 输出计算结果 for (i=1; i1 时，时，A 的取值即的取值即 C 的值，的值，而而 C 的值即的值即 E 的值，为了的值，为了(wi le)求得求得 E 的值，需的值，需要先求出要先求出 D 的值。的值。D 值值 fact( n-1 ) 乘以乘以 n 即为即为 E 的的值。值。A fact(n)Bfact(1)=1Cn1n=1Dfact(n-1)En*fact(n-1)第55页/共174页第五十五页，共174页。与结点可能有多个与结点可能有多个(du )相关联的点，这时可描述为下相关联的点，这时可描述为下图图A 结点的值最终

22、为结点的值最终为 D 的值，但为了求的值，但为了求 D 需先求需先求 B 和和 C。从图上看。从图上看, 先求左边的点才能求最右边的点的值，先求左边的点才能求最右边的点的值，我们我们(w men)约定最右边约定最右边 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

23、)Cfact(1)D2*fact(1)AE21第57页/共174页第五十七页，共174页。下面下面(xi mian)画出了调用和返回的递归示意图画出了调用和返回的递归示意图 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 ) 先求

24、先求 fact( 1 )。就象剥一颗圆白菜，从外向里，一。就象剥一颗圆白菜，从外向里，一层层剥下来层层剥下来(xi li)，到了菜心，遇到，到了菜心，遇到 1 的阶乘，其的阶乘，其值为值为1，到达了递归的边界。然后再用，到达了递归的边界。然后再用 fact( n )=n*fact( n-1 ) 这个普遍公式，从里向外倒推这个普遍公式，从里向外倒推回去得到回去得到 fact( n ) 的值。的值。为了把这个问题说得再透彻一点。我们画了如为了把这个问题说得再透彻一点。我们画了如下的流程图：下的流程图：第59页/共174页第五十九页，共174页。 31 fact(3) 真真 假假 调调用用 fact

25、(2) 计计算算 3*fact(2) fact(2) fact(1) 21 真真 假假 调调用用 fact(1) 计计算算 2*fact(1) 11 真真 假假 fact(1) 1 返返回回 返返回回 第60页/共174页第六十页，共174页。为了形象为了形象(xngxing)地描述递归过程，将上图改画成下图地描述递归过程，将上图改画成下图 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 返返回回 第6

26、1页/共174页第六十一页，共174页。在这个图中在这个图中“内层内层”与与“外层外层”有着相同的结构。它们之间有着相同的结构。它们之间“你你中有我，我中有你中有我，我中有你”，呈现相互依存的关系。，呈现相互依存的关系。为了进一步讲清递归的概念，将递归与递推做一比较。仍为了进一步讲清递归的概念，将递归与递推做一比较。仍以求阶乘以求阶乘(ji chn)为例。为例。递推是从已知的初始条件出发，逐次去求所需要的阶乘递推是从已知的初始条件出发，逐次去求所需要的阶乘(ji chn)值。值。如求如求 3！初始条件初始条件 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2

27、fact( 3 ) = 3 * fact( 2 ) = 6第62页/共174页第六十二页，共174页。这相当于从菜心这相当于从菜心“推到推到”外层。而递归算法的出发外层。而递归算法的出发点不放在初始条件上，而放在求解的目标上，从所求点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归的的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。就本例而言，读者会认为递归边界（即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。但许多实际问题算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的递推关系，这时递归

28、不可能或不容易找到显而易见的递推关系，这时递归算法就表现出了明显的优越性。下面算法就表现出了明显的优越性。下面(xi mian)我们将我们将会看到，递归算法比较符合人的思维方式，逻辑性强，会看到，递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于可将问题描述得简单扼要，具有良好的可读性，易于理解，许多看来相当复杂，或难以下手的问题，如果理解，许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处理。下面能够使用递归算法就会使问题变得易于处理。下面(xi mian)举一个尽人皆知的例子哈诺（举一个尽人皆知的例子哈诺（Hanoi）塔问）塔问

29、题。题。第63页/共174页第六十三页，共174页。故事：故事：相传在古代印度的相传在古代印度的 Bramah 庙中，有位僧人整天把庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把三根柱子上的金盘倒来倒去，原来他是想把64个一个一个比一个小的金盘从一根柱子上移到另一根柱子上个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只简单，真的动手移盘就会发现，如以每秒移动一只盘子盘子

30、(pn zi)的话，按照上述规则将的话，按照上述规则将64只盘子只盘子(pn zi)从一个柱子移至另一个柱子上，所需时间约为从一个柱子移至另一个柱子上，所需时间约为5800亿年。亿年。 第64页/共174页第六十四页，共174页。怎样编写这种程序？思路上还是先从最简单的情况怎样编写这种程序？思路上还是先从最简单的情况(qngkung)分析起，搬一搬看，慢慢理出思路。分析起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盘子柱上只有一只盘子(pn zi)，假定盘号为，假定盘号为1，这时只需将该盘从这时只需将该盘从A搬至搬至C，一次完成，记为，一次完成，记为move 1 from A to C

31、(演示演示)ABC1第65页/共174页第六十五页，共174页。2、在、在A柱上有二只盘子柱上有二只盘子(pn zi)，1为小盘，为小盘，2为大盘。为大盘。第（第（1）步将）步将1号盘从号盘从A移至移至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页第六十六页，共174页。3、在、在A柱上有柱上有3只盘子，

32、从小到大分别为只盘子，从小到大分别为1号，号，2号，号，3号号第（第（1）步）步 将将1号盘和号盘和2号盘视为一个整体；先将二者作为号盘视为一个整体；先将二者作为整体从整体从A移至移至B，给，给3号盘创造能够号盘创造能够(nnggu)一次移至一次移至C的机会。这一步记为的机会。这一步记为 move( 2, A, C, B) 意思是将上面的意思是将上面的2只盘子作为整体从只盘子作为整体从A借助借助C移至移至B。第（第（2）步）步 将将3号盘从号盘从A移至移至C，一次到位。记为，一次到位。记为 move 3 from A to C第（第（3）步）步 处于处于B上的作为一个整体的上的作为一个整体的2

33、只盘子，再移至只盘子，再移至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演示演示(ynsh)(ynsh)：移动：移动3 3个盘子个盘子的分解的分解第68页/共174页第六十八页，共174页。move (3, A, B, C)mov

34、e (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、从题目的约束条件看，大盘上可以随便摞小盘，、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许相反则不允许(ynx)。在将。在将1号和号和2号盘当整体号盘当整体从从A移至移至B的过程中的过程中 move(2, A, C, B) 实际上是

35、分实际上是分解为以下三步解为以下三步第（第（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页。经过以上步骤经过以上步骤(bzhu)，将，将 1 号和号和 2 号号盘作为整体从盘作为整体从 A 移至移至 B，为，为 3 号盘从号盘从 A 移至移至 C 创造了条件。同样，创造了条件。同样，3号盘一旦到了号盘一旦到了 C，就，就要考虑如何实现将要考虑如何实现将 1 号和号和 2 号盘当整体从号盘当整体从 B 移至移至 C 的过程了。

36、实际上的过程了。实际上 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 是不行的，因为第（是不行的，因为第（1）.1步就要将步就要将 1 盘从盘从 A 移到移到 C，给，给 2 盘创造条件从盘创造条件从 A 移至移至 B，然后再

37、把然后再把 1 盘从盘从 C 移至移至 B。看到这里就能明白借。看到这里就能明白借助助 C 的含义的含义(hny)了。因此，在构思搬移过程的了。因此，在构思搬移过程的参量时，要把参量时，要把 3 个柱子都用上。个柱子都用上。第72页/共174页第七十二页，共174页。6、定义、定义(dngy)搬移函数搬移函数 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)考虑到前面已经考虑到前面已经研究过的研究过的(1)(2)(3)步，可以将

38、搬移步，可以将搬移过程用如下的与过程用如下的与或结点或结点(ji din)图表示。图表示。第73页/共174页第七十三页，共174页。这里用与或结点的含义是分解为这里用与或结点的含义是分解为(1)(2)(3)步。这步。这3步是步是相关的，相互依存的，而且是有序的，从左至右执行。相关的，相互依存的，而且是有序的，从左至右执行。move(n, A, B, C) 分解为分解为3步步(1)move(n-1, A, C, B)理解为将上面理解为将上面(shng min)的的n-1只盘子作只盘子作为一个整体从为一个整体从A经经C移至移至B；(2)输出输出n：A to C，理解将，理解将n号盘从号盘从A移至

39、移至C，是直接可解结点；，是直接可解结点；(3)Move(n-1, B, A, C)理解为将上面理解为将上面(shng min)的的n-1只盘子作只盘子作为一个整体从为一个整体从B经经A移至移至C。第74页/共174页第七十四页，共174页。这里显然是一种递归定义，当着解这里显然是一种递归定义，当着解 move(n-1, A, C, B)时又可想到，将其分解为时又可想到，将其分解为 3 步：步：第第1步：将上面的步：将上面的n-2只盘子作为一个只盘子作为一个(y )整体从整体从A经经B到到C，move(n-2, A, B, C)；第第2步：第步：第n-1号盘子从号盘子从A直接移至直接移至B，即

40、，即n-1:A to B；第第3步：再将上面的步：再将上面的n-2只盘子作为一个只盘子作为一个(y )整体从整体从C经经A移至移至B，move(n-2, C, A, B)；下面，我们还是以下面，我们还是以3只盘子为例画出递归的与或图。只盘子为例画出递归的与或图。第75页/共174页第七十五页，共174页。这个图很象一颗倒置着的树，结点这个图很象一颗倒置着的树，结点move(3, A, B, C)是树是树根，与结点是树的分枝根，与结点是树的分枝(fn zh)，叶子都是直接可解，叶子都是直接可解结点。结点。输出1:A to C1:A to C输出3:A to Cmove(2,A,C,B)move(

41、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) 调调用用 mo

42、ve(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(

43、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

44、 4 5 6 7 第78页/共174页第七十八页，共174页。/ */ * 程程 序：序：6_hanoi2002.cpp */ * 作作 者：者：wuwh */ * 编制编制(binzh)时间：时间：2002年年10月月13日日 */ * 主要功能：用递归求解主要功能：用递归求解Hanoi问题问题 */ *#include / 预编译命令预编译命令int step=1;/ 整型全局变量整型全局变量,预置预置1,步数步数void move(int m, char p, char q, char r);/ 声明要用到的被调用函数声明要用到的被调用函数void main()/ 主函数主函数/ 主程序

45、开始主程序开始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，整型变量，表示盘子数目，整型变量

46、，表示盘子数目/ 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/ 如果不为如果不为(b wi)1,则要调用则要调用move(m-1)move(m-1,p,r,q);/ 递归调用递归调用move(m-1

47、)/直接可解结点直接可解结点,输出移盘信息输出移盘信息 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页。第82页/共174

48、页第八十二页，共174页。/ */ * 程程 序：序：6_7.cpp * / * 编制时间：编制时间：2002年年10月月28日日 * / * 主要功能：计算主要功能：计算(j sun)组和数组和数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)=mret

49、urn 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()/ 主函数开始主函数开始(kish)/ 测试一些结果测试一些结果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#

50、 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页。 为了将过河过程描述为了将过河过程描述(mio sh)(mio sh)得更清楚，我们给出了表得更清楚，我们给出了表1 1。表中表中L1 L2 L3 L4L1 L2 L3 L4表示左岸石

51、柱上落在一起的青蛙的高度位置。表示左岸石柱上落在一起的青蛙的高度位置。L1 L1 在最上面，在最上面，L4 L4 在最下面的位置。引入这个信息就可比较容在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理易地看出对青蛙占位的约束条件。同理R1 R2 R3 R4R1 R2 R3 R4也是如此。也是如此。对水中石柱对水中石柱S S，也分成两个高度位置，也分成两个高度位置S1 S2S1 S2。对荷叶。对荷叶Y Y无须分层，无须分层，因为它只允许一只青蛙落在其上。因为它只允许一只青蛙落在其上。t=0t=0为初始时刻，青蛙从小到为初始时刻，青蛙从小到大落在石柱大落在石柱L L上。上。

52、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只通过荷叶只通过荷

53、叶y y转移到了转移到了S S上。这一过上。这一过程是一分为二的过程。即将程是一分为二的过程。即将L L上的一队青蛙，分解为两个队，每上的一队青蛙，分解为两个队，每队各二只，且将上面的二只转移到了队各二只，且将上面的二只转移到了S S上。这时我们可以考虑形上。这时我们可以考虑形成两个系统，一个是成两个系统，一个是L L，Y Y，R R系统，一个是系统，一个是S S，Y Y，R R系统。前者系统。前者二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。从第五步到第九步可以看出的确是这么做的。第93

54、页/共174页第九十三页，共174页。2YRSL31第94页/共174页第九十四页，共174页。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上的青蛙的一半借助于上的青蛙的一半借助于S2和和y转转移移(zhuny)到到S1上，当然是一半小号的青上，当然是一半小号的青蛙在蛙在S1上，大的留在上，大的留在L上。上。y yLR RS1S

55、1S2S2第96页/共174页第九十六页，共174页。 1第97页/共174页第九十七页，共174页。S19. 8 2 4第98页/共174页第九十八页，共174页。LRYS2876543S1214321第99页/共174页第九十九页，共174页。LS2YR 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)

56、=2*Jump(S-1, y)第101页/共174页第一百零一页，共174页。5. 将上述分析出来的规律写成递归形式将上述分析出来的规律写成递归形式(xngsh)的与或结点图为：的与或结点图为：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

57、页/共174页第一百零三页，共174页。/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 编制时间：编制时间：2002年年10月月20日日 */ * 主要功能：青蛙过河主要功能：青蛙过河 */ *#include /预编译预编译(biny)命令命令int Jump(int, int);/声明有被调用函数声明有被调用函数void main()/主函数主函数/主程序开始主程序开始int s=0,y=0,sum=0;/整型变量整型变量,s为河中石柱数为河中石柱数,y为荷叶数为荷叶数cout s;/输入正整数输入正整数scout y;/输入正整数输入正整数ysum

58、 = Jump ( s , y ) ;/Jump(s,y)为被调用函数为被调用函数cout Jump( s , /输出结果输出结果 y )= sum endl;/主程序结束主程序结束第104页/共174页第一百零四页，共174页。/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 编制时间：编制时间：2002年年10月月20日日 */ * 主要主要(zhyo)功能：青蛙过河功能：青蛙过河(递归递归) */ *第105页/共174页第一百零五页，共174页。#include /预编译命令预编译命令int Jump(int, int);/声明声明(shngmng

59、)有被调用函数有被调用函数int main()/主函数主函数 int s=0,y=0,sum=0; cout s;/输入正整数输入正整数s cout y;/输入正整数输入正整数y sum = Jump ( s , y ) ;/Jump(s,y)为被调用函数为被调用函数 cout Jump( s , /输出结果输出结果 y )= sum =rl=rA sort(l,r)数据在al,.,ar中数据在al,.,ar中B什么也不做什么也不做ClrD分区处理分区处理Fsort(m+1,r)Esort(l,m-1)第111页/共174页第一百一十一页，共174页。第112页/共174页第一百一十二页，共1

60、74页。分区处理：分区处理：1、让、让 k=a z 2、将、将 k 放在放在 a m 3、使、使 az, az+1 , , a m-1 = a m 4、使、使 a m = y，则什么也不做。这是直，则什么也不做。这是直接可解结点接可解结点(ji din)。C 结点结点(ji din)是在是在 z y 情况下情况下 A 结点结点(ji din)的解。的解。C 是一个与结点是一个与结点(ji din)。要对。要对 C 求解需分解为三步。求解需分解为三步。依次为：依次为：第113页/共174页第一百一十三页，共174页。1、先解、先解 D 结点，结点，D 结点是一个直接可解结点，功能是进行结点是一个直接可解结点，功能是进