算法分析與設(shè)計作業(yè)(一)及參考答案

1、算法分析與設(shè)計作業(yè)（一）本課程作業(yè)由兩部分組成。第一部分為“客觀題部分”，由15個選擇題組成，每題1分，共15分。第二部分為“主觀題部分”，由簡答題和論述題組成，共15分。作業(yè)總分30分，將作為平時成績記入課程總成績?？陀^題部分：一、 選擇題（每題1分，共15題）1、遞歸算法： （ C ） A、直接調(diào)用自身 B、間接調(diào)用自身 C、直接或間接調(diào)用自身 D、不調(diào)用自身2、分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的字問題，這些子問題： （ D ）A、相互獨立 B、與原問題相同 C、相互依賴 D、相互獨立且與原問題相同 3、備忘錄方法的遞歸方式是： （ C ）A、自頂向下 B、自底向上

2、 C、和動態(tài)規(guī)劃算法相同 D、非遞歸的4、回溯法的求解目標(biāo)是找出解空間中滿足約束條件的： （ A ） A、所有解 B、一些解 C、極大解 D、極小解 5、貪心算法和動態(tài)規(guī)劃算法共有特點是： （ A ）A、最優(yōu)子結(jié)構(gòu) B、重疊子問題 C、貪心選擇 D、形函數(shù) 6、哈夫曼編碼是： （ B） A、定長編碼 B、變長編碼 C、隨機編碼 D、定長或變長編碼 7、多機調(diào)度的貪心策略是： （ A）A、最長處理時間作業(yè)優(yōu)先 B、最短處理時間作業(yè)優(yōu)先 C、隨機調(diào)度 D、最優(yōu)調(diào)度8、程序可以不滿足如下性質(zhì)： （ D ） A、零個或多個外部輸入 B、至少一個輸出 C、指令的確定性 D、指令的有限性9、用分治法設(shè)計出

3、的程序一般是： （ A ）A、遞歸算法 B、動態(tài)規(guī)劃算法 C、貪心算法 D、回溯法10、采用動態(tài)規(guī)劃算法分解得到的子問題： （ C ）A、相互獨立 B、與原問題相同 C、相互依賴 D、相互獨立且與原問題相同 11、回溯法搜索解空間的方法是： （ A ） A、深度優(yōu)先 B、廣度優(yōu)先 C、最小耗費優(yōu)先 D、隨機搜索 12、拉斯維加斯算法的一個顯著特征是它所做的隨機選性決策有可能導(dǎo)致算法： （ C ）A、所需時間變化 B、一定找到解 C、找不到所需的解 D、性能變差 13、貪心算法能得到： （ C ） A、全局最優(yōu)解 B、0-1背包問題的解 C、背包問題的解 D、無解 14、能求解單源最短路徑問題的

4、算法是： （ A ）A、分支限界法 B、動態(tài)規(guī)劃 C、線形規(guī)劃 D、蒙特卡羅算法15、快速排序算法和線性時間選擇算法的隨機化版本是： （ A ） A、舍伍德算法 B、蒙特卡羅算法 C、拉斯維加斯算法 D、數(shù)值隨機化算法主觀題部分：二、 寫出下列程序的答案（每題2.5分，共2題） 1、請寫出批處理作業(yè)調(diào)度的回溯算法。#include<iostream>#include<algorithm>using namespace std; class Flowingfriend int Flow(int * ,int ,int );private: /int Bound(int i

5、); void Backtrack(int t); int *M;/ int *x;/當(dāng)前解 int *bestx;/ int *f2;/ int f1;/ int f;/ int bestf;/ int n;/ ;void Flowing:Backtrack(int i)if(i>n)for(int j=1;j<=n;j+)bestxj=xj;bestf=f;elsefor(int j=i;j<=n;j+)f1+=Mxj1;f2i=(f2i-1>f1)?f2i-1:f1)+Mxj2;f+=f2i;if(f<bestf)swap(xi,xj);Backtrack(

6、i+1);swap(xi,xj);f1-=Mxj1;f-=f2i;int Flow(int * M,int n,int bestx)int ub=INT_MAX;Flowing X;X.x=new intn+1;X.f2=new intn+1;X.M=M;X.n=n;X.bestx=bestx;X.bestf=ub;X.f1=0;X.f=0;for(int i=0;i<=n;i+)X.f2i=0,X.xi=i;X.Backtrack(1);delete X.x;delete X.f2;return X.bestf;void main()int *M;int n;int *bestx;co

7、ut<<"請輸入作業(yè)數(shù):"cin>>n;M=new int *n+1;cout<<"請輸入各作業(yè)處理時間:"<<endl;for(int i=1;i<=n;i+)Mi=new int2;for(int k=1;k<=n;k+)for(int j=1;j<3;j+)cin>>Mkj;bestx=new intn+1;for(i=1;i<=n;i+)bestxi=0;cout<<"最優(yōu)完成時間:"<<Flow(M,n,bestx)&

