動(dòng)態(tài)規(guī)劃模擬試卷及答案

3/3動(dòng)態(tài)規(guī)劃模擬試卷及答案模擬試卷

——第三章動(dòng)態(tài)規(guī)劃

一、填空題（每小題4分，共20分）

1、動(dòng)態(tài)規(guī)劃算法的基本要素是（）和（）。

2、（）是動(dòng)態(tài)規(guī)劃法的變形。

3、（）是最大子段和問題想二維的推廣。

4、矩陣連乘問題的算法可由（）設(shè)計(jì)實(shí)現(xiàn)。

5、動(dòng)態(tài)規(guī)劃算法中，通常不同子問題的個(gè)數(shù)隨問題大小呈（）增長。

二、簡答題（每小題6分，共30分）

1、寫出設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟。

2、簡述什么是備忘錄方法。

3、簡述備忘錄法與動(dòng)態(tài)規(guī)劃法的異同。

4、簡述動(dòng)態(tài)規(guī)劃算法的基本思想。

5.寫出最長公共子序列問題具有的性質(zhì)。

三、綜合題（每小題25分，共50分）

1、用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最長公共子序列問題。

2、用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)下列問題：設(shè)A和B是兩個(gè)字符串。我們要用最少的字

符操作將字符串A轉(zhuǎn)換為字符串B，這里所說的字符操作包括：

（1）刪除一個(gè)字符；

（2）插入一個(gè)字符；

（3）將一個(gè)字符改為另一個(gè)字符。

將字符串A變換為字符串B所用的最少字符操作數(shù)稱為字符串A到B的編輯距離，記為d（A,B）。試設(shè)計(jì)一個(gè)有效算法，對(duì)任給的兩個(gè)字符串A和B，計(jì)算出它們的編輯距離d（A,B）。

答案

一、填空題

1、最優(yōu)子結(jié)構(gòu)、子問題重疊

2、備忘錄方法

3、最大子矩陣的問題

4、動(dòng)態(tài)規(guī)劃法

5、多項(xiàng)式

二、簡答題

1、（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；

（2）遞歸地定義最優(yōu)解；

（3）以自底向上的方法計(jì)算出最優(yōu)值；

（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。

2、備忘錄方法是動(dòng)態(tài)規(guī)劃算法的變形。備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法

的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。

3、與動(dòng)態(tài)規(guī)劃算法一樣，備忘錄方法用表格保存已解決的子問題的答案，在下

次需要解此子問題時(shí)，只要簡單地查看該子問題的解答，而不必重新計(jì)算。

與動(dòng)態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動(dòng)態(tài)規(guī)劃算法則是自底向上遞歸的。

4、動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

5、最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。

三、綜合題

1、解：用動(dòng)態(tài)規(guī)劃算法求解的算法代碼如下：

intlcs_len(char*a,char*b,intc[][N])

{

intm=strlen(a),n=strlen(b),i,j;

for(i=0;i=c[i][j-1])

c[i][j]=c[i-1][j];

elsec[i][j]=c[i][j-1];

returnc[m][n];

};

char*build_lcs(chars[],char*a,char*b)

{

intk,i=strlen(a),j=strlen(b),c[N][N];

k=lcs_len(a,b,c);

s[k]=’/0’;

while(k>0){

if(c[i][j]==c[i-1][j])i--;

elseif(c[i][j]==c[i][j-1])j--;

else{

s[--k]=a[i-1];

i--,j--;

}

}

returns;

}

2、解：用動(dòng)態(tài)規(guī)劃算法求解的算法代碼如下：

intdist()

{

intm=a,size();

intn=b,size();

vectord(n+1,0);

for(inti=1;i1?d[j-1]:i;

int