算法分析復(fù)習(xí)題

1、一、閱讀以下說明和圖，填補流程圖中的空缺，將解答填入答題紙的對應(yīng)欄內(nèi)。 說明 在一條農(nóng)村公路的一邊稀疏地分布著房子，其分布如下圖所示。某電信公司需要在某些位置放置蜂窩電話基站，由于基站的覆蓋范圍是6公里，因此必須使得每棟房子到某個基站的直線距離不超過 6 公里。為簡化問題，假設(shè)所有房子在同一直線上，并且基站沿該直線放置?，F(xiàn)采用貪心策略實現(xiàn)用盡可能少的基站覆蓋所有的房子。實現(xiàn)貪心算法的流程如下圖所示，請?zhí)畛淦渲锌瞻撞⒂嬎阍撍惴ǖ臅r間復(fù)雜度，其中：1di(1i N)表示第i個房子到公路A端的距離，N表示房子的總數(shù)，房子編號按照房子到公路A端的距離從小到大進行編號。2sk表示第 k（k 1）個基站到

2、公路 A 端的距離，算法結(jié)束后 k 的值為基站的總數(shù)。該算法的時間復(fù)雜度為 （5）。二、閱讀下列說明，回答問題 1 至問題 3，將解答填入答題紙的對應(yīng)欄內(nèi)。 【說明】某餐廳供應(yīng)各種標準的營養(yǎng)套餐。假設(shè)菜單上共有 n 項食物 m1，m2，mn，每項食物 mi的營養(yǎng)價值為 vi，價格為 pi，其中 i=1,2,n，套餐中每項食物至多出現(xiàn)一次?？腿顺Ｐ枰粋€算法來求解總價格不超過 M 的營養(yǎng)價值最大的套餐。【問題 1】下面是用動態(tài)規(guī)劃策略求解該問題的偽代碼，請?zhí)畛淦渲械目杖?1)、(2)和(3)處。偽代碼中的主要變量說明如下：n：總的食物項數(shù)；v：營養(yǎng)價值數(shù)組，下標從 1 到 n，對應(yīng)第 1 到第

3、n 項食物的營養(yǎng)價值；p：價格數(shù)組，下標從 1 到 n，對應(yīng)第 1 到第 n 項食物的價格；M：總價格標準，即套餐的價格不超過 M；x： 解向量（數(shù)組），下標從 1 到 n，其元素值為 0 或 1，其中元素值為 0 表示對應(yīng)的食物不出現(xiàn)在套餐中，元素值為 1 表示對應(yīng)的食物出現(xiàn)在套餐中；nv：n+1 行 M+1 列的二維數(shù)組，其中行和列的下標均從 0 開始，nvij表示由前 i 項食物組合且價格不超過 j 的套餐的最大營養(yǎng)價值。問題最終要求的套餐的最大營養(yǎng)價值為nvnM。偽代碼如下：MaxNutrientValue(n, v, p, M, x) 1 for i = 0 to n2 nvi0 =

4、 03 for j = 1 to M 4 nv0j = 05 for i = 1 to n6 for j = 1 to M 7 if j < pi /若食物 mi不能加入到套餐中8 nvij = nvi - 1j 9 else if （1） 10 nvij = nvi - 1j 11 else 12 nvij = nvi - 1j pi + vi 13 j = M 14 for i = n downto 115 if （2） 16 xi = 0 17 else 18 xi = 119 （3） 20 return x and nvnM 【問題 2】 現(xiàn)有 5 項食物，每項食物的營養(yǎng)價值和價

5、格如表1 所示。表 1 食物營養(yǎng)價值及價格表編 碼營養(yǎng)價值價 格m120050m218030m322545m420025m5505若要求總價格不超過 100 的營養(yǎng)價值最大的套餐，則套餐應(yīng)包含的食物有 （4） （用食物項的編碼表示），對應(yīng)的最大營養(yǎng)價值為（5）?！締栴} 3】 【問題 1】中偽代碼的時間復(fù)雜度為（6）（用 符號表示）。三、算法填空1.背包問題的貪心算法void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;i<=n;i+) xi=0; float c=M; for (

6、i=1;i<=n;i+) if (wi>c) break; xi=1; _; _;2.最大子段和: 動態(tài)規(guī)劃算法int MaxSum(int n, int a) int sum=0, b=0； /sum存儲當前最大的bj, b存儲bj for(int j=1； j<=n； j+) if (b>0) b+= aj ； _； /一旦某個區(qū)段和為負，則從下一個位置累和 if(b>sum) _; return sum； 3.貪心算法求裝載問題template<class Type>void Loading(int x, Type w, Type c, int

7、n) int *t = new int n+1; ; for (int i = 1; i <= n; i+) xi = 0; for (int i = 1; i <= n && wti <= c; i+) xti = 1; ;4.貪心算法求活動安排問題template<class Type>void GreedySelector(int n, Type s, Type f, bool A) _; int j=1; for (int i=2;i<=n;i+) if (si>=fj) _; j=i; else Ai=false; 5.快速排

8、序template<class Type>void QuickSort (Type a, int p, int r) if (p<r) int q=Partition(a,p,r); _; /對左半段排序 _; /對右半段排序 6.排列問題Template <class Type>void perm(Type list, int k, int m ) /產(chǎn)生listk:m的所有排列 if(k=m) /只剩下一個元素 for (int i=0;i<=m;i+) cout<<listi; cout<<endl; else /還有多個元素待排列，遞歸產(chǎn)生排列 for (int i=k; i<=m; i+) sk，listi); perm(list,k+1;m); sk,listi); 四、問答題1.分治法的基本思想是什么？2. 設(shè)計動態(tài)規(guī)劃算法的主要步驟是什么3. 分治法與動態(tài)規(guī)劃法的異同有哪些4. 分支限界法與回溯法的異同有哪些5. 分支限界法的搜索策略什么6. 分治法所能解決的問題一般具有的幾個特征是：7. 用分支限界法設(shè)計算法的步驟是：8. 常見的兩種分支限界法的算法框架9. 回溯法中常見的兩類典型的解空間樹是子集樹和排列樹。 五、算法題