算法语言与数据结构课件

1、第5章 函数数 / */ * 程 序：6_3.cpp（验证素数程序） */ * 作 者：wuwh */ * 编制时间：2002年10月20日 */ * 主要功能：可验证某数是否为素数 */ *#include / 预编译命令#include / 预编译命令int checkprime( int );/ 子函数声明int main()/ 主函数int a=0;/ 定义整型变量，初始化为0cout a; / 键盘输入一个整数/ 用实参a调用子函数，该子函数的/ 返回值作为if语句的分支条件if ( checkprime(a) ) / checkprime(a)为1cout a 是素数 endl;e

2、lse/ checkprime(a)为0cout a 不是素数 endl;/ 主函数结束第第5章章 函数函数第第5章章 函数函数第第5章章 函数函数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;

3、return 1;/ b不能被不能被k整除，则返回整除，则返回1第第5章章 函数函数第第5章章 函数函数 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章章 函数函数 讲这一程序的目的：讲这一程序的目的：如何定义一个函数如何定义一个函数主函数怎样调用子函数主函数怎样调用子函数实在参数和形式参数实在参数和

4、形式参数返回值是什么意思返回值是什么意思第第5章章 函数函数第第5章章 函数函数 1nkxx4444441 2 3 4 5 6 p o w e r ( , )li li i=1,2,n l = k 4441 , 2, 61SOP( , )power( , )mim li l 例例: int power(int p, int n)power 为函数名，要以英文字母开头。为函数名，要以英文字母开头。int 是函数值的数据类型，这里是是函数值的数据类型，这里是int（整型）。（整型）。(int p, int n) 括号中的括号中的 p, n为函数的形式参数，形式为函数的形式参数，形式参数也要定义其数

5、据类型。参数也要定义其数据类型。 ()1、形式参数形式参数是在定义函数时放在函数名后括号中的参数。在是在定义函数时放在函数名后括号中的参数。在未进行函数调用时，并不对形式参数分配内存单元。在发未进行函数调用时，并不对形式参数分配内存单元。在发生函数调用时，立刻给形式参数分配内存单元。调用结束生函数调用时，立刻给形式参数分配内存单元。调用结束后，释放掉行参所占的内存单元。后，释放掉行参所占的内存单元。2、因此，形参变量属于局部变量，其作用域在它所在的函数、因此，形参变量属于局部变量，其作用域在它所在的函数体内。体内。3、在定义函数的时候，必须指定形参变量的类型，如下所示、在定义函数的时候，必须指

6、定形参变量的类型，如下所示int power(int p, int n) / 函数体函数体 c 执行执行 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 = s

7、um + 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 调用 返回 执行执行 powe

8、r(5, 4): product = 5*5*5*5 return(625) = 625 调用 返回 执行执行 power(6, 4): product = 6*6*6*6 return(1296) = 1296 调用 返回 SOP(n,k) 调用调用 递递 推推 定义数组 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 循环 fi

9、shi = fishi+1*5/4+1; 该图可分为三部分该图可分为三部分(1) 是说明部分：包含定义数组是说明部分：包含定义数组 fish6，并初始化为，并初始化为 1 和和定义循环控制变量定义循环控制变量 i，并初始化为，并初始化为 0。(2) 是是 do.while 直到型循环，其循环体又含两块：直到型循环，其循环体又含两块：(2).1 是枚举过程中的是枚举过程中的 fish5 的初值设置，一开始的初值设置，一开始 fish5=1+5; 以后每次增以后每次增 5。(2).2 是一个是一个 for 循环，循环，i 的初值为的初值为 4，终值为，终值为 1，步长，步长为为 -1，该循环的循环

10、体是一个分支语句，该循环的循环体是一个分支语句， 如果如果 fishi+1不能被不能被 4 整除，则跳出整除，则跳出 for 循环（使用循环（使用 break 语句）语句）; 否则，从否则，从 fishi+1 算出算出 fishi。递归算法在可计算性理论中占有重要地位，它是递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。学者要建立起递归概念不十分容易。我们先从一个最简单的例子导入。我们先从一

