第2章递归与分治策略.ppt.pptVIP

算法设计与分析第二章 递归与分治策略 杨圣洪 学习要点: 理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 （1）二分有哪些信誉好的足球投注网站技术； （2）大整数乘法； （3）Strassen矩阵乘法； （4）棋盘覆盖； （5）合并排序和快速排序； （6）线性时间选择； （7）最接近点对问题； （8）循环赛日程表。 第2章 递归与分治策略 本章主要知识点： 2.1 递归的概念 2.2 分治法的基本思想 2.3 二分有哪些信誉好的足球投注网站技术 2.4 大整数的乘法 2.5 Strassen矩阵乘法 2.6 棋盘覆盖 2.7 合并排序 2.8 快速排序 2.9 线性时间选择 2.10 最接近点对问题 2.11 循环赛日程表 计划授课时间：6～8课时 2.1 递归的概念 直接或间接地调用自身的算法称为递归算法 用函数自身给出定义的函数称为递归函数(板) 使用递归技术使算法的描述简洁、易理解。 在实时系统或嵌入系统开发中，建议不使用递归算法 下面来看几个实例。 2.1 递归的概念 例1 阶乘函数(板) 可递归地定义为：高?低 其中： n=0时，n!=1为结束条件 n0时，n!=n(n-1)!为递归方程 结束条件也称为边界条件，这二者是递归函数的二个要素。 T=1; //递归结束条件为循环初值 递归为递推 for (i=2;in+1;i++){T=T*i;} 循环低?高 2.1 递归的概念 public static int jcdg(int n) { if (n = 1) return 1;//结束条件 return n*jcdg(n-1); //递归式 } //(板) pubic static int jcLoop(int n){ int T=1;//初始条件 for (i=2;i=n;i++){T=T*i;//递推式 } return T;} 2.1 递归的概念 例2 Fibonacci数列 (板) 无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。递归地定义： 第n个Fibonacci数可递归地计算如下： public static int fibonacci(int n) { if (n = 1) return 1;//结束条件 return fibonacci(n-1)+fibonacci(n-2); //递归式 } pubic static int fibonacciLoop(int n){ f0=1;f1=1;//初始条件 for (i=2;i=n;i++){f2=f0+f1;//递推式，保存中间值 f0=f1;f1=f2;} return f1;} 2.1 递归的概念 例3 Ackerman函数 当一个函数及其变量是由函数自身定义时，称双递归函数。 Ackerman函数A(n，m)定义如右(板) 2.1 递归的概念 A(n，m)的自变量m的每一个值都定义了一个单变量函数： M=0时，A(0,0)=1 A(1,0)=2 A(n,0)=n+2 (通式) 板 M=1时，A(0,1)=1 A(1,1)=A(A(1-1,1),1-1)=A(A(0,1),0)=A(1,0)=2*1 A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，前值上加2，倍增 A(2,1)=A(2-1,1)+2=A(1,1)+2=2*2, A(3,1)=A(3-1,1)+2=A(2,1)+2=2*2+2, 故A(n,1)= n*2板 M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2) A(1,2)=A(A(0,2),1)=A(1,1)=2， A(2,2)=A(A(1,2),1)=A(2,1)=22. A(3,2)=A(A(2,2),1)=A(22,1)=2*22 =23 故A(n,2)= 2n 。板 M=3时，类似的可以推出，M=4增长快，不好表示。 2.1 递归的概念 例4 排列问题 递归算法生成n个元素{r1,r2,…,rn}的全排列。 设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。去掉元素ri。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。 R的全排列可归纳定义如下：板 当n=1时，perm(R)=(r)，r是集合R中唯一的元素； 当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。 2.1 递归的概念 例5 整数划分问