2022年递归专题讲座 .pdf

《2022年递归专题讲座 .pdf》由会员分享，可在线阅读，更多相关《2022年递归专题讲座 .pdf（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1 第 4 讲递归递归是算法设计中的一种基本而重要的算法。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。递归方法具有易于描述、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。4.1递归概述一个函数在它的函数体内调用它自身称为递归（recursion ）调用。是一个过程或函数在其定义或说明中直接或间接调用自身的一种方法，通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有

2、限的语句来定义对象的无限集合。 用递归思想写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进； 当边界条件满足时，递归返回。使用递归要注意以下几点：（1）递归就是在过程或函数里调用自身；（2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。例如有函数r 如下：int r(int a) b=r(a- 1); return b; 这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用

3、，然后逐层返回。构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。例 4-1 用递归法计算n! 。n! 的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。（1）描述递归关系递归关系是这样的一种关系。设U1,U2,U3,Un, ,是一个序列，如果从某一项k 开始，Un和它之前的若干项之间存在一种只与n 有关的关系，这便称为递归关系。注意到，当n1 时， n!=n*(n- 1)! （n=0 时，0!=1 ） ，这就是一种递归关系。对于特定的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

4、 - - - 名师精心整理 - - - - - - - 第 1 页，共 33 页 - - - - - - - - - 2 k! ，它只与 k 与(k - 1)! 有关。（2）确定递归边界在步骤 1 的递归关系中， 对大于 k 的 Un的求解将最终归结为对Uk的求解。 这里的 Uk称为递归边界（或递归出口） 。在本例中，递归边界为k=0，即 0!=1 。对于任意给定的N!，程序将最终求解到0! 。确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：#include int f(int x) return(f(x- 1); main() printf(f(5)

5、; 它没有规定递归边界，运行时将无限循环，会导致错误。（3）写出递归函数并译为代码将步骤 1 和步骤 2 中的递归关系与边界统一起来用数学语言来表示，即n!= n*(n- 1)! 当 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(n- 1); return(g); （4）完善程序主要的递归函数已经完成，设计主程序调用递归函数即可。#include long f(int n) long g; if(n0) printf(n

6、0,输入错误！ ); 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 33 页 - - - - - - - - - 3 y=f(n); printf( %d!=%ld n,n,y); 程序中给出的函数f 是一个递归函数。 主函数调用 f 后即进入函数f

7、执行， 如果 n0,n=0或 n=1时都将结束函数的执行， 否则就递归调用f 函数自身。由于每次递归调用的实参为n- 1，即把 n- 1的值赋予形参n，最后当 n- 1 的值为 1 时再作递归调用，形参n 的值也为 1，将使递归终止，然后可逐层退回。下面我们再举例说明该过程。设执行本程序时输入为5，即求 5! 。在主函数中的调用语句即为 y=f(5) ， 进入 f 函数后，由于 n=5， 不等于 0或 1， 故应执行 f=f(n - 1)*n ， 即 f=f(5 - 1)*5 。该语句对f 作递归调用即f(4) 。进行 4 次递归调用后， f 函数形参取得的值变为1，故不再继续递归调用而开始逐

