高考申論題
106年
[資訊處理] 資料結構
第 一 題
📖 題組：
矩陣相乘是問題解決中常見的計算，但相乘順序對於計算效能有極大的影響。給定 n 個矩陣，A1, A2, ..., An，且任一矩陣 Ai 大小為 pi-1 × pi，p0, p1, ..., pn 皆為正整數。A1 × A2 × ... × An 實際計算過程可以是(...((A1 × A2) × A3) × ... × An)、(A1 × (A2 × (...× (An-2 × (An-1 × An))...)))、或其他合理的順序，而因矩陣相乘順序不同，所需要的乘法運算次數可能也會不同。透過動態規劃（dynamic programming）、二維陣列的應用及遞迴程式，可以找到最少乘法運算次數的計算順序。方法如下：令 m[i, j] 為計算 Ai × Ai+1 × ... × Aj 時所需最少乘法運算次數，m[i, j] 可以下列遞迴公式表示之： m[i, j] = { min_{i <= k < j} { m[i, k] + m[k+1, j] + p_{i-1} * p_k * p_j }, if i < j ; 0, if i >= j } （一）請說明 A1 × A2 × ... × An 相乘過後的矩陣大小為何？（3 分） （二）透過上述方法所找到的最少乘法運算次數，應為二維陣列 m[i, j] 中的那個元素，亦即 i, j 應分別為何？（3 分） （三）若 n = 4 且 p0, p1, p2, p3, p4 分別為 3, 4, 5, 4, 2，請計算並填寫出二維陣列 m[i, j]。（11 分） （四）承上小題（三），請說明該四矩陣相乘，A1 × A2 × A3 × A4，最少共需有幾次乘法運算。（3 分）
矩陣相乘是問題解決中常見的計算，但相乘順序對於計算效能有極大的影響。給定 n 個矩陣，A1, A2, ..., An，且任一矩陣 Ai 大小為 pi-1 × pi，p0, p1, ..., pn 皆為正整數。A1 × A2 × ... × An 實際計算過程可以是(...((A1 × A2) × A3) × ... × An)、(A1 × (A2 × (...× (An-2 × (An-1 × An))...)))、或其他合理的順序，而因矩陣相乘順序不同，所需要的乘法運算次數可能也會不同。透過動態規劃（dynamic programming）、二維陣列的應用及遞迴程式，可以找到最少乘法運算次數的計算順序。方法如下：令 m[i, j] 為計算 Ai × Ai+1 × ... × Aj 時所需最少乘法運算次數，m[i, j] 可以下列遞迴公式表示之： m[i, j] = { min_{i <= k < j} { m[i, k] + m[k+1, j] + p_{i-1} * p_k * p_j }, if i < j ; 0, if i >= j } （一）請說明 A1 × A2 × ... × An 相乘過後的矩陣大小為何？（3 分） （二）透過上述方法所找到的最少乘法運算次數，應為二維陣列 m[i, j] 中的那個元素，亦即 i, j 應分別為何？（3 分） （三）若 n = 4 且 p0, p1, p2, p3, p4 分別為 3, 4, 5, 4, 2，請計算並填寫出二維陣列 m[i, j]。（11 分） （四）承上小題（三），請說明該四矩陣相乘，A1 × A2 × A3 × A4，最少共需有幾次乘法運算。（3 分）
📝 此題為申論題，共 4 小題
小題 (一)
請說明 A1 × A2 × ... × An 相乘過後的矩陣大小為何？（3 分）
思路引導 VIP
考生看到這題應先回想線性代數中「矩陣乘法」的基本規則：大小為 (r × s) 的矩陣與 (s × t) 的矩陣相乘，結果會是 (r × t)。接著觀察題幹中矩陣 Ai 的維度定義為 pi-1 × pi，將頭尾連鎖推導即可得出結果。
小題 (二)
透過上述方法所找到的最少乘法運算次數，應為二維陣列 m[i, j] 中的那個元素，亦即 i, j 應分別為何？（3 分）
思路引導 VIP
看到這題先回顧 m[i, j] 的定義：代表計算第 i 個到第 j 個矩陣相乘所需的最少乘法次數。題目要求全部 n 個矩陣 A1 × A2 × ... × An 的最少乘法運算次數，直接將起點和終點代入定義即可得出對應的陣列索引。
小題 (三)
若 n = 4 且 p0, p1, p2, p3, p4 分別為 3, 4, 5, 4, 2，請計算並填寫出二維陣列 m[i, j]。（11 分）
思路引導 VIP
看到「矩陣連乘」與「動態規劃」，應立即聯想其遞迴公式，並遵循「由短到長」的連乘區間長度依序計算（長度 1 到長度 n）。在推導計算時需將每種分割點 k 的成本列出比較，取最小值填入二維陣列中。
小題 (四)
承上小題（三），請說明該四矩陣相乘，A1 × A2 × A3 × A4，最少共需有幾次乘法運算。（3 分）
思路引導 VIP
本題主要測試對動態規劃陣列結果的解讀。考生應清楚知道 A1 × A2 × A3 × A4 的最少乘法運算次數即為 m[1, 4] 的值。作答時直接提取上一小題的最終計算結果，並簡要列出比較過程以確保計分完整。