11、个最简单的例子导入。递归及其实现递归及其实现用递归算法求用递归算法求n!定义：函数定义：函数 fact( n ) = n!fact( n-1 ) = ( n-1 )!则有则有 fact( n ) = n fact( n-1 )已知已知 fact( 1 ) = 1为了表述得直观清晰，我们定义两个结点：或结点和为了表述得直观清晰，我们定义两个结点：或结点和与结点。与结点。图示的直观性与思维助力。图示的直观性与思维助力。1、或结点、或结点,BZ trueCZfalseA（真）（假） A 条条件件Z 条条件件!Z B C A为为“或结点或结点”，A依不同条件会有两种不同的取值依不同条件会有两种不同的取

12、值, B 或或C。结点用。结点用 表示。表示。 如果有多于如果有多于2 种取值，可用下图：种取值，可用下图： Z1 Z2 Zn B C G A 条件为条件为Z1,Z2,Zn,Z1,Z2,Zn,取值为取值为 B B 或或C,C,或或G G2、与结点、与结点与结点要涂实心，相与结点要涂实心，相关联的关联的B与与C之间要用之间要用弧线连起来。弧线连起来。A为与结点，为与结点，A的最终取值为的最终取值为C结点的值，但为结点的值，但为了求得了求得C的值，得先求出的值，得先求出B结点的值，结点的值，C是是B的的函数。函数。ABC仍以求仍以求 n! 为例画出如下与或图为例画出如下与或图A 为或结点；为或结点

13、；B 为直接可解结点，值为为直接可解结点，值为 1；C 为与结点，当为与结点，当 n1 时，时，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)与结点可能有多个相关联的点，这时可描述为下图与结点可能有多个相关联的点，这时可描述为下图A 结点的值最终为结点的值最终为 D 的值，但为了求的值，但为了求 D 需先求需先求 B 和和 C

14、。从图上看。从图上看, 先求左边的点才能求最右边的点的先求左边的点才能求最右边的点的值，我们约定最右边值，我们约定最右边 D 点的值就是点的值就是 A 结点的值。结点的值。ABDC下面我们以下面我们以3！为例来画与或结点图，目的是体！为例来画与或结点图，目的是体会递归的含义。会递归的含义。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下面画出了调用和返回的递归示意图下面画出了调用和返回的递归示意图 Bfact(2)fact(2)=2*f

15、act(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调用调用调用调用从图可以想象：从图可以想象：欲求欲求 fact( 3 )，先要求，先要求 fact( 2 )；要求；要求 fact( 2 ) 先先求求 fact( 1 )。就象剥一颗圆白菜，从外向里，一层层。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到剥下来，到了菜心，遇到 1 的阶乘，其值为的阶乘，其值为1，到达，到达了递归的边界。然后再用了递归的边界。然后再用 fact( n )=n

16、*fact( n-1 ) 这个这个普遍公式，从里向外倒推回去得到普遍公式，从里向外倒推回去得到 fact( n ) 的值。的值。为了把这个问题说得再透彻一点。我们画了如下为了把这个问题说得再透彻一点。我们画了如下的流程图：的流程图： 31 fact(3) 真真 假假 调调用用 fact(2) 计计算算 3*fact(2) fact(2) fact(1) 21 真真 假假 调调用用 fact(1) 计计算算 2*fact(1) 11 真真 假假 fact(1) 1 返返回回 返返回回 为了形象地描述递归过程，将上图改画成下图为了形象地描述递归过程，将上图改画成下图 fact(3) 真真 假假 3

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

18、，逐次去求所需要的阶乘值。阶乘值。如求如求 3！初始条件初始条件 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2fact( 3 ) = 3 * fact( 2 ) = 6这相当于从菜心这相当于从菜心“推到推到”外层。而递归算法的出外层。而递归算法的出发点不放在初始条件上，而放在求解的目标上，从发点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。就本例而言，读者会递归的边界（即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。但许认为

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

20、子哈诺（易于处理。下面举一个尽人皆知的例子哈诺（Hanoi）塔问题。塔问题。故事：故事：相传在古代印度的相传在古代印度的 Bramah 庙中，有位僧人整天把庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把三根柱子上的金盘倒来倒去，原来他是想把64个一个一个比一个小的金盘从一根柱子上移到另一根柱子上个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只简单，真的动手移盘就会发现，

21、如以每秒移动一只盘子的话，按照上述规则将盘子的话，按照上述规则将64只盘子从一个柱子移只盘子从一个柱子移至另一个柱子上，所需时间约为至另一个柱子上，所需时间约为5800亿年。亿年。 怎样编写这种程序？思路上还是先从最简单的情况分怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。析起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盘子，假定盘号为柱上只有一只盘子，假定盘号为1，这时只，这时只需将该盘从需将该盘从A搬至搬至C，一次完成，记为，一次完成，记为move 1 from A to C (演示演示)ABC12、在、在A柱上有二只盘子，柱上有二只盘子，1为小盘，为小

22、盘，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;3、在、在A柱上有柱上有3只盘子，从小到大分别为只盘子，从小到大分别为1号，号，2号，号，3号号第（第（1）步）步 将将1号盘和号盘和2号盘视为一个整体；先将二者作号盘视为一个整体；先将二者作为整体从为整体从A移

23、至移至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。所谓借助是什么意思，等这件事

24、做完了不言自明。所谓借助是什么意思，等这件事做完了不言自明。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (2, B, A, C)ABC213演示：移动演示：移动3 3个个盘子盘子的分解的分解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)A

