第2章 节 递归与分治策略 计算机算法设计与分析.pptVIP

第2章 递归与分治策略;将要求解的较大规模的问题分割成k个更小规模的子问题。;算法总体思想;算法总体思想;算法总体思想;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;(2) q(n,m)=q(n,n),m?n; 最大加数n1实际上不能大于n。因此，q(1,m)=1。 ;2.1 递归的概念;2.1 递归的概念;;2.1 递归的概念;在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。 ;递归算法的实现;递归算法的实现;递归小结;递归小结;分治法的适用条件;分治法的基本步骤;分治法的复杂性分析;分治法的复杂性分析;二分有哪些信誉好的足球投注网站技术;二分有哪些信誉好的足球投注网站技术;;大整数的乘法;大整数的乘法;Strassen矩阵乘法;Strassen矩阵乘法;Strassen矩阵乘法;Strassen矩阵乘法;棋盘覆盖;棋盘覆盖;棋盘覆盖;合并排序;合并排序;合并排序;快速排序;private static int randomizedPartition (Type a[], int p, int r) { int i = random(p,r); MyMath.swap(a, i, p); return partition (a, p, r); };线性时间选择;线性时间选择;将n个输入元素划分成?n/5?个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共?n/5?个。 递归调用select来找出这?n/5?个元素的中位数。如果?n/5?是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。;private static Comparable select (int p, int r, int k) { if (r-p75) { //用某个简单排序算法对数组a[p:r]排序; bubbleSort(p,r); return a[p+k-1]; } //将a[p+5*i]至a[p+5*i+4]的第3小元素 //与a[p+i]交换位置; //找中位数的中位数，r-p-4即上面所说的n-5 for ( int i = 0; i=(r-p-4)/5; i++ ) { int s=p+5*i, t=s+4; for (int j=0;j3;j++) bubble(s,t-j); MyMath.swap(a, p+i, s+2); } Comparable x = select(p, p+(r-p-4)/5, (r-p+6)/10); int i=partition(p,r,x), j=i-p+1; if (k=j) return select(p,i,k); else return select(i+1,r,k-j); };最接近点对问题;最接近点对问题;最接近点对问题;最接近点对问题;为了确切地知道要检查哪6个点，可以将p和P2中???有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。 因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。;最接近点对问题;;循环赛日程表