算法设计与分析典型算法概述——分治法与贪心法

《算法设计与分析典型算法概述——分治法与贪心法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法设计与分析典型算法概述I分治法与贪心法拾光工作室分治法分治算法也叫分治策略，把输入分为若干个部分，递归的解每一个问题，最后将这些子问题合并成为一个全局解。如果子问题较大，可以再次使用分治策略。由此可以得到分治策略解决的问题特点：1.该问题的规模缩小到一定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题；3.分解出的子问题的解可以合并为原问题的解；4.分解出的各个子问题是相互独立的。分治法的应用——二叉查找设a[i](1〈二i〈二n)是一个数组，其中的元素以非降序排列.考虑判断一个元素x是否在数组中的问题。确定一个j,使得a[j]=x。如

2、果x在数组中返回j,否则，返回0。分析该问题符合分治法策略解决问题的特点，可以用分治法解决：如果n=1,直接判断a[n]是否与x相等。如果n〉1,可以把问题分解如下新的问题：选择一个下标q(范围[i,I]中)，比较x与a[q],则有三种情况：1.x:a[q].得到解。2.x>a[q].问题范围转换为(l-q,a[q+1],...,x)3.x〈a[q].问题范围转换为(q-i,a[i],...,x)转换的子问题可以继续分解。二叉查找的递归算法intBinSrch(Typea口，inti,intn，Typex)//a[i__n]是非递减排列且1<=i<=n;{if

3、(n==i){if(x==a[i])returni;elsereturn0;}else{intmid=(i+n)/2;if(x==a[mid])returnmid;elseif(x

4、+){if(a[i]>max)max=a[i];if(a[i]

5、min=a[i];//分解的最小问题elseif(i==j-1){//分解的另一种的最小问题if(a[i]

6、用——归并排序从上面两列子可以看出分治算法设计的关键点在于，如何定义出最小子问题的处理方法，如何分解问题和如何合并子问题的解。我们接着在看一下分治的思想用于排序问题，是如何设计算法的。归并排序思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。//归并排序的递归算法Typea[]，b[];//全局变量voidMergeSort(intleft,intright){if(left

7、(left,mid);MergeSort(mid+1，right);//合并Merge(left,mid,right);//合并到数组b}}//归并排序的合并程序voidMerge(intlow,intmid,inthigh){inth=low，i=low，j=mid+1，k;while((h<=mid)&&(j<=high)){if(a[h]<=a[j]){b[i]=a[h];h++}else{h[i]=aU];j++}i++;}if(h〉mid)for(k=j;k<=high){b[i]=a[k];i++}elsefor(k=h;k<=mid;k++){b

8、[i]=a[k];i++}for(k=