高考申論題
110年
[資訊處理] 資料結構
第 一 題
📖 題組：
A 為（8×4）矩陣、B 為（4×10）矩陣、C 為（10×3）矩陣、D 為（3×20）矩陣、E 為（20×4）矩陣，(一)請列出此 5 個矩陣相乘 A×B×C×D×E 所有可能的乘法順序（請用括號表示乘法順序）。（5 分）(二)請使用 Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘 A×B×C×D×E 的最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費的乘法數量最少。（15 分）(三)請列出此五個矩陣相乘所需要花費的最少乘法數量。（5 分）（注意：未說明 Dynamic Programming 的計算過程，不予計分。）
A 為（8×4）矩陣、B 為（4×10）矩陣、C 為（10×3）矩陣、D 為（3×20）矩陣、E 為（20×4）矩陣，(一)請列出此 5 個矩陣相乘 A×B×C×D×E 所有可能的乘法順序（請用括號表示乘法順序）。（5 分）(二)請使用 Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘 A×B×C×D×E 的最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費的乘法數量最少。（15 分）(三)請列出此五個矩陣相乘所需要花費的最少乘法數量。（5 分）（注意：未說明 Dynamic Programming 的計算過程，不予計分。）
📝 此題為申論題，共 3 小題
小題 (一)
請列出此 5 個矩陣相乘 A×B×C×D×E 所有可能的乘法順序（請用括號表示乘法順序）。（5 分）
思路引導 VIP
- 考點辨識：這是一個典型的「矩陣鏈乘積（Matrix Chain Multiplication）」問題，第一小題要求列出所有組合。2. 知識聯結：矩陣相乘的結合律。五個矩陣 A, B, C, D, E 的括號組合數量符合卡特蘭數（Catalan number）C(n-1)，其中 n=5，所以 C(4) = 14 種。3. 展開邏輯：建議採用系統化的展開方式，例如先固定最後一次相乘的位置（如 (ABCD)E, (ABC)(DE)...），再對括號內部進行遞迴拆解，以確保不漏列。
小題 (二)
請使用 Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘 A×B×C×D×E 的最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費的乘法數量最少。（15 分）
思路引導 VIP
- 考點辨識：動態規劃解矩陣鏈相乘問題。2. 定義維度：$p_0=8, p_1=4, p_2=10, p_3=3, p_4=20, p_5=4$。3. 建立 DP 表：$m[i,j]$ 表示從矩陣 $i$ 到 $j$ 的最小乘法次數。轉移方程為 $m[i,j] = \min_{i \le k < j} {m[i,k] + m[k+1,j] + p_{i-1}p_kp_j}$。4. 實戰建議：考試時務必畫出表格，從小區間長度（2個矩陣）算到大區間（5個矩陣），並記錄分割點 $s[i,j]$ 以回推最佳括號順序。
小題 (三)
請列出此五個矩陣相乘所需要花費的最少乘法數量。（5 分）（注意：未說明 Dynamic Programming 的計算過程，不予計分。）
思路引導 VIP
此題與第二小題連動，直接引用 DP 表格最終計算出的數值 $m[1,5]$。在申論中，這部分的給分通常取決於前面的 DP 過程是否完整。