110 高普考高考三級 資訊處理 資料結構 考古題詳解

核心觀念

本題考「矩陣鏈乘法」（Matrix-Chain Multiplication）。矩陣乘法具有結合律，因此 $A\times B\times C\times D\times E$ 可以有多種加括號方式；只要不改變矩陣的先後順序，乘積結果相同，但所需的純量乘法次數可能不同。

若矩陣 $M_i$ 的大小為 $p_{i-1}\times p_i$，則相乘 $M_i\cdots M_j$ 時，令 $m[i,j]$ 表示所需的最少純量乘法次數，可用下列動態規劃遞迴式計算：

其中 $k$ 表示最後一次乘法的切割位置；$p_{i-1}p_kp_j$ 是將左側結果與右側結果相乘的成本。

本題的維度序列為：

解題方法

由只有一個矩陣的子鏈開始，依序計算長度為 2、3、4、5 的子鏈。每一格都列出不同切割位置的成本，再取最小值；最後依各子鏈的最佳切割位置還原括號順序。

（一）所有可能的乘法順序

五個矩陣保持原順序，加括號方式共有 $14$ 種：

1. $((((AB)C)D)E)$
2. $(((A(BC))D)E)$
3. $(((AB)(CD))E)$
4. $((A((BC)D))E)$
5. $((A(B(CD)))E)$
6. $(((AB)C)(DE))$
7. $((A(BC))(DE))$
8. $((AB)((CD)E))$
9. $((AB)(C(DE)))$
10. $(A(((BC)D)E))$
11. $(A((B(CD))E))$
12. $(A((BC)(DE))$)
13. $(A(B((CD)E)))$
14. $(A(B(C(DE))))$

以上共 $14$ 種，亦即五個矩陣的加括號方式數量為 Catalan 數 $C_4=14$。

（二）動態規劃計算最佳乘法順序

子鏈長度為 2：

子鏈長度為 3：

最佳順序為 $A(BC)$。

核心觀念

本題考查硬幣找零的 Greedy（貪婪）策略：每一步都從尚未使用的硬幣中，選擇面額不大於剩餘金額的最大硬幣，直到找足 $W$。硬幣面額若有重複，仍視為不同枚硬幣，使用後就移除。

貪婪策略每一步都做局部最佳選擇；但局部最佳不一定能導致硬幣總數最少，因此是否得到最佳解，須視硬幣面額組合而定。

解題方法與找零過程

將硬幣按面額由大到小排列，每次取不超過剩餘金額的最大面額。題目中硬幣為 $50,20,20,15,10,2,1,1,1$，找零金額 $W=75$。

1. 剩餘 $75$：取 $50$，剩餘 $75-50=25$。
2. 剩餘 $25$：取一枚 $20$，剩餘 $25-20=5$。
3. 剩餘 $5$：$15、10、2$ 都不超過 $5$ 的最大面額為 $2$，取兩枚 $2$，剩餘 $5-2-2=1$。
4. 剩餘 $1$：取一枚 $1$，剩餘 $0$。

因此 Greedy 找零為：

共使用 $5$ 枚硬幣。

Greedy-Change(S, W):
 將 S 依面額由大到小排序
 result ← 空集合
 remaining ← W

 依序檢查每一枚硬幣 c：
 當 c ≤ remaining：
 將 c 加入 result
 remaining ← remaining - c
 若 remaining = 0：
 回傳 result

 若 remaining > 0：
 回報無法找足金額

適用的資料結構

核心觀念

二元搜尋法能排除一半搜尋範圍，依賴陣列已排序：比較中間值後，才能判定目標在左半或右半。題目要求陣列維持未排序，因此不能只靠索引位置排除區段。

改以三個子陣列分治時，必須遞迴搜尋三個子陣列，因為任何一個都可能包含 $x$。三分法在此不會減少總搜尋工作量，只改變每次遞迴的切分方式。

解題方法

使用半開區間 $[L,R)$ 表示目前搜尋範圍，長度為 $R-L$。將區間切成三段：

其中 $M_1=L+\lfloor(R-L)/3\rfloor$，$M_2=L+\lfloor2(R-L)/3\rfloor$。程式先檢查目前區間的元素是否等於 $x$；若否，便遞迴搜尋三段。當區間為空時，表示沒有找到。

程式碼

核心觀念

本題考查中位數、算術平均數的定義，以及未排序陣列的選取（selection）與時間複雜度分析。

• 中位數：將數值依大小排序後，位於中央的數值。若 $n$ 為奇數，取第 $(n+1)/2$ 小的數；若 $n$ 為偶數，取第 $n/2$ 小與第 $(n/2+1)$ 小兩數的平均。
• 算術平均數：所有元素總和除以元素個數，即 $\frac{1}{n}\sum_{i=0}^{n-1}A[i]$。
• 選取（selection）：在未排序資料中，找出第 $k$ 小的元素。若採用最差時間為 $O(n)$ 的選取演算法，中位數可在線性時間內求得；若先排序再取中間元素，則需要 $O(n\log n)$。

題目指定 int *mean 與 int *average，以下依常見考題假設，將中位數及平均數以整數回傳；偶數筆資料的中位數與平均數採整數除法，會捨去小數部分。

解題方法

先複製陣列，避免尋找中位數時改動呼叫端的原始資料。對複本使用 median-of-medians（中位數的中位數） 選取演算法，取得所需順位的元素；其最差時間複雜度為 $O(n)$。

• 若 $n$ 為奇數，選出第 $(n+1)/2$ 小的元素。
• 若 $n$ 為偶數，分別選出第 $n/2$ 小與第 $(n/2+1)$ 小的元素，取其整數平均。

平均數則以一次走訪累加所有元素，最後除以 $n$。總時間仍為 $O(n)$，空間需求為 $O(n)$，主要用於保存選取演算法所操作的複本。