25、BC2134、从题目的约束条件看，大盘上可以随便摞小、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将盘，相反则不允许。在将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;经过以上步骤，将经过以上步骤，将 1 号和号和 2 号盘作为整体号盘作为整体从从 A 移至移至 B，为，为 3 号盘从号盘从 A 移至

26、移至 C 创造了条创造了条件。同样，件。同样，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;5、看、看 move(2, A, C, B) 是说要将是说要将 2 只盘子从只盘子从 A 搬至搬至 B，但没有，但没有 C 是不行的，

27、因为第（是不行的，因为第（1）.1步就要将步就要将 1 盘从盘从 A 移到移到 C，给，给 2 盘创造条件盘创造条件从从 A 移至移至 B，然后再把，然后再把 1 盘从盘从 C 移至移至 B。看。看到这里就能明白借助到这里就能明白借助 C 的含义了。因此，在的含义了。因此，在构思搬移过程的参量时，要把构思搬移过程的参量时，要把 3 个柱子都用上。个柱子都用上。6、定义搬移函数、定义搬移函数 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

28、,B,C)考虑到前面已考虑到前面已经研究过的经研究过的(1)(2)(3)步，可步，可以将搬移过程以将搬移过程用如下的与或用如下的与或结点图表示。结点图表示。这里用与或结点的含义是分解为这里用与或结点的含义是分解为(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移

29、至移至C，是直接可，是直接可解结点；解结点；(3)Move(n-1, B, A, C)理解为将上面的理解为将上面的n-1只盘子作为一只盘子作为一个整体从个整体从B经经A移至移至C。这里显然是一种递归定义，当着解这里显然是一种递归定义，当着解 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只盘

30、子作为一个整体从只盘子作为一个整体从C经经A移至移至B，move(n-2, C, A, B)；下面，我们还是以下面，我们还是以3只盘子为例画出递归的与或图。只盘子为例画出递归的与或图。这个图很象一颗倒置着的树，结点这个图很象一颗倒置着的树，结点move(3, A, B, C)是树是树根，与结点是树的分枝，叶子都是直接可解结点。根，与结点是树的分枝，叶子都是直接可解结点。输出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

31、: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) 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

32、,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) 输出输出 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

33、,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 / */ * 程程 序：序：6_hanoi2002.cpp */ * 作作 者：者：wuwh */ * 编制时间：编制时间：2002年年10月月13日日 */ * 主要功能：用递归求解主要功能：用递归求解Ha

34、noi问题问题 */ *#include / 预编译命令预编译命令int step=1;/ 整型全局变量整型全局变量,预置预置1,步数步数void move(int m, char p, char q, char r); / 声明要用到的被调用函数声明要用到的被调用函数void main()/ 主函数主函数/ 主程序开始主程序开始int n;/ 整型变量整型变量,n为盘数为盘数,printf( 请输入盘数请输入盘数 n=“);/ 提示信息提示信息scanf(“/%d”),&n);/ 输入正整数输入正整数nprintf( 在在3根柱子上移根柱子上移%d只盘的步骤为只盘的步骤为:“,n);

