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

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

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

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

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

[試題4]

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

[說明]

用兩臺(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í)間長，而對(duì)某些作業(yè)在B上處理時(shí)間長。一臺(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í)間之和)最少。算法步驟如下。

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

12用p(x,y,k)=1表示前k個(gè)作業(yè)可以在A用時(shí)不超過x且在B用時(shí)不超過y時(shí)間內(nèi)處理完成，則p(x,y,k)=p(x-ak,y,k-1)‖p(x,y-bk,k-1)(‖表示邏輯或操作)。

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

[C代碼]

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

11常量和變量說明

n：作業(yè)數(shù)

m：候選解上界

a：數(shù)組，長度為n，記錄n個(gè)作業(yè)在A上的處理時(shí)間，下標(biāo)從0開始

b：數(shù)組，長度為n，記錄n個(gè)作業(yè)在B上的處理時(shí)間，下標(biāo)從0開始

k：循環(huán)變量

p：三維數(shù)組，長度為(m+1)*(m+1)*(n+1)

temp：臨時(shí)變量

max：最短處理時(shí)間

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代碼，算法的時(shí)間復(fù)雜度為______(用O符號(hào)表示)。

[問題3]

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

表2-7 各個(gè)作業(yè)在兩臺(tái)處理機(jī)上的處理時(shí)間