基本的算法策略(編輯修改稿)
2025-02-01 18:29 本頁面
【文章內容簡介】 問題分解成的子問題個數(shù)一般是固定的 ， 每個子問題的規(guī)模也是平均分配的 。 當每次都將問題分解為原問題規(guī)模的一半時 ， 稱為二分法 。 二分法是分治法較常用的分解策略 ， 數(shù)據(jù)結構課程中的折半查找 、 歸并排序等算法都是采用此策略實現(xiàn)的 。 分治法的一般的算法設計模式如下： DivideandConquer(int n) /n為問題規(guī)模 / { if （ n≤n0 ） /n0 為可解子問題的規(guī)模 / { 解子問題； return(子問題的解 )； } for （ i=1 。i=k。i++） /分解為較小子問題p1,p2,……pk/ yi=DivideandConquer(|Pi|)。 /遞歸解決 Pi/ T =MERGE(y1,y2,...,yk)。 /合并子問題 / return(T)。 } 【例 1】金塊問題： 老板有一袋金塊 (共 n塊 )，最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設有一臺比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。 ? 算法設計 1： 比較簡單的方法是逐個的進行比較查找。先拿兩塊比較重量，留下重的一個與下一塊比較，直到全部比較完畢，就找到了最重的金子。算法類似于一趟選擇排序， 算法如下： maxmin( float a[],int n) { max==min=a[1]。 for(i=2。 i=n 。i++ ) if(max a[i]) max=a[i]。 else if(min a[i]) min=a[i]。 } 算法分析 1： 算法中需要 n1次比較得到 max。最好的情況是金塊是由小到大取出的，不需要進行與 min的比較，共進行 n1次比較。最壞的情況是金塊是由大到小取出的，需要再經(jīng)過 n1次比較得到 min 算法設計 2: 在含 n（ n是 2的冪（ n=2））個元素的集合中尋找極大元和極小元。用分治法（二分法）： 1） 將數(shù)據(jù)等分為兩組（兩組數(shù)據(jù)可能差 1）， 2） 遞歸分解直到每組元素的個數(shù) ≤2，可簡單地找 到最大（?。┲?。 3） 回溯時將分解的兩組解大者取大，小者取小， 合并為當前問題的解。 算法 2 遞歸求取最大和最小元素 float a[n]。 maxmin （ int i, int j ,float fmax, float fmin）{int mid。 float lmax, lmin, rmax, rmin。 if (i=j) {fmax= a[i]。 fmin=a[i]。} else if (i=j1) if(a[i]a[j]) { fmax=a[j]； fmin=a[i]。} else {fmax=a[i]。 fmin=a[j]。} else {mid=(i+j)/2。 maxmin （ i， mid， lmax， lmin） 。 maxmin （ mid+1， j， rmax， rmin） 。 if(lmaxrmax) fmax=lmax。 else fmax=rmax。 if(lminrmin) fmin=rmin。 else fmin=lmin
教學課件相關推薦
鄂ICP備17016276號-1