免費開始練習
地特三等申論題 105年 [資訊處理] 資料結構

第 一 題

📖 題組：
分別給定矩陣 A、B、C 與 D 的大小為 2×4、4×3、3×5 和 5×1：（每小題 5 分，共 15 分）
📝 此題為申論題，共 3 小題

小題 (一)

共有幾種加括號的方法？

思路引導 VIP

看到「矩陣連乘加括號方法數」，應立刻聯想到「卡塔蘭數（Catalan number）」的應用。對於 n 個矩陣連乘，其加括號的方法數等於第 n-1 個卡塔蘭數，可直接套用公式計算或使用列舉法快速求得。

🤖
AI 詳解
AI 專屬家教

【解題關鍵】利用卡塔蘭數（Catalan number）公式或直接列舉法來計算 n 個矩陣連乘的括號組合數。 【解答】 已知有 A、B、C、D 共 4 個矩陣相乘（n = 4）。

小題 (二)

例如(AB)(CD)，共需多少次乘法？

思路引導 VIP

考生看到此題應先回想「矩陣乘法」的運算規則：當大小為 p×q 的矩陣與 q×r 的矩陣相乘時，需耗費 p×q×r 次純量乘法，且產生大小為 p×r 的新矩陣。接著依照題目指定的括號順序 (AB)(CD) 拆解步驟，分別計算各個局部矩陣的乘法次數再作加總即可。

🤖
AI 詳解
AI 專屬家教

【解題關鍵】大小為 $p \times q$ 的矩陣與大小為 $q \times r$ 的矩陣相乘，需進行 $p \times q \times r$ 次乘法，且結果矩陣大小為 $p \times r$。 【解答】 計算：

小題 (三)

求出三者乘積之最有效的方式為何？

思路引導 VIP

看到多個矩陣連乘求最佳效率的問題，立刻想到使用動態規劃（Dynamic Programming）中的連鎖矩陣相乘（Matrix Chain Multiplication）演算法。透過建立成本表，由小範圍（兩個矩陣）逐步推導至大範圍（四個矩陣），找出總乘法次數最少的括號組合。

🤖
AI 詳解
AI 專屬家教

【解題思路】使用動態規劃（Dynamic Programming）求解連鎖矩陣相乘（Matrix Chain Multiplication），找出純量乘法總次數最小的結合順序。 【詳解】 已知：各矩陣維度可記為陣列 $P = [2, 4, 3, 5, 1]$，分別對應 $A(2\times 4)$、$B(4\times 3)$、$C(3\times 5)$、$D(5\times 1)$。

📝 同份考卷的其他題目

查看 105年[資訊處理] 資料結構 全題

升級 VIP 解鎖