普考申論題
112年
[資訊處理] 程式設計概要
第 一 題
📖 題組：
超商預計發展合併集點卡程式，說明如下。若有 n 張集點卡要合併，但只能兩張兩張合併，因此共需合併 n-1 次才能把點數全部集中到一張卡。2 張合併時會扣掉較少點數那張的 1/10 點數（無條件進位至整數）做為手續費。例如，若有 A, B, C 3 張集點卡要合併，且點數分別為 25, 30, 51 點。若先合併 A, B，再合併 C，則會扣掉 3+6 點，因此合併後剩 97 點，這也剛好是最差合併策略下的合併總點數；但在最佳的合併策略下（先合併 B, C，再合併 A），則可有 100 點。（每小題 15 分，共 30 分） (一)請寫 best_case() 函式，計算 n 張集點卡合併過後最多可有多少點數。 (二)請寫 worst_case() 函式，計算 n 張集點卡合併過後最少可有多少點數。 #include
int a[101], n; // 最多可有 100 張集點卡要合併，實際上要合併 n 張卡
int best_case () {
...
}
int worst_case () {
...
}
int main () {
scanf ("%d", &n);
for (i=0; i
超商預計發展合併集點卡程式，說明如下。若有 n 張集點卡要合併，但只能兩張兩張合併，因此共需合併 n-1 次才能把點數全部集中到一張卡。2 張合併時會扣掉較少點數那張的 1/10 點數（無條件進位至整數）做為手續費。例如，若有 A, B, C 3 張集點卡要合併，且點數分別為 25, 30, 51 點。若先合併 A, B，再合併 C，則會扣掉 3+6 點，因此合併後剩 97 點，這也剛好是最差合併策略下的合併總點數；但在最佳的合併策略下（先合併 B, C，再合併 A），則可有 100 點。（每小題 15 分，共 30 分） (一)請寫 best_case() 函式，計算 n 張集點卡合併過後最多可有多少點數。 (二)請寫 worst_case() 函式，計算 n 張集點卡合併過後最少可有多少點數。 #include
📝 此題為申論題，共 2 小題
小題 (一)
請寫 best_case() 函式，計算 n 張集點卡合併過後最多可有多少點數。
思路引導 VIP
面對這類求極值（最多/最少）的合併問題，應優先思考『貪心演算法 (Greedy Algorithm)』。要讓最終點數最多，等於要讓『被扣除的手續費總和最小』；因此應讓陣列中『最大』的數字作為主體，依序去合併其他較小的數字，確保每次計算 1/10 手續費的基底都是原始較小的數值，而不會是合併後膨脹的大數字。
小題 (二)
請寫 worst_case() 函式，計算 n 張集點卡合併過後最少可有多少點數。
思路引導 VIP
為求最終剩餘點數最少（最差情況），應使每次扣除的手續費最大化。採用貪婪演算法，每次挑選當前點數「最小的兩張」進行合併。同時注意必須複製全域陣列建立副本來操作，以免影響另一個函式的計算。