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

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

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

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

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

[試題4]

閱讀下列說明和C代碼，回答下列問題。

[說明]

用兩臺處理機A和B處理n個作業(yè)。設A和B處理第i個作業(yè)的時間分別為ai和bi。由于各個作業(yè)的特點和機器性能的關系，對某些作業(yè)，在A上處理時間長，而對某些作業(yè)在B上處理時間長。一臺處理機在某個時刻只能處理一個作業(yè)，而且作業(yè)處理是不可中斷的，每個作業(yè)只能被處理一次?，F(xiàn)要找出一個最優(yōu)調(diào)度方案，使得n個作業(yè)被這兩臺處理機處理完畢的時間(所有作業(yè)被處理的時間之和)最少。算法步驟如下。

11確定候選解上界為R短的單臺處理機處理所有作業(yè)的完成時間m，

12用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)(‖表示邏輯或操作)。

13得到最短處理時間為min(max(x,y))。

[C代碼]

下面是該算法的C語言實現(xiàn)。

11常量和變量說明

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：最短處理時間

12C代碼

#include＜stdio.h＞

int  n,  m;

int a[60], b[60], p[100] [100] [60];

void read16 { …… /*輸入n、 a、 b, 求出m, 代碼略*/

void schedule16 {       /*求解過程*/

int  x, y, k;

for (x=0;x＜=m;x++){

for (y=0;y＜m;y++){

______

for (k=1;k＜n;k++)

p[x] [y] [k] =0;

}

}

for (k=1;k＜n;k++){

for (x=0;x＜=m;x++) {

for (y=0;y＜=m;y++){

if(x-a[k-1]＞=0)

______;

if(______)

p[x] [y] [k]=(p[x] [y] [k] ‖ p[x] [y-b[k-1]] [k-1]);

}

}

}

}

void write16 {   /*確定最優(yōu)解并輸出*/

int x, y, temp, max=m;

for (x=0;x＜=m;x++) {

for (y=0,y＜=m;y++){

if(______)

temp______:

if (temp＜max) max = temp;

}

}

}

print ("\n%d\n",max) ;

}

void main16 {

read16 ;

schedule16 ;

write16 ;

}

[問題1]

根據(jù)以上說明和C代碼，填充C代碼中的空缺處。

[問題2]

根據(jù)以上C代碼，算法的時間復雜度為______(用O符號表示)。

[問題3]

考慮6個作業(yè)的實例，各個作業(yè)在兩臺處理機上的處理時間如表2-7所示。該實例的最優(yōu)解為______，最優(yōu)解的值(即最短處理時間)為______。最優(yōu)解用(x1，x2，x3，x4，x5，x6)表示，其中若第i個作業(yè)在A上處理，則xi=1，否則xi=2。如(1，1，1，1，2，2)表示作業(yè)1、2、3和4在A上處理，作業(yè)5和6在B上處理。

表2-7 各個作業(yè)在兩臺處理機上的處理時間