軟件設(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/5/19）在線測(cè)試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/5/19

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

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

閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
設(shè)有n個(gè)貨物要裝入若干個(gè)容量為C的集裝箱以便運(yùn)輸，這n個(gè)貨物的體積分別為{S1，S2，．．．，Sn}，且有si≤C(1≤i≤ n)。為節(jié)省運(yùn)輸成本，用盡可能少的集裝箱來裝運(yùn)這n個(gè)貨物。
下面分別采用最先適宜策略和最優(yōu)適宜策略來求解該問題。
最先適宜策略( firstfit)首先將所有的集裝箱初始化為空，對(duì)于所有貨物，按照所給的次序，每次將一個(gè)貨物裝入第一個(gè)能容納它的集裝箱中。
最優(yōu)適宜策略( bestfit)與最先適宜策略類似，不同的是，總是把貨物裝到能容納它且目前剩余容量最小的集裝箱，使得該箱子裝入貨物后閑置空間最小。
【C代碼】
下面是這兩個(gè)算法的C語言核心代碼。
(1)變量說明
n：貨物數(shù)
C：集裝箱容量
s：數(shù)組，長(zhǎng)度為n，其中每個(gè)元素表示貨物的體積，下標(biāo)從0開始
b：數(shù)組，長(zhǎng)度為n，b[i]表示第i+1個(gè)集裝箱當(dāng)前已經(jīng)裝入貨物的體積，下標(biāo)從0開始
i，j：循環(huán)變量
k：所需的集裝箱數(shù)
min:當(dāng)前所用的各集裝箱裝入了第i個(gè)貨物后的最小剩余容量
m:當(dāng)前所需要的集裝箱數(shù)
temp：臨時(shí)變量
(2)函數(shù)firstfit
int firstfit(){
inti，j；
k=0：
for(i=0；ib[i]=0；
}
for（i=0；i(1)；
while(C-b[j]j++;
}
(2)；
k=k>(j+1)?k：(j+1)；
}
returnk；
}
(3)函數(shù)bestfit
int bestfit() {
int i，j，min，m，temp;
k=0；
for（i=0；ib[i]=0；
}
for (i=0；imin=C；
m=k+l；
for(j=0;j< k+l；j++){
temp=C- b[j] - s[i];
if(temp>0&&temp< min){
(3)    ；
m=j，
}
}
(4)；
k=k>(m+1)?k:(m+1)；
}
return k；
}
【問題1】（8分）
根據(jù)【說明】和【C代碼】，填充C代碼中的空(1)～(4)。
【問題2】（4分）
根據(jù)【說明】和【C代碼】，該問題在最先適宜和最優(yōu)適宜策略下分別采用了(5) 和(6)算法設(shè)計(jì)策略，時(shí)間復(fù)雜度分別為 (7) 和 (8)（用O符號(hào)表示）。
【問題3】（3分）
考慮實(shí)例n= 10，C= 10，各個(gè)貨物的體積為{4，2，7，3，5，4，2，3，6，2}。該實(shí)例在最先適宜和最優(yōu)適宜策略下所需的集裝箱數(shù)分別為(9)和(10)。考慮一般的情況，這兩種求解策略能否確保得到最優(yōu)解？(11)  （能或否）
信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/st/3812421463.html

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

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