8、层返回主调函数。 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)递归定义如下：1,)1,(,1(0)1,1(01),(nmnmamanmamnnma试输出阿克曼函数的(m3,n 10)的值。解： a 函数是一个随着变量m,n 变化的双递归函数。当 m=0时， a(0,n)=n+1 ，这是递归终止

9、条件；当 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)=5 a 函数及其调用描述如下：int a(int m,int n) if(m=0) return n+1; else if(n=0) return a(m-1,1); el

10、se return a(m-1,a(m,n-1); #include void main() int m,n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 33 页 - - - - - - - - - 4 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); pr

11、intf(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的取值是未知的且非常大，可见递推完成的

12、难度。4.2 排队购票1. 问题提出一场球赛开始前，售票工作正在紧张的进行中。每张球票为50 元，现有 30 个人排队等待购票，其中有20 个人手持 50 元的钞票，另外10 个人手持 100 元的钞票。假设开始售票时售票处没有零钱， 求出这 30 个人排队购票， 使售票处不至出现找不开钱的局面的不同排队种数。（约定：拿同样面值钞票的人对换位置后为同一种排队。）2递归设计要点我们考虑一般情形： 有 m+n个人排队等待购票， 其中有 m 个人手持 50 元的钞票， 另外 n个人手持100元的钞票。求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数（这里正整数m ，n从键盘输入

13、）。这是一道典型的组合计数问题，考虑用递推求解。令 f(m,n) 表示有 m个人手持 50 元的钞票， n个人手持 100 元的钞票时共有的方案总数。我们分情况来讨论这个问题。(1) n=0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 33 页 - - - - - - - - - 5 n=0 意味着排队购票的所有人手中拿的都是50元的钱币，注意到拿同样面值钞票的人对换位置后为同一种排队，那么这m个人的排队总数为1，即 f(m,0)=1 。(2 ）mn 当 mn时，即排

14、队购票的人中持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 元的钞票，此

15、种情况共有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)=1 3. 购票排队递归程序实现/ 购票排队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); #include void main() int m,n; printf( input m,n: ); scanf(%d,%d,&m,&n);

16、printf( f(%d,%d)=%ld.n,m,n,f(m,n); 运行程序， input m,n: 15,12，得 f(15,12)=4345965. 4. 购票排队递推程序实现/ 购票排队#include void main() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 33 页 - - - - - - - - - 6 int m,n,i,j; long f100100; printf( input m,n: ); scanf(%d,%d,&m,&n); fo

17、r(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），又称河内塔问题，是印度的一个古老传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面

18、套着64 个圆的金片， 最大的一个在底下， 其余一个比一个小，依次叠上去。庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。后来，这个传说就演变为汉诺塔游戏：木桩A木桩 B木桩 C木桩A木桩 B木桩 C123N123N图1图 35-1 汉诺塔游戏示意图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 33 页 - - - - - - - - - 7 （1）有三根桩子A、B、C 。A桩上有 n 个

19、碟子，最大的一个在底下，其余一个比一个小，依次叠上去。（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 个盘子

20、借助 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 盘移动次数#include void main() double g(int m); / 确定初始条件 int n; printf( 请输入盘片数n: ); scanf(%d,&n); if(n1 时，分以下三步：(1) 将 A桩上面的 n-1 个盘子

21、借助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 i

22、nt 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 33 页 - - - - - - - - - 9 hn(m-1,a,c,b); mv(a,c); hn(m-1,

23、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: 4 A-B A-C B-C A-B C-A C-B A-B A-C B-C B-A C-A B-C A-B A-C B-C k=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,

24、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，

25、这后 3 步是实施 hn(2,C,A,B),即完成把 C桩的两个盘借助A移到 B桩。从以上的结果分析可进一步帮助对递归的理解。4.4 旋转数阵4.4.1 双转向旋转方阵1. 案例提出名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 33 页 - - - - - - - - - 10 把前 n2个正整数 1，2，. ， n2 从左上角开始 ,由外层至中心按顺时针方向螺旋排列所成的数字矩阵 ,? 称 n 阶顺转方阵；按逆时针方向螺旋排列所成的称n 阶逆转方阵。下面即为一个5 阶

26、顺转方阵与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 为止。

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

28、;js;j+) ahv=d;v-;d+; / 行号 h 不变，列号 v 递减，数 d递增4） 一圈的左行从下至上递增for(j=1;js;j+) ahv=d;h-;d+; / 列号 v 不变，行号 h递减，数 d递增经以上 4 步，完成一圈的赋值。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 11 14 23 22 21 8 4 19 20 21 10 13 12 11 10 9 5 6 7 8 9 5 阶顺转方阵5 阶逆转方阵名师资料总结 - - -精品资料欢迎下载 - - - - -

29、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 33 页 - - - - - - - - - 11 主程序中，只要带实参调用递归函数t(a,0,n,1)即可。方阵按所选的转向以二维形式输出：p=1 为顺转，输出ahv；p=2 为逆转，输出avh 3. 程序实现/ 双转向旋转方阵递归设计#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);

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

31、=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+) / 一圈的下行从右至左递增名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 33 页 - - - - - - - - - 12 ahv=d;v-;d+; for(j=1;j1 时，在

32、函数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

33、 个元素，从下至上递增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列的顺转矩阵。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 33 页 - - - - - - -

34、 - - 14 3. m n 顺转矩阵递归设计/ m n 顺转矩阵递归设计#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

35、,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. 程序运行示例与说明名

36、师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 33 页 - - - - - - - - - 15 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 ，还是上述赋值，把行列互换打印输出，可得逆转矩阵。这样处理是巧妙

37、的，较为简便。如果 m n，要得到逆转矩阵，必须重新赋值才行。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，借

38、助变量 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; 显然，数据比较的次数为2)1()1(21nnns可见逐个比较排序的时间复杂度为O(n2) 。当 n 很大时，排序所需时间会很长。因为逐个比较排序最简单，当n不是很大时也常使用。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

39、 - - 第 15 页，共 33 页 - - - - - - - - - 16 为了缩减排序的时间，降低排序的时间复杂度，出现了很多新颖而有特色的排序算法，下面介绍的快速排序法就是其中之一。2. 快速排序设计要点快速排序又称为分区交换排序，其基本思想是分治，即分而治之：在待排序的n 个数据r1,2,n 中任取一个数（例如r1 ）作为基准，把其余n-1 个数据分为两个区，小于基准的数放在左边，大于基准的数放在右边。这样分成的两个区实际上是待排序数据的两个子列。然后对这两个子列分别重复上述分区过程，直到所有子列只有一个元素，即所有元素排到位后，输出排序结果。分区交换描述如下：while(i!=j)

40、 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 ，进入 1 12

41、 实施分区交换的 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

42、,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 ，进入 1 2 实施分区交换的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)的分区，即为：名师资料总结 - - -精品资料欢迎下载 - - - - - -

43、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 33 页 - - - - - - - - - 17 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); / 随机数发

44、生器初始化 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) / 从左至右逐

45、个检查是否大于基准 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

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

47、,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. 程序运行示例参与选择的有n 个整数 , 请

48、确定 n: 15 选择第 k 小整数 , 请确定 k: 3 参与选择的 15 个整数为： 26 41 57 30 50 45 25 53 68 60 46 32 59 61 52 以上 15 个整数中第 3 小整数为 30. 5. 快速选择的时间复杂度分析设 T(n) 为对 n 个元素分区选择所进行的时间，每次分区正好把待分区间分为长度相等的两个子区间。注意到每一次分区时对每一个元素者要扫描一遍，所需时间为O(n)，于是)()1(2/4/)8/(2/)4/()2/()(nOnTnnnnnTnnnTnnTnT以上分区按每个区数的个数相等计算。如果每次分区时各区数的个数不一定相等，平均时间性能为O

49、(n )，低于排序的时间复杂度O(nn2log)。4.6 排列组合的实现排列组合是组合数学的基础，从n 个不同元素中任取m个，约定1m n，按任意一种次序排成一列，称为排列，其排列种数记为A(n,m) 。从 n个不同元素中任取m个( 约定 1mn) 成一组，称为一个组合，其组合种数记为C(n,m) 。计算 A(n,m) 与 C(n,m) 只要简单进行乘运算即可，要具体展现出排列的每一列与组合的每一组，决非轻而易举。本节应用递归设计来具体实现排列与组合。4.6.1 实现基本排列 A(n,m)与组合 C(n,m) 1实现基本排列A(n,m) 对指定的正整数m,n(约定 1 m n) ，具体实现从n

50、 个不同元素中任取m个元素 A(n,m)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 33 页 - - - - - - - - - 21 的每一排列。2. 设计要点设置 a 数组在 n 个整数 1 n中选取 m个数。递归函数 p(k) 的变量 k 从 1 开始取值。当km时，第 k 个数 a(k) 取 i(1 n)，并标志量 u=0。（1）若 a(k) 与其前面已取的数a(j)(jk)比较，出现a(k)=a(j)，即第 k 个数取 i 不成功，标志量u=1。（2）若