8、lt;<endl;cout<<"最優(yōu)方案:"for(i=1;i<=n;i+)cout<<"作業(yè)"<<bestxi<<" "cout<<endl;2、函數(shù)漸進階對于下列各組函數(shù)f(n)和g(n)，確定f(n)=O(g(n)或f(n)= 或f(n)=，并簡述理由。(1) f(n)=logn2; g(n)=logn+5;f(n)與g(n)同階，f(n)= (2) f(n)=logn2; g(n)=;當(dāng)n>=8時，f(n)<=g(n)，故f(n)=O(g(n)

9、分析：此類題目不易直接看出階的高低，可用幾個數(shù)字代入觀察結(jié)果。 如依次用n=1, 21, 22, 23, 26, 28, 210 (3) f(n)=n; g(n)=log2n;f(n)= (4) f(n)=nlogn+n; g(n)=logn;f(n)= (5) f(n)=10; g(n)=log10;f(n)=(6) f(n)= log2n; g(n)=logn;f(n)= (7) f(n)=2n; g(n)=100n2;f(n)= (8) f(n) =2n; g(n)=3n;f(n)=O(g(n)三、寫出下列題目的程序（每題5分，共2題）1、請寫出背包問題的貪心算法。procedure G

10、REEDY-KNAPSACK(P，W，M，X，n) X0 /將解向量初始化為零/ cuM /cu是背包剩余容量/ for i1 to n do if W(i) cu then exit endif X(i) 1 ； cu cu-W(i) ； repeat ； if in then X(i) cu/ W(i) ； endif end GREEDY-KNAPSACK 2、字符串比較問題問題描述：對于長度相同的2個字符串A和B，其距離定義為相應(yīng)位置字符距離之和。2個非空格字符的距離是它們的ASCII碼之差的絕對值。空格與空格的距離為0，空格與其它字符的距離為一定值k。在一般情況下，字符串A和B的長度

11、不一定相同。字符串A的擴展是在A中插入若干空格字符所產(chǎn)生的字符串。在字符串A和B的所有長度相同的擴展中，有一對距離最小的擴展，該距離稱為字符串A和B的擴展距離。對于給定的字符串A和B，試設(shè)計一個算法，計算其擴展距離。編程任務(wù)：對于給定的字符串A和B，編程計算其擴展距離。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第1行是字符串A，第2行是字符串B，第3行是空格與其它字符的距離定值k。結(jié)果輸出：將計算出的字符串A和B的擴展距離輸出到文件output.txt。 輸入文件示例 輸出文件示例 input.txt output.txt cmc 10 snmn 2解答：設(shè)字符串A和B的字串A1.i和B

12、1.j的擴展距離是val(i, j)；依題意，字符串A和B有三種可能的情況：1）A串最后一個字符是空格，B串最后一個字符是字母，則val(i, j) = val(i-1, j) + k；2）A串最后一個字符時字母，B串最后一個字符時空格，則val(i, j) = val(i, j-1) + k；3）A串和B串最后一個字符均是字母，則val(i, j) = val(i-1, j-1) + dist(ai , bi)；由上可知，val(i, j)具有最優(yōu)子結(jié)構(gòu)性質(zhì)，且滿足如下遞推式：val(i, j) = min val(i-1, j) + k，val(i, j) + k，val(i-1, j-1

13、) + dist(ai , bi) （使用動態(tài)規(guī)劃算法，自底向上的計算各個子問題并利用每次計算的結(jié)果，避免重復(fù)運算，從而降低算法復(fù)雜度。）從動態(tài)規(guī)劃遞歸式可知，算法的時間復(fù)雜度為O（mn），m和n分別是字符串A和B的長度。代碼如下：#include <iostream>#include <cmath>#define MAX 100000 /標(biāo)識最大的可能整數(shù)int val300300; std:string stra; /字符串A std:string strb; /字符串B int k; /定值k /返回字符a與b的ASCII碼的差的絕對值int dist(char

14、a, char b) return abs(a-b); int comp() int len1, len2; int tmp; val00 = 0; len1 = stra.length(); len2 = strb.length(); for(int i=0; i<=len1; i+) /字符串A和B的有效下標(biāo)是º1len,下標(biāo)0表示空字符串 /i或j是0表示A或B串為空串 for(int j=0; j<=len2; j+) if(i+j)/i和j至少一個大于0 valij = MAX; tmp = vali-1j + k; if(i && (tmp<valij)/i大于0 valij = tmp; tmp = valij-1+k; if(j && (tmp<valij)/j大于0 valij = tmp; tmp = vali-1j-1 + dist(strai, strbj); if(i*j) && (tmp<valij) /i和j至少有一個不為0 valij = tmp; return vallen1len2;int main() std: