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

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

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

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

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

[試題4]

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

[說明]

設有n個貨物要裝入若干個容量為C的集裝箱以便運輸，這n個貨物的體積分別為{s₁，s₂，...，s_n}，且有s₁≤c(1≤i≤n)。為節(jié)省運輸成本，用盡可能少的集裝箱來裝運這n個貨物。

下面分別采用最先適宜策略和最優(yōu)適宜策略來求解該問題。

最先適宜策略(firstfit)首先將所有的集裝箱初始化為空，對于所有貨物，按照所給的次序，每次將一個貨物裝入第一個能容納它的集裝箱中。

最優(yōu)適宜策略(bestfit)與最先適宜策略類似，不同的是，總是把貨物裝到能容納它且目前剩余容量最小的集裝箱，使得該箱子裝入貨物后閑置空間最小。

[C代碼]

下面是這兩個算法的C語言核心代碼。

11變量說明

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：臨時變量

12函數(shù)firstfit

int firstfit13 {

int i, j;

k=0;

for(i=0; i＜n;i++){

b[i]=0;

}

for i=0; i＜n;i++) {

______;

while (C-b [j]＜s [i]){

j++;

}

______;

k=k＞(j+1)?k: (j+1);

}

return k;

}

14函數(shù)bestfit

int bestfit13 {

int i, j ,min, m, temp;

k=0;

for (i=0; i＜n;i++) {

b[i]=0;

}

for (i=0; i＜n;i++) {

min=C;

m=k+1;

for (j=0; j＜k+1;j++) {

temp=C-b [j]-s [i];

if(temp＞0 && temp＜min){

______;

m=j;

}

}

______;

k=k＞(m+1)?k: (m+1);

}

return k;

}

[問題1]

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

[問題2]

根據(jù)[說明]和[C代碼]，該問題在最先適宜和最優(yōu)適宜策略下分別采用了______和______算法設計策略，時間復雜度分別為______和______(用O符號表示)。

[問題3]

考慮實例n=10，C=10，各個貨物的體積為{4，2，7，3，5，4，2，3，6，2}。該實例在最先適宜和最優(yōu)適宜策略下所需的集裝箱數(shù)分別為______和______?？紤]一般的情況，這兩種求解策略能否確保得到最優(yōu)解?______(能或否)。