申論 1A 為（8×4）矩陣、B 為（4×10）矩陣、C 為（10×3）矩陣、D 為（3×20）矩陣、E 為（20×4）矩陣，㈠請列出此5 個矩陣相乘ABCDE 所有可能的乘法順序（請用括號表示乘法順序）。（5 分）㈡請使用DynamicProgramming（動態規劃）的技巧計算出此五個矩陣相乘ABCDE 的最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費的乘法數量最少。（15 分）㈢請列出此五個矩陣相乘所需要花費的最少乘法數量。（5 分）（注意：未說明Dynamic Programming 的計算過程，不予計分。）
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2假設收銀機內銅板的集合S={$50, $20, $20, $15, $10, $2, $1, $1, $1}，而預計找錢給顧客的金額W=$75。㈠請設計一個Greedy（貪婪）的演算法，來解決找錢給顧客的問題，使得找給顧客金額W 所使用的銅板數量最少，並依此Greedy 的演算法列出找給顧客金額W=$75 的過程。（15 分）㈡此Greedy 演算法適合使用何種資料結構來完成。（5 分）㈢此Greedy演算法的解法是否能保證為最佳解？請舉例說明。（5 分）
申論 3二元搜尋法（binary search）使用divide-and-conquer（分而治之）演算法技巧，對一個已排序的（sorted）且長度為n 的陣列A[0:n1]，以二元化方式進行資料值x 的搜尋，其最差時間複雜度（worst case timecomplexity）可降到(log n)。㈠請使用C++或Python 語言，修改此二元搜尋法，使其能對未排序的（unsorted）且長度為n 的陣列A[0:n1]，進行三元化搜尋，即以divide-and-conquer 技巧將此陣列切成三個子陣列，並在可能包含資料值x 的子陣列繼續進行divide-and-conquer 技巧的搜尋，如果找到則回傳1，如果找不到則回傳0。（17 分）（注意：請寫一個searching 類別，內含一個search 功能）㈡請分析修改後的三元化搜尋法其最差時間複雜度（worst case time complexity）以order 的方式表示。（8 分）（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）
申論 4㈠請使用C 語言寫一副程式void FindMeanAverage(int A [], int n, int *mean, int * average)，對一個未排序的（unsorted）且長度為n 的陣列A[0:n1]，尋找陣列中的中位數與平均數，並分別存入mean 及average運算複雜度。（17 分）㈡請舉例說明此副程式最差情況（worst case）所花費的運算複雜度。（8 分）（注意：請加註解說明程式碼作法。）