算法分析與設(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、回溯法的求解目標是找出解空間中滿足約束條件的： （ 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、拉斯維加斯算法的一個顯著特征是它所做的隨機選性決策有可能導致算法： （ 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;/當前解 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)=;當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碼之差的絕對值?？崭衽c空格的距離為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é)果，避免重復運算，從而降低算法復雜度。）從動態(tài)規(guī)劃遞歸式可知，算法的時間復雜度為O（mn），m和n分別是字符串A和B的長度。代碼如下：#include <iostream>#include <cmath>#define MAX 100000 /標識最大的可能整數(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的有效下標是º1len,下標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: