分治法ppt课件

1、分治法acm学习小组新生入门指导教程tot-谭俊概序 经过两周的对c语言的复习，大家对语言应该要很熟练了，接下来就正式进入学习算法了。大家要做好准备额，算法学习的过程是很辛苦很累的，大家一定要好好坚持下去。 关于算法的学习，大家首先要深刻的理解算法思想。 其次，熟记这些经典问题的解法，对常用的算法大家一定要牢牢掌握并且已达到不用参看资料也能写出正确的代码。 最后，针对每一个算法的做好每一个算法的专题练习，并且多做练习，这样才能透过问题表面而联系到自己掌握的算法。 概序 *acm竞赛中常用的算法 分治算法 贪心算法 动态规划 搜索算法 回溯算法 分支界限算法 图算法 网络流 . . 这些都是最基

2、本的算法，比赛不仅仅局限于此，更多的是综合的考验。分治算法 学习目的：掌握分治算法思想 学习要求：熟练运用分治算法思想解决以下问题 1.二叉查找算法 2.查找最大最小值 3.归并排序 4.快速排序 5.选择第k小元素 6.大整数乘法 完成时间：11月16日-11月21日 分治算法简介 分治算法也叫分治策略，把输入分为若干个部分，递归的解每一个问题，最后将这些子问题合并成为一个全局解。如果子问题较大，可以再次使用分治策略。 由此可以得到分治策略解决的问题特点： 1.该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决； 2.该问题可以分解为若干个规模较小的相

3、同问题该问题可以分解为若干个规模较小的相同问题; 3.分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解； 4.分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。 大家已经看到划分出的自问题与原问题是一样的，那么我大家已经看到划分出的自问题与原问题是一样的，那么我们设计算法的时候也就可以利用递归的编程技巧了！们设计算法的时候也就可以利用递归的编程技巧了！ 分治算法的应用 二叉查找 设ai（1=i1,可以把问题分解如下新的问题：选择一个下标q(范围i,l中)，比较x与aq，则有三种情况： 1.x=aq.得到解。 2.xaq.问题范围转换为(l-q,aq+

4、1,.,x) 3.xaq.问题范围转换为(q-i,ai,.,x) 转换的子问题可以继续用同分解二叉查找 二叉查找的递归算法 int binsrch(type a,int i,int n,type x)/ai.n是非递减排列 且 1=i=n; if(n=i) if(x=ai) return i; else return 0; else int mid=(i+n)/2; if(x=amid) return mid; else if(xamid) return binsrh(a,mid+1,n,x); 二叉查找把以下14个数按二叉查找算法分析每个元素比较次数a: 1 2 3 4 5 6 7 8 9

5、10 11 12 13 14元素：-15 -6 0 7 9 23 54 82 101 112 125 131 142 151比较：3 4 2 4 3 4 1 4 3 4 2 4 3 4可以看到没有一个元素的比较要超过4次，平均性能比我们直接扫描整个数组要高很多。可以分析出二叉查找的算法时间复杂度最坏为o(logn).任务1： 写出二叉查找的迭代版本，并比较二者的运行时间。查找最大最小值 在n个元素中找出最大值和最小值。 首先看下简单的查找算法： void maxmin(type a,int n,type &max,type &min) max=min =a0; for(int i=1;imax

6、) max=ai; if(ai2时，可以将an 分为(a0.an/2)和(an/2+1.an)两个子问题，递归的调用分治法求解，最后在合并最大最小值。查找最大最小值递归程序void maxmin(int i,int j,type &max,type &min) if(i=j) max=min=ai;/分解的最小问题 else if(i=j-1)/分解的另一种的最小问题 if(aiaj) max=aj;min=ai; elsemax=ai;min=aj; else int mid=(i+j)/2; type max1,min1; /分解成子问题 maxmin(i,mid,max,min); ma

7、xmin(mid+1,j,max1,min1); / 合并子问题的解 if(maxmax1) max=max1; if(minmin1) min=min1; 调用方式 maxmin(1,n,max,min);/数组从1开始归并排序 从上面两列子可以看出分治算法设计的关键点在于，如何定义出最小子问题的处理方法，如何分解问题和如何合并子问题的解。 我们接着在看一下分治的思想用于排序问题，是如何设计算法的。 归并排序思想： 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 归并排序的递归程序type a,b；/全局变量void m

8、ergesort(int left, int right) if (leftright) /至少有2个元素 int mid=(left+right)/2; /取中点 /分解 mergesort(left, mid); mergesort( mid+1, right); /合并 merge( left, mid, right); /合并到数组b 归并排序的合并程序void merge(int low,int mid,int high) int h=low,i=low,j=mid+1,k; while(h=mid)&(j=high) if(ahmid) for(k=j;k=high)bi=ak;i

9、+ else for(k=h;k=mid;k+)bi=ak;i+ for(k=low;k=high;k+) ak=bk;任务2：hdoj 2665(需要用到线段树) 分治法还可以用来得到一种不同于归并排序的有效排序算法。在归并排序中，文件an在中间分为子数组，各自独立排序，然后归并。 在快速排序中，把文件分为两个子数组，其排序后的子数组不需要归并。 1.完成这个排序过程是通过某个m(0=m=n-1)，重新排列an中的元素，使得0和m之间的所有i和在m+1和n之间的所有j，都有ai=aj.这样a0:m和am+1:n-1中的元素就可以独立排序，不再需要归并。 2.元素的重新排列其他的元素，以至于所

10、有a0:n中在t之前出现的元素都会在小于或等于t，所有在t之后出现的元素都会大于或等于t。这种重新排列称为划分。 int partition (type a, int m, int r) int i = m, j = r+1; /考虑这里为什么+1？ type x=am; / 将 x的元素交换到右边区域 while (true) while (a+i x); if (i = j) break; /退出循环 swap(ai, aj);/交换两个元素 am = aj; aj = x; return j;快速排序void quicksort (type a, int p, int r) if (pr

11、) int q=partition(a,p,r); quicksort (a,p,q-1); /对左半段排序 quicksort (a,q+1,r); /对右半段排序 （仔细体会其中分治策略，和递归技巧的使用，大家还需参考数据结构（c语言版）学习这两个排序）任务3：掌握快速排序算法并实现，自己上网查阅资料并学习“随机快速排序”第k小元素 给定n个元素的an,找出第k最小的元素。这里利用上节的划分算法能够很好的解决。 如果划分元素v是aj,这个j-1个元素小于或等于aj,n-j个元素大于或等于aj。 如果kj,第k最小元素就在aj+1:n中的第k-j最小元素。 这样我们可以设计出一种第k小元素，

12、如下：int select(type a,int n,int k)/数组a元素从0开始，n为元素的个数/partition()见上节算法 int low=-1,up=n-1;/请大家思考为什么low=-1，up=n-1 /如果a下标是从1开始的将会有怎样的变化 do int j=partition(a,low,up); if(k=j) return j;/找到 则结束 else if(kj) up=j; else low=j+1; while(1); 查找第k最小的元素查找第k最小的元素 这个算法的平均计算时间为o(n),最坏为o（n2）。 下面有一种简单的选择算法当选择的k接近1或n是速度很快。但在最坏的情况下为o（n2），平均情况也为o（n2）。 void select(type a,int n,int k) int i,j,q; if(k=n/2) for(i=1;i=k;i+) q=i;type min=ai; for(j=i+1;j=n;j+) if(aj=k;i-) q=i;type max=ai; for(j=(i-1);j=1;j-) if(ajmax) q=j;max=aj; swap(aq,ai); 大整数乘法 这个就作为一个研究性学习的任务发布给大家，对于位数非