閱讀下列說(shuō)明和C代碼，回答問(wèn)題1和問(wèn)題2，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

某公司購(gòu)買(mǎi)長(zhǎng)鋼條，將其切割后進(jìn)行出售。切割鋼條的成本可以忽略不計(jì)，鋼條的長(zhǎng)度為整英寸。已知價(jià)格表P，其中中P_i(i=1，2，...，m)表示長(zhǎng)度為i英寸的鋼條的價(jià)格。現(xiàn)要求解使銷(xiāo)售收益最大的切割方案。

求解此切割方案的算法基本思想如下：

假設(shè)長(zhǎng)鋼條的長(zhǎng)度為n英寸，最佳切割方案的最左邊切割段長(zhǎng)度為i英寸，則繼續(xù)求解剩余長(zhǎng)度為n-i英寸鋼條的最佳切割方案?？紤]所有可能的i，得到的最大收益rn對(duì)應(yīng)的切割方案即為最佳切割方案。rn的遞歸定義如下：

r_n=max_1≤i≤n(p_i+r_n-i)對(duì)此遞歸式，給出自頂向下和自底向上兩種實(shí)現(xiàn)方式

【C代碼】

/*常量和變量說(shuō)明

n：長(zhǎng)鋼條的長(zhǎng)度

P[]：價(jià)格數(shù)組

*/

#defineLEN100

intTop_Down_Cut_Rod(intP[]，intn){/*自頂向下*/Intr=0

Inti;if(n=0){

retum0;

}

for(i=1;(1);i++){

inttmp=p[i]+Top_Down_Cut_Rod(p，n-i)r=(r>=tmp)?r：tmp;

}

returnr;

}

intBottom_Up_Cut_Road(intp[],intn){/*自底向上*/

intr[LEN]={0};

inttemp=0;

inti,j;

for(j=1;j<=n;j++){

temp=0;

for(i=l;(2);i++){

temp=(3);

}

(4)

}

returnr[n];

}

【問(wèn)題1】(8分)

根據(jù)說(shuō)明，填充C代碼中的空(1)～(4)。

【問(wèn)題2】(7分)

根據(jù)說(shuō)明和C代碼，算法采用的設(shè)計(jì)練略為(5)。

求解時(shí)，自頂向下方法的時(shí)間復(fù)雜度為(6);自底向上方法的時(shí)間復(fù)雜度為(7)

(用O表示)。

信管網(wǎng)參考答案：

【問(wèn)題1】

(1)：i<=n

(2)：i<=j

(3)：temp=(temp>=r[i]+r[j-i])?temp:(r[i]+r[j-i])

(4)：r[j]=(temp>p[j])?temp:p[j];

【問(wèn)題2】

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

(6)O(2ⁿ)

(7)O(n²)

查看解析：www.ichunya.com/st/396349820.html

相關(guān)推薦：

點(diǎn)擊查看/下載：軟件設(shè)計(jì)師歷年真題匯總

點(diǎn)擊查看：軟件設(shè)計(jì)師在線(xiàn)培訓(xùn)課程 丨 免費(fèi)試聽(tīng)課程

免費(fèi)練習(xí)：軟件設(shè)計(jì)師考試題庫(kù)(模擬試題、章節(jié)練習(xí)、每日一練)