35、 / 输出提示信息输出提示信息 move(n,a,b,c);/ 调用函数调用函数 move(n,a,b,c)/ 主函数结束主函数结束/ 以下函数是被主程序调用的函数以下函数是被主程序调用的函数/ 函数名：函数名：move/ 输输 入：入：m，整型变量，表示盘子数目，整型变量，表示盘子数目/ p，q，r为字符型变量，表示柱子标号为字符型变量，表示柱子标号/ 返回值：无返回值：无void move(int m, char p, char q, char r)/ 自定义函数体开始自定义函数体开始if (m=1)/ 如果如果m为为1,则为直接可解结点则为直接可解结点,/ 直接可解结点直接可解结点,输出

36、移盘信息输出移盘信息printf(%d move 1# from p to r”, step); step+;/ 步数加步数加1else/ 如果不为如果不为1,则要调用则要调用move(m-1)move(m-1,p,r,q);/ 递归调用递归调用move(m-1)/直接可解结点直接可解结点,输出移盘信息输出移盘信息 printf(%d move %d from p to r”, step,m); step+;/ 步数加步数加1move(m-1,q,p,r); / 递归调用递归调用move(m-1)/自定义函数体结束自定义函数体结束1111,125;123nmnnnmmmnm nmmnCmnCC

37、CCC习题：已知表示从 个元素中取 个的组合数，又知、试画出符合上述关系的与或结合图；、指出哪个是直接可解结点；、画出求解结点图；4、写出递归程序求解组合问题。/ */ * 程程 序：序：6_7.cpp * / * 编制时间：编制时间：2002年年10月月28日日 * / * 主要功能：计算组和数主要功能：计算组和数C(m,n) */ *#include / 预编译命令预编译命令Using namespace std;int main()/ 主函数开始主函数开始/ 测试一些结果测试一些结果cout C(6,0)= Cmn(6,0) endl;cout C(6,1)= Cmn(6,1) endl

38、;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#表一表一 为了将过河过程描述得更清楚，我们

39、给出了表为了将过河过程描述得更清楚，我们给出了表1 1。表。表中中L1 L2 L3 L4L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。表示左岸石柱上落在一起的青蛙的高度位置。L1 L1 在最上面，在最上面，L4 L4 在最下面的位置。引入这个信息就可比在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理较容易地看出对青蛙占位的约束条件。同理R1 R2 R3 R4R1 R2 R3 R4也也是如此。对水中石柱是如此。对水中石柱S S，也分成两个高度位置，也分成两个高度位置S1 S2S1 S2。对荷。对荷叶叶Y Y无须分层，因为它只允许一只青蛙落在其上。无须分层，

40、因为它只允许一只青蛙落在其上。t=0t=0为初为初始时刻，青蛙从小到大落在石柱始时刻，青蛙从小到大落在石柱L L上。上。t=1t=1为第一步：为第一步：1#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#，好象是原来在，

41、好象是原来在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系统。前者二只系统。前者二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。青蛙号大；后者二只

42、青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。从第五步到第九步可以看出的确是这么做的。 2YRSL31现在再看现在再看S=2，y=1 Jump(2,1) 我们将河中的两个石柱称作我们将河中的两个石柱称作S1和和S2，荷叶叫，荷叶叫y，考虑先，考虑先将将L上的青蛙的一半借助于上的青蛙的一半借助于S2和和y转移到转移到S1上，当然是上，当然是一半小号的青蛙在一半小号的青蛙在S1上，大上，大的留在的留在L上。上。y yLR RS1S1S2S2LRYS2876543S1214321这样这样 L S1 S2 y R 系统分解为系统分解为 ： （L S2 y R 系统）系统）

43、+ （S1 S2 y R 系统）系统）= 2 * （L S2 y R 系统）系统）= 2 * Jump(1,1)用归纳法用归纳法Jump(S, y)=2*Jump(S-1, y)5. 将上述分析出来的规律写成递归形式的与或结点图为：将上述分析出来的规律写成递归形式的与或结点图为：Jump(S,y)y+1S!=0S=0Jump(S-1,y)2*Jump(S-1,y)举例：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

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

45、) ;/Jump(s,y)为被调用函数为被调用函数cout Jump( s , /输出结果输出结果 y )= sum endl;/主程序结束主程序结束/ */ * 程程 序：序：6_5.cpp */ * 作作 者：者：wuwh */ * 编制时间：编制时间：2002年年10月月20日日 */ * 主要功能：青蛙过河主要功能：青蛙过河(递归递归) */ *#include /预编译命令预编译命令int Jump(int, int);/声明有被调用函数声明有被调用函数int main()/主函数主函数 int s=0,y=0,sum=0; cout s;/输入正整数输入正整数s cout y;/输

