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

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

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

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

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

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

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

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