軟件設計師案例分析當天每日一練試題地址：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4

往期軟件設計師每日一練試題匯總：www.xomuzic.com/class/27/e4_1.html

軟件設計師案例分析每日一練試題（2024/7/25）在線測試：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4&day=2024/7/25

點擊查看：更多軟件設計師習題與指導

軟件設計師案例分析每日一練試題內(nèi)容（2024/7/25）

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

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

信管網(wǎng)試題答案與解析：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4&day=2024/7/25

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

信管網(wǎng)試題答案與解析：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4&day=2024/7/25