算法設計與分析典型算法概述——分治法與貪心法

《算法設計與分析典型算法概述——分治法與貪心法》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

1、算法設計與分析典型算法概述I分治法與貪心法拾光工作室分治法分治算法也叫分治策略，把輸入分為若干個部分，遞歸的解每一個問題，最后將這些子問題合并成為一個全局解。如果子問題較大，可以再次使用分治策略。由此可以得到分治策略解決的問題特點：1.該問題的規(guī)?？s小到一定的程度就可以容易地解決；2.該問題可以分解為若干個規(guī)模較小的相同問題；3.分解出的子問題的解可以合并為原問題的解；4.分解出的各個子問題是相互獨立的。分治法的應用——二叉查找設a[i](1〈二i〈二n)是一個數(shù)組，其中的元素以非降序排列.考慮判斷一個元素x是否在數(shù)組中的問題。確定一個j,使得a[j]=x。如

2、果x在數(shù)組中返回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)轉換的子問題可以繼續(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);//合并到數(shù)組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=