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

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

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

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

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

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

6、AX;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;coutn;M=new int *n+1;cout請(qǐng)輸入各作業(yè)處理時(shí)間:endl;for(int i=1;i=n;i+)Mi=new int2;for(int k=1;

7、k=n;k+)for(int j=1;jMkj;bestx=new intn+1;for(i=1;i=n;i+)bestxi=0;cout最優(yōu)完成時(shí)間:Flow(M,n,bestx)endl;cout最優(yōu)方案:;for(i=1;i=n;i+)cout作業(yè)bestxi ;cout=8時(shí)，f(n)=g(n)，故f(n)=O(g(n)分析：此類(lèi)題目不易直接看出階的高低，可用幾個(gè)數(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

8、)=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)三、寫(xiě)出下列題目的程序（每題5分，共2題）1、請(qǐng)寫(xiě)出背包問(wèn)題的貪心算法。procedure GREEDY-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

9、 then X(i) cu/ W(i) ； endif end GREEDY-KNAPSACK 2、字符串比較問(wèn)題問(wèn)題描述：對(duì)于長(zhǎng)度相同的2個(gè)字符串A和B，其距離定義為相應(yīng)位置字符距離之和。2個(gè)非空格字符的距離是它們的ASCII碼之差的絕對(duì)值?？崭衽c空格的距離為0，空格與其它字符的距離為一定值k。在一般情況下，字符串A和B的長(zhǎng)度不一定相同。字符串A的擴(kuò)展是在A中插入若干空格字符所產(chǎn)生的字符串。在字符串A和B的所有長(zhǎng)度相同的擴(kuò)展中，有一對(duì)距離最小的擴(kuò)展，該距離稱為字符串A和B的擴(kuò)展距離。對(duì)于給定的字符串A和B，試設(shè)計(jì)一個(gè)算法，計(jì)算其擴(kuò)展距離。編程任務(wù)：對(duì)于給定的字符串A和B，編程計(jì)算其擴(kuò)展距離。

10、數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第1行是字符串A，第2行是字符串B，第3行是空格與其它字符的距離定值k。結(jié)果輸出：將計(jì)算出的字符串A和B的擴(kuò)展距離輸出到文件output.txt。 輸入文件示例 輸出文件示例 input.txt output.txt cmc 10 snmn 2解答：設(shè)字符串A和B的字串A1.i和B1.j的擴(kuò)展距離是val(i, j)；依題意，字符串A和B有三種可能的情況：1）A串最后一個(gè)字符是空格，B串最后一個(gè)字符是字母，則val(i, j) = val(i-1, j) + k；2）A串最后一個(gè)字符時(shí)字母，B串最后一個(gè)字符時(shí)空格，則val(i, j) = val

11、(i, j-1) + k；3）A串和B串最后一個(gè)字符均是字母，則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) + dist(ai , bi) （使用動(dòng)態(tài)規(guī)劃算法，自底向上的計(jì)算各個(gè)子問(wèn)題并利用每次計(jì)算的結(jié)果，避免重復(fù)運(yùn)算，從而降低算法復(fù)雜度。）從動(dòng)態(tài)規(guī)劃遞歸式可知，算法的時(shí)間復(fù)雜度為O（mn），m和n分別是字符串A和B的長(zhǎng)度。代碼如下：#include #include #

12、define MAX 100000 /標(biāo)識(shí)最大的可能整數(shù)int val300300; std:string stra; /字符串A std:string strb; /字符串B int k; /定值k /返回字符a與b的ASCII碼的差的絕對(duì)值int dist(char 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至少一個(gè)大于0 valij = MAX; tmp = vali-1j + k; if(i & (tmpvalij)/i大于0 valij = tmp; tmp = valij-1+k; if(j & (tmpvalij)/j大于0 valij = tmp; tm