第4讲 递归专题讲座.doc

第4讲 递归递归是算法设计中的一种基本而重要的算法。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。递归方法具有易于描述、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。4.1 递归概述一个函数在它的函数体内调用它自身称为递归（recursion）调用。是一个过程或函数在其定义或说明中直接或间接调用自身的一种方法，通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。使用递归要注意以下几点：（1）递归就是在过程或函数里调用自身；（2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。例如有函数r如下：int r(int a) b=r(a1); return b;这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。例4-1 用递归法计算n!。n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。（1）描述递归关系递归关系是这样的一种关系。设U1,U2,U3,Un,是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。注意到，当n1时，n!=n*(n1)!（n=0时，0!=1），这就是一种递归关系。对于特定的k!，它只与k与(k1)!有关。（2）确定递归边界在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：#include int f(int x) return(f(x1);main() printf(f(5);它没有规定递归边界，运行时将无限循环，会导致错误。（3）写出递归函数并译为代码将步骤1和步骤2中的递归关系与边界统一起来用数学语言来表示，即n!= n*(n1)! 当n1时n!= 1 当n=1时再将这种关系翻译为代码，即一个函数：long f(int n) long g;if(n0) printf(n0, 输入错误！);else if(n=1) g=1; else g=n*f(n1);return(g);（4）完善程序主要的递归函数已经完成，设计主程序调用递归函数即可。#include long f(int n) long g;if(n0) printf(n0,输入错误！);else if(n=1) g=1; else g=n*f(n-1); return(g); void main() int n; long y; printf( 计算n!，请输入n: );scanf(%d,&n); y=f(n); printf( %d!=%ld n,n,y); 程序中给出的函数f是一个递归函数。主函数调用f后即进入函数f执行，如果n0,n=0或n=1时都将结束函数的执行，否则就递归调用f函数自身。由于每次递归调用的实参为n1，即把n1的值赋予形参n，最后当n1的值为1时再作递归调用，形参n的值也为1，将使递归终止，然后可逐层退回。下面我们再举例说明该过程。设执行本程序时输入为5，即求 5!。在主函数中的调用语句即为y=f(5)，进入f函数后，由于n=5，不等于0或1，故应执行f=f(n1)*n，即f=f(51)*5。该语句对f作递归调用即f(4)。进行4次递归调用后，f函数形参取得的值变为1，故不再继续递归调用而开始逐层返回主调函数。f(1)的函数返回值为1，f(2)的返回值为1*2=2，f(3)的返回值为2*3=6，f(4) 的返回值为6*4=24，最后返回值f(5)为24*5=120。综上，得出构造一个递归方法基本步骤，即描述递归关系、确定递归边界、写出递归函数并译为代码，最后将程序完善。例4-2 计算阿克曼函数 阿克曼(Ackerman)函数a(n，m)递归定义如下：试输出阿克曼函数的(m3,n10)的值。解：a函数是一个随着变量m,n变化的双递归函数。当m=0时，a(0,n)=n+1，这是递归终止条件；当n=0时，a(m,0)=a(m-1,1)；这是n=0时的递归表达式当m,n1时，a(m,n)=a(m-1,a(m,n-1)，这是递归表达式。试以a(1,3)为例说明函数的递归过程：a(1,3)=a(0,a(1,2)=a(0,a(0,a(1,1)= a(0,a(0,a(0,a(1,0) = a(0,a(0,a(0,a(0,1)= a(0,a(0,a(0,2) = a(0,a(0,3)=a(0,4)=5a函数及其调用描述如下：int a(int m,int n) if(m=0) return n+1; else if(n=0) return a(m-1,1); else return a(m-1,a(m,n-1);#include void main() int m,n; printf(a(m,n); for(n=0;n=10;n+) printf( n=%1d ,n); printf(n); for(m=0;m=3;m+) printf( m=%d,m); for(n=0;n=10;n+) printf(%5d,a(m,n); printf(n); printf(n);程序运行求示例：a(m,n) n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 m=0 1 2 3 4 5 6 7 8 9 10 11 m=1 2 3 4 5 6 7 8 9 10 11 12 m=2 3 5 7 9 11 13 15 17 19 21 23 m=3 5 13 29 61 125 253 509 1021 2045 4093 8189若采用递推求a(3,10)，由上表可知a(3,9)=4093，则a(3,10)=a(2,a(3,9)=a(2,4093) n的取值是未知的且非常大，可见递推完成的难度。 4.2 排队购票1. 问题提出一场球赛开始前，售票工作正在紧张的进行中。每张球票为50元，现有30个人排队等待购票，其中有20 个人手持50元的钞票，另外10个人手持100元的钞票。假设开始售票时售票处没有零钱，求出这30个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数。（约定：拿同样面值钞票的人对换位置后为同一种排队。）2递归设计要点我们考虑一般情形：有m+n个人排队等待购票，其中有m 个人手持50元的钞票，另外n个人手持100元的钞票。求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数（这里正整数m，n从键盘输入）。这是一道典型的组合计数问题，考虑用递推求解。令f(m,n)表示有m个人手持50元的钞票，n个人手持100元的钞票时共有的方案总数。我们分情况来讨论这个问题。(1) n=0n=0意味着排队购票的所有人手中拿的都是50元的钱币，注意到拿同样面值钞票的人对换位置后为同一种排队，那么这m个人的排队总数为1，即f(m,0)=1。(2）mn当mn时，即排队购票的人中持50元的人数小于持100元的钞票，即使把m张50元的钞票都找出去，仍会出现找不开钱的局面，所以这时排队总数为0，即f(m,n)=0。 (3）其它情况我们思考m+n个人排队购票，第m+n个人站在第m+n-1个人的后面，则第m+n个人的排队方式可由下列两种情况获得：1） 第m+n个人手持100元的钞票，则在他之前的m+n-1个人中有m个人手持50元的钞票，有n-1个人手持100元的钞票，此种情况共有f(m,n-1)。2） 第m+n个人手持50元的钞票，则在他之前的m+n-1个人中有m-1个人手持50元的钞票，有n个人手持100元的钞票，此种情况共有f(m-1,n)。由加法原理得到f(m,n)的递推关系：f(m,n)=f(m,n-1)+f(m-1,n)初始条件：当mn时，f(m,n)=0当n=0时，f(m,n)=13. 购票排队递归程序实现/ 购票排队 long f(int j,int i)long y; if(i=0) y=1; else if(ji) y=0; / 确定初始条件 else y=f(j-1,i)+f(j,i-1); / 实施递归 return(y);#includevoid main()int m,n; printf( input m,n: ); scanf(%d,%d,&m,&n); printf( f(%d,%d)=%ld.n,m,n,f(m,n); 运行程序，input m,n: 15,12，得 f(15,12)=4345965.4. 购票排队递推程序实现/ 购票排队 #includevoid main()int m,n,i,j; long f100100; printf( input m,n: ); scanf(%d,%d,&m,&n); for(j=1;j=m;j+) / 确定初始条件 fj0=1; for(j=0;j=m;j+) for(i=j+1;i=n;i+) fji=0; for(i=1;i=n;i+) for(j=i;j=m;j+) fji=fj-1i+fji-1; / 实施递推 printf( f(%d,%d)=%ld.n,m,n,fmn); 运行程序，input m,n: 20,10，得 f(20,10)=15737865.比较以上两个程序，递推程序的运行速度要快于递归程序。4.3 汉诺塔问题汉诺塔（Hanoi），又称河内塔问题，是印度的一个古老传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去。庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。后来，这个传说就演变为汉诺塔游戏：图35-1 汉诺塔游戏示意图（1）有三根桩子A、B、C。A桩上有n个碟子，最大的一个在底下，其余一个比一个小，依次叠上去。（2）每次移动一块碟子，小的只能叠在大的上面。 （3）把所有碟子从A桩全部移到C桩上，如图35-1所示。试求解n个圆盘A桩全部移到C桩上的移动次数，并求出n个圆盘的移动过程。4.3.1 求移动次数1. 递归关系当n=1时，只一个盘，移动一次即完成。当n=2时，由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，首先把小盘从A桩移到B桩；然后把大盘从A桩移到C桩；最后把小盘从B桩移到C桩，移动3次完成。设移动n个盘的汉诺塔需g(n)次完成。分以下三个步骤：(1) 首先将n个盘上面的n-1个盘子借助C桩从A桩移到B桩上，需g(n-1)次；(2) 然后将A桩上第n个盘子移到C桩上（1次）；(3) 最后，将B桩上的n-1个盘子借助A桩移到C桩上，需g(n-1)次。因而有递归关系：g(n)=2*g(n-1)+1初始条件(递归出口)：g(1)=1.2. 递归求解汉诺塔移动次数的程序设计/ 汉诺塔n盘移动次数 #includevoid main()double g(int m); / 确定初始条件 int n; printf( 请输入盘片数n: ); scanf(%d,&n); if(n1时，分以下三步：(1) 将A桩上面的n-1个盘子借助C桩移到B桩上，即hn(n-1,a,c,b)；(2) 将A桩上第n个盘子移到C桩上，即mv(a,c)；(3) 将B桩上的n-1个盘子借助A桩移到C桩上，即hn(n-1,b,a,c)。在主程序中，用hn(m,1,2,3)带实参m,1,2,3调用hn(n,a,b,c)，这里m为具体移动盘子的个数。同时设置变量k统计移动的次数。2. 展示汉诺塔移动过程的程序设计函数mv(x,y)输出从x桩到y桩的过程，这里x,y分别不同情况取“A”或“B”或“C”，主函数调用hn(m,A,B,C)。/ 展示汉诺塔移动过程的递归设计 #include int k=0;void mv(char x,char y) / 输出函数 printf( %c-%c ,x,y); k+; / 统计移动次数 if(k%5=0) printf(n); void hn(int m,char a,char b,char c) / 递归函数 if(m=1) mv(a,c); else hn(m-1,a,c,b);mv(a,c);hn(m-1,b,a,c);#include void main() / 主函数 int n; printf(n input n: ); scanf(%d,&n); hn(n,A,B,C); printf(n k=%d n,k); / 输出移动次数 3. 程序运行示例与分析运行程序，input n: 4A-B A-C B-C A-B C-AC-B A-B A-C B-C B-AC-A B-C A-B A-C B-Ck=15(1) 上面的运行结果是实现函数hn(4,A,B,C)的过程，可分解为以下三步：1） A-B A-C B-C A-B C-A C-B A-B， 这前7步是实施hn(3,A,C,B),即完成把上面3个盘从A桩借助C移到B桩。2）A-C 这1步是实施着mv(A,C)，即把最下面的盘从A桩移到C桩。3） B-C B-A C-A B-C A-B A-C B-C，这后7步是实施hn(3,B,A,C),即完成把B桩的3个盘借助A移到C桩。(2) 其中实现hn(3,A,C,B)的过程,可分解为以下三步:1） A-B A-C B-C，这前3步是实施hn(2,A,B,C),即完成把上面两个盘从A桩借助B移到C桩。2） A-B，这1步是实施mv(A,B),即把第3个盘从A桩移到B桩。3） C-A C-B A-B， 这后3步是实施hn(2,C,A,B),即完成把C桩的两个盘借助A移到B桩。从以上的结果分析可进一步帮助对递归的理解。4.4 旋转数阵4.4.1 双转向旋转方阵 1. 案例提出把前n2个正整数1，2，.，n2 从左上角开始,由外层至中心按顺时针方向螺旋排列所成的数字矩阵,称n阶顺转方阵；按逆时针方向螺旋排列所成的称n阶逆转方阵。1 2 3 4 5 1 16 15 14 13 16 17 18 19 6 2 17 24 23 12 15 24 25 20 7 3 18 25 22 1114 23 22 21 8 4 19 20 21 1013 12 11 10 9 5 6 7 8 95阶顺转方阵 5阶逆转方阵下面即为一个5阶顺转方阵与5阶逆转方阵。设计程序选择转向分别构造并打印这二种旋转方阵。2. 设计要点设计以顺转展开，设置二维数组ahv存放方阵中第h行第v列的整数。把n阶方阵从外到内分圈，外圈内是一个n-2阶顺转方阵，只是起始数，具有与原问题相同的特性属性。因此，设置旋转方阵递归函数t(a,b,s,d)，其中a是存储方阵元素的数组；b为每个方阵的起始位置；d是为a数组赋值的整数；s是方阵的阶数。b赋初值0, 因数组下标从0开始，方阵的起始位置为(0,0)。以后每一圈后进入下一内方阵，起始位置b需增1。d从1开始递增1取值，分别赋值给数组的各元素，至n2为止。s从方阵的阶数n开始，以后每一圈后进入下一内方阵，s需减2。s=0时返回，作为递归的出口；s=1时，即方阵只有一个数，显然为abb=d，返回。s1时，在函数t(a,b,s,d)中还需调用t(a,b+1,s-2,d)。递归函数t(a,b,s,d)中对方阵的每一圈的各边的各个元素赋值：1） 一圈的上行从左至右递增for(j=1;js;j+) ahv=d;v+;d+; / 行号h不变，列号v递增，数d递增 2） 一圈的右列从上至下递增for(j=1;js;j+) ahv=d;h+;d+; / 列号v不变，行号v递增，数d递增 3） 一圈的下行从右至左递增for(j=1;js;j+) ahv=d;v-;d+; / 行号h不变，列号v递减，数d递增 4） 一圈的左行从下至上递增for(j=1;js;j+) ahv=d;h-;d+; / 列号v不变，行号h递减，数d递增 经以上4步，完成一圈的赋值。主程序中，只要带实参调用递归函数t(a,0,n,1)即可。方阵按所选的转向以二维形式输出：p=1为顺转，输出ahv；p=2为逆转，输出avh3. 程序实现/ 双转向旋转方阵递归设计 #include int n,a2020=0;void main() int h,v,b,p,s,d;printf( 请选择方阵阶数n：);scanf(%d,&n);printf( 请选择转向，顺转1，逆转2：);scanf(%d,&p);b=1;s=n;d=1;void t(int a2020,int b,int s,int d); / 递归函数说明 t(a,b,s,d);if(p=1) / 按要求输出旋转方阵 printf( %d阶顺转方阵: n,n);else printf( %d阶逆转方阵: n,n);for(h=1;h=n;h+) for(v=1;v=n;v+) if(p=1) printf( %3d,ahv); else printf( %3d,avh); printf(n); return;void t(int a2020,int b,int s,int d) / 定义递归函数 int j,h=b,v=b;if(s=0) return; / 递归出口 if(s=1) abb=d;return;for(j=1;js;j+) / 一圈的上行从左至右递增 ahv=d;v+;d+;for(j=1;js;j+) / 一圈的右列从上至下递增 ahv=d;h+;d+;for(j=1;js;j+) / 一圈的下行从右至左递增 ahv=d;v-;d+;for(j=1;j1时，在函数t(a,b,s,d)中还需调用t(a,b+1,s-2,d)。递归函数t(a,b,s,d)中对矩阵的每一圈的各边的各个元素赋值：1） 一圈的上行n+1-2*b个元素，从左至右递增for(j=1;j=n+1-2*b;j+) ahv=d;v+;d+; / 行号h不变，列号v递增，数d递增 2） 一圈的右列m+1-2*b个元素，从上至下递增for(j=1;j=m+1-2*b;j+) ahv=d;h+;d+; / 列号v不变，行号v递增，数d递增 3） 一圈的下行n+1-2*b个元素，从右至左递增for(j=1;jm*n) s=0;break;4） 一圈的右列m+1-2*b个元素，从下至上递增for(j=1;jm*n) s=0;break; 经以上4步，完成一圈的赋值。注意到当s=min(m,n)为奇数时，最后一圈(s=1)只有一半。为避免最后一圈的另一半再赋值可能因数据覆盖导致出错，当完成整数d=m*n赋值后，即返回，作为递归的出口。主程序中，只要带实参调用递归函数t(a,1,min(m,n),1)即可。按圈赋值完成，输出m行n列的顺转矩阵。3. mn顺转矩阵递归设计/ mn顺转矩阵递归设计 #include int m,n,a2020=0;void main() int h,v,b,s,d;printf( 数阵为m行n列，请确定m,n：);scanf(%d,%d,&m,&n);s=m;if(mn) s=n;b=1;d=1;void t(int a2020,int b,int s,int d); / 递归函数说明 t(a,b,s,d); / 调用递归函数 printf( %d%d顺转矩阵: n,m,n); for(h=1;h=m;h+) for(v=1;v=n;v+) printf( %3d,ahv); printf(n); return;void t(int a2020,int b,int s,int d) / 定义递归函数 int j,h=b,v=b;if(s=0) return; / 递归出口 for(j=1;j=n+1-2*b;j+) / 一圈的上行从左至右递增 ahv=d;v+;d+;for(j=1;j=m+1-2*b;j+) / 一圈的右列从上至下递增 ahv=d;h+;d+;for(j=1;jm*n) return; / 另一递归出口 for(j=1;jm*n) return;t(a,b+1,s-2,d); / 调用内一圈递归函数 4. 程序运行示例与说明m行n列矩阵,请确定m,n: 5,8 5行8列旋转矩阵为: 1 2 3 4 5 6 7 8 22 23 24 25 26 27 28 9 21 36 37 38 39 40 29 10 20 35 34 33 32 31 30 11 19 18 17 16 15 14 13 12 如果m=n，还是上述赋值，把行列互换打印输出，可得逆转矩阵。这样处理是巧妙的，较为简便。如果mn，要得到逆转矩阵，必须重新赋值才行。4.5 快速排序与选择4.5.1 快速排序1. 排序概述排序就是将一组数据按需要排列成一个有序序列，是数据处理中一种重要的运算。排序分为升序与降序。通常把待排序的n个数据存放在一个数组中，排序后的n个数据仍存放在这n个数组元素中。最简单的排序是把存放在数组的n个数据逐个比较，必要时进行数据交换。当i=1时，r1分别与其余n-1个数据rj(j=2,3,n)比较，若rirj，借助变量t实施交换，确保r1最小。然后，i=2时，r2分别与其余n-2个数据rj(j=3,4,n)比较，若rirj，借助变量t实施交换，确保r2次小。依此类推，最后当i=n-1时，rn-1与rn比较，若rn-1rn实施交换，确保rn最大。逐个比较排序进行升序排序的算法描述如下： for(i=1;i=n-1;i+) for(j=i+1;jrj) t=ri;ri=rj;rj=t;显然，数据比较的次数为 可见逐个比较排序的时间复杂度为O(n2)。当n很大时，排序所需时间会很长。因为逐个比较排序最简单，当n不是很大时也常使用。为了缩减排序的时间，降低排序的时间复杂度，出现了很多新颖而有特色的排序算法，下面介绍的快速排序法就是其中之一。2. 快速排序设计要点快速排序又称为分区交换排序，其基本思想是分治，即分而治之：在待排序的n个数据r1,2,n中任取一个数（例如r1）作为基准，把其余n-1个数据分为两个区，小于基准的数放在左边，大于基准的数放在右边。这样分成的两个区实际上是待排序数据的两个子列。然后对这两个子列分别重复上述分区过程，直到所有子列只有一个元素，即所有元素排到位后，输出排序结果。分区交换描述如下：while(i!=j) while(rj=r0 & ji) / 从左至右逐个检查是否大于基准 j=j-1; if(ij) ri=rj;i=i+1; / 把小于基准的一个数赋给r(i) while(rii) / 从右至左逐个检查是否小于基准 i=i+1; if(ij) rj=ri;j=j-1; / 把大于基准的一个数赋给r(j) 为了解分区交换的实施，以具体数据稍加剖析如下。设n=12，参与排序的12个整数为：r1=25,45,40,13,30,27,56,23,34,41,46,r12=52 调用qk(r,1,12):i=1,j=12,选用r1=25为基准，并赋给r0，即r0=25，进入112实施分区交换的while循环： 从左至右逐个检查大于基准25的数，至j=8,r8=23小于基准，则r1=23,i=2； 从右至左逐个检查小于基准25的数，至i=2,r2=45大于基准，则r8=45,j=7； i=2,j=7,ij，继续while循环： 从左至右逐个检查大于基准25的数，至j=4,r4=13小于基准，则r2=13,i=3； 从右至左逐个检查小于基准25的数，至i=3,r3=40大于基准，则r4=40,j=3； i=3,j=3,i=j，结束while循环，由ri=r0定位基准为r3=25。 至此，完成qk(r,1,12)的分区，即为：r1=23,13,25,40,30,27,56,45,34,41,46,r12=52 进一步调用qk(r,1,2)与qk(r,4,12)，继续细化分区。 例如调用qk(r,1,2)：i=1,j=2,选用r1=23为基准，并赋给r0，即r0=23，进入12实施分区交换的while循环：从左至右逐个检查大于基准23的数，至j=2,r2=13小于基准，则r1=13,i=2；从右至左未检查出小于基准23的数； i=2,j=2,i=j，结束while循环，由ri=r0定位基准为r2=23。 至此，完成qk(r,1,2)的分区，即为：r1=13,r2=23 而调用qk(r,4,12)，还需作多次分区。 所有分区完成，即升序排序完成，返回调用qk(r,1,12)处，输出排序结果。3. 快速排序程序实现/ 递归实现快速排序 #include #include #include void main() int i,n,t,r20001; void qk(int r,int m1,int m2); / 函数声明 t=time(0)%1000;srand(t); / 随机数发生器初始化 printf( input n:); scanf(%d,&n); printf( 参与排序的%d个整数为：n,n); for(i=1;i=n;i+) ri=rand()%(4*n)+10; / 随机产生并输出n个整数 printf(%d ,ri); qk(r,1,n); printf( n 以上%d个整数从小到大排序为：n,n); for(i=1;i=n;i+) printf(%d ,ri); / 输出排序结果 printf(n);void qk(int r,int m1,int m2) / 快速排序递归函数 int i,j; if(m1=r0 & ji) / 从左至右逐个检查是否大于基准 j=j-1; if(ij) ri=rj;i=i+1; / 把小于基准的一个数赋给r(i) while(rii) / 从右至左逐个检查是否小于基准 i=i+1; if(ik，可知左边小于该基准的数s-1k，则在左边的子区继续分区。（3） 若sk，可知所寻求的第k小元素在右边子区，则在右边的子区继续分区。依此（2）（3）继续分区，直到出现（1）结束分区，输出结果。3. 程序实现/ 递归实现选择 #include #include #include void main() int i,j,k,n,t,r20001; int s(int r,int m1,int m2,int m); / 函数声明 t=time(0)%1000;srand(t); / 随机数发生器初始化 printf( 参与选择的有n个整数,请确定n: ); scanf(%d,&n); printf( 选择第k小整数,请确定k: ); scanf(%d,&k); printf( 参与选择的%d个整数为：n,n); for(i=1;i=n;i+) t=rand()%(4*n)+10; / 随机产生并输出n个整数 for(j=1;ji;j+) if(t=rj) break; if(j=i) ri=t; printf( %d,ri); else i-; continue; s(r,1,n,k); printf( n 以上%d个整数中第%d小整数为%d.n,n,k,rk); int s(int r,int m1,int m2,int m) / 快速选择递归函数 int i,j; if(m1=r0 & ji) / 从左至右逐个检查是否大于基准 j=j-1; if(ij) ri=rj;i=i+1; / 把小于基准的一个数赋给r(i) while(rii) / 从右至左逐个检查是否小于基准 i=i+1; if(im) return s(r,m1,i-1,m); else return s(r,i+1,m2,m); / 选择继续分区 4. 程序运行示例参与选择的有