46、入正整数输入正整数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) 分区处理：分区处理：1、让、让 k=a z 2、将、将 k 放在放在 a m 3、使、使 az, az+1 , , a m-1 = a m 4、使、使 a m = y，则什么也不做。这是直接可，则什么也不做。这是直接可解结点。解结点。C 结点是在结

47、点是在 z y 情况下情况下 A 结点的解。结点的解。C 是一个与结是一个与结点。要对点。要对 C 求解需分解为三步。依次为：求解需分解为三步。依次为：1、先解、先解 D 结点，结点，D 结点是一个直接可解结点，功能是结点是一个直接可解结点，功能是进行所谓的分区处理，规定这一步要做的事情是进行所谓的分区处理，规定这一步要做的事情是 （1）将）将 a z 中的元素放到它应该在的位置上，比中的元素放到它应该在的位置上，比如如 m 位置。这时位置。这时 a m a z ； （2）让下标从）让下标从 z 到到 m-1 的数组元素小于等的数组元素小于等 a m ； （3）让下标从）让下标从 m+1 到到

48、 y 的数组元素大于的数组元素大于a m ；比如比如 a 数组中数组中 a z = 5，经分组处理后，经分组处理后，5 送至送至 a 4 。5 到位后，其左边到位后，其左边 a 0 a 3 的值都小于的值都小于 5；其右；其右边边 a 5 , a 6 大于大于 5。（见下图）（见下图）azyam下标：下标：下标：下标：zm-1ym+12、再解、再解 E 结点，这时要处理的是结点，这时要处理的是 a 0 a 3 ；3、再解、再解 F 结点，处理结点，处理a 5 ,a 6 。下面按照这种思路构思一个快速排序的程序框图。下面按照这种思路构思一个快速排序的程序框图。void sort( int arr

49、ay , int zz, int yy )int z, y, i , k ; ll r r l= ll; r = r r ; k = a r r a y l; T F d o w h ile (l = k ) (1 ) r = r-1 ; l r (2 ) T F a r r a y l= a r r a y r ; l= l+ 1 w h ile (l r )& & (a r r a y l = k ) (3 ) l= l+ 1 ; l r ; (4 ) T F a r r a y r = a r r a y l; w h ile (l!= r ); a r r a y l=

50、 k ; fo r (i= ll; i = r r ; i= i+ 1 ) 输输 出出 a r r a y i; 换换 行行 ; s o r t(a r r a y, ll, l-1 ); s o r t(a r r a y, l+ 1 , r r ); 下面举例说明排序过程下面举例说明排序过程图图1 a数组中有数组中有7个元素待排序个元素待排序1 让让 k = a z = a 0 = 5zy图图 1k2 进入直到型循环进入直到型循环 执行（执行（1）ay=a6=4 不满足当循环条件，不满足当循环条件，y不动。不动。 执行（执行（2）zy，做两件事：，做两件事： a z = a y ，即，即a

51、 0 = a 6 = 4， z = z +1 = 0+1 = 1，见图，见图2zy 图图 2k 执行（执行（3）图）图2中的中的a1k满足当循环的条件，满足当循环的条件，y = y-1 = 6-1 = 5见图见图5，之后退出当循环，因为，之后退出当循环，因为 a y = 3kzy图图 5k 执行（执行（2）a z =a y ，并让，并让 z = z+1=3，见图，见图6 zy图图 6k 执行（执行（3）由于）由于a3=1k，退出循环。见图，退出循环。见图7 zy图图 7k 执行（执行（4）az=ay，a5=7。见图。见图8 这时仍然这时仍然 zk，让，让 y = y-1 = 4。见图。见图9z

