軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2022/8/7）在線測(cè)試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/8/7

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2022/8/7）

閱讀下列說(shuō)明和C代碼，回答問題1至問題3，將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
用兩臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)。設(shè)A和B處理第i個(gè)作業(yè)的時(shí)間分別為ai和bi。由于各個(gè)作業(yè)的特點(diǎn)和機(jī)器性能的關(guān)系，對(duì)某些作業(yè)，在A上處理時(shí)間長(zhǎng)，而對(duì)某些作業(yè)在B上處理時(shí)間長(zhǎng)。一臺(tái)處理機(jī)在某個(gè)時(shí)刻只能處理一個(gè)作業(yè)，而且作業(yè)處理是不可中斷的，每個(gè)作業(yè)只能被處理一次?，F(xiàn)要找出一個(gè)最優(yōu)調(diào)度方案，使得n個(gè)作業(yè)被這兩臺(tái)處理機(jī)處理完畢的時(shí)間（所有作業(yè)被處理的時(shí)間之和）最少。
算法步驟：
（1）確定候選解上界為R短的單臺(tái)處理機(jī)處理所有作業(yè)的完成時(shí)間m，

（2）用p（x，y，k）=1表示前k個(gè)作業(yè)可以在A用時(shí)不超過(guò)x且在B用時(shí)不超過(guò)y時(shí)間  內(nèi)處理完成，則p（x，y，k）=p（x-ak，y，k-1）||p（x，y-bk，k-1）（||表示邏輯或操作）。
（3）得到最短處理時(shí)問為min（max（x，y））。
【C代碼】
下面是該算法的C語(yǔ)言實(shí)現(xiàn)。
（1）常量和變量說(shuō)明
n: 作業(yè)數(shù)
m: 候選解上界
a: 數(shù)組，長(zhǎng)度為n，記錄n個(gè)作業(yè)在A上的處理時(shí)間，下標(biāo)從0開始
b: 數(shù)組，長(zhǎng)度為n，記錄n個(gè)作業(yè)在B上的處理時(shí)間，下標(biāo)從0開始
k: 循環(huán)變量
p: 三維數(shù)組，長(zhǎng)度為（m+1）*（m+1）*（n+1）
temp: 臨時(shí)變量
max: 最短處理時(shí)間
（2）C代碼
#include
int n， m;
int a[60]， b[60]， p[100][100][60];
void read(){ /*輸入n、a、b，求出m，代碼略*/}
void schedule(){ /*求解過(guò)程*/
int x，y，k;
for（x=0；x<=m；x++）{
for(y=0；y（1）
for（k=1；kp[x][y][k]=0；
}
}
for（k=1；kfor（x=0；x<=m；x++）{
for（y=0；y<=m；y++）{
if（x - a[k-1]>=0）    （2）    ；
if（ （3） ）p[x][y][k]=(p[x][y][k] ||p[x][y-b[k-1]][k-1]);
}
}
}
}
void write(){    /*確定最優(yōu)解并輸出*/
int x，y，temp，max=m;
for（x=0；x<=m；x++）{
for（y=0;y<=m;y++）{
if(  （4）  ）{
temp=（5） ；
if（temp< max）max = temp;
}
}
}
printf(“\n%d\n”，max），
}
void main(){read();schedule();write();}
【問題1】 （9分）
根據(jù)以上說(shuō)明和C代碼，填充C代碼中的空（1）～（5）。
【問題2】（2分）
根據(jù)以上C代碼，算法的時(shí)間復(fù)雜度為（6）（用O符號(hào)表示）。
【問題3】（4分）
考慮6個(gè)作業(yè)的實(shí)例，各個(gè)作業(yè)在兩臺(tái)處理機(jī)上的處理時(shí)間如表4-1所示。該實(shí)例的最優(yōu)解為（7），最優(yōu)解的值（即最短處理時(shí)間）為（8）。最優(yōu)解用（x1，x2，x3，x4，x5，x6）表示，其中若第i個(gè)作業(yè)在A上處理，則xi=l，否則xi=2。如（1，1，1，1，2，2）表示作業(yè)1，2，3和4在A上處理，作業(yè)5和6在B上處理

表4-1

	作業(yè)1	作業(yè)2	作業(yè)3	作業(yè)4	作業(yè)5	作業(yè)6
處理機(jī)A	2	5	7	10	5	2
處理機(jī)B	3	8	4	11	3	4

信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/st/3811810850.html

信管網(wǎng)考友試題答案分享：

信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/st/3811810850.html