52、y图图 9k 之后，之后，z = y，退出直到型循环，做，退出直到型循环，做 a z = k，z = 4， a 4 = 5，这是，这是 5 的最终位置，的最终位置，5 将整个数据分成左右将整个数据分成左右两个集合，见图两个集合，见图10。zy图图 10左左右右k用上述思路去排左边的部分用上述思路去排左边的部分从从 z = 0 到到 y = 3，见图，见图11。让。让 k = a z = a 0 = 4，然后，然后进到直到型循环，进到直到型循环， 执行（执行（1）a y = 1k，不满足当循环的条件，不满足当循环的条件，y不动。不动。 执行（执行（2）a z = a y ，z = z+1 = 1

53、, 见图见图12zy图图 12zy图图 11k 执行（执行（3）a z k，z=z+1=2，a2k，z=z+1=3，这时，这时z=y，不会执行（，不会执行（4），同时退出直到型循环，见图），同时退出直到型循环，见图13。然后做然后做 a z =k，即，即a 3 =4，见图，见图14，左边也排好了。，左边也排好了。图图 14zy图图 13zykk4、用上述思路去排右边的部分，见图、用上述思路去排右边的部分，见图15，让，让k = a z = a 5 = 7，进入直到型循环；，进入直到型循环； 执行（执行（1）a y = 6k，y不动不动 执行（执行（2）a z = a y =6，z = z+1=

54、5+1=6，见图，见图16图图 16zy图图 15zyk这时这时 z = y，不再执行（，不再执行（3）（）（4），退出直到型循环后，），退出直到型循环后，做做 a z = k，见图，见图17。图图 17zyk在有了递归调用函数之后，主程序很容易写，主程序中应在有了递归调用函数之后，主程序很容易写，主程序中应包含包含1、 定义整型变量：数组定义整型变量：数组 a10 ，i ；2、 用循环结构输入待排序的数，将其放入用循环结构输入待排序的数，将其放入 a 数组；数组；3、 调用调用 sort 函数，使用三个实际参数函数，使用三个实际参数a将数组将数组 a 当实参；当实参；0数组下标下界；数组下标

55、下界；9数组下标上界；数组下标上界；4、 输出排序结果输出排序结果下面给出参考程序（分两页）下面给出参考程序（分两页）/ */ * 程程 序：序：6_6.cpp */ * 作作 者：者：wuwh */ * 编制时间：编制时间：2002年年10月月28日日 */ * 主要功能：快速排序主要功能：快速排序 */ *#include /预编译命令预编译命令void sort(int array , int zz, int yy)/被调用函数，数组被调用函数，数组array,zz,yy为形参为形参 /函数体开始函数体开始 int z,y,i,k; /定义变量定义变量 if ( zzyy ) /如果如果

56、 zz yy ,则做下列则做下列 7 件事件事: / 7 件事开始件事开始z = zz; y = yy; k = array z ; /第第1件事件事do /第第2件事件事(开始开始) while( z=k) y-; /2.1,右边的元素右边的元素=k,让让 y 往中间移往中间移 if( z y ) /2.2,右边的元素右边的元素k,让让 array z = array y ; /array y 送给送给 array z ， z = z+1; /同时让同时让 z 往中间移往中间移 while( z y) & (arrayz = k) z+; /2.3,左边的元素左边的元素=k,让让 z

57、 往中间移往中间移 if ( z k, 让让 array z array y = array z ; /送给送给array y while( z != y ) ; /第第2件事件事(结束结束)array z = k; /第第3件事件事,k已排到位已排到位for(i = zz ;i = yy ;i+) /第第4件事，输出件事，输出 coutai=arrayi; ;cout endl; /第第5件事，换行件事，换行sort( array, zz ,z-1 ); /第第6件事，排左边部分件事，排左边部分sort( array ,z+1, yy); /第第7件事，排右边部分件事，排右边部分 /7件事结束件事结束 /函数体结束函数体结束void main() /主函数开始主函数开始 int a10,i; /整型变量整型变量cout 请输入请输入10个整数个整数n; /提示信息提示信息for (i = 0;