(二)請使用 Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘 A✖B✖C✖D✖E 的 最佳乘法順序（請用括號表示乘法順序） ，使得五個矩陣相乘所需要花費 的乘法數量最少。（15 分）

(四)請計算發行新股收現數。（2 分）

三、乙公司經營牧場養殖肉豬並以出售豬肉為本業，20X4/1/1 購買肉豬 100 頭，每頭成本$50,000 並發生運費$200,000。20X4 年之飼料成本 為$4,500,000，人員工薪$2,000,000。2014 年底，每頭肉豬之公允價值 減出售成本為$200,000。2015 年 1 月 1 日，屠宰 20 頭肉豬並出售， 每頭售價$300,000 並發生運費$80,000。請作乙公司 20X5 年相關之分 錄。（12 分）

四、20X5/1/1 丙公司因合併必須承擔除役負債，該公司依法必須於 10 年 後移除因合併而取得之加油站相關設施，丙公司採用期望現值技術以 衡量除役負債之公允價值。丙公司對負債公允價值之估計包括以下之 輸入值：人工成本、間接成本之分攤、相關風險（不確定因素）之補 償、通貨膨脹、貨幣時間價值及信用風險。丙公司對人工成本的機率 及發生金額之估計為：百分之二十五金額為$200,000；百分之五十金 額為$300,000；百分之二十五金額為$400,000，間接成本之分攤則以 人工成本之 75%估計之，廠商利潤為人工及間接成本之 20%，不確 定因素之影響則以期望現金流量之 5%計算之；此外假設 10 年間的 通貨膨脹率均為 4%。20X5/1/1 時無風險利率為 3%，並加上 4%之信 用風險。試計算此一除役負債之公允價值（6 分）。（利率 4%，期數 10 之複利終值為 1.4802；利率 7%，期數 10 之複利現值為 0.5083）

(一)請列出此 5 個矩陣相乘 A✖B✖C✖D✖E 所有 可能的乘法順序（請用括號表示乘法順序） 。（5 分）

(三)請列出此五個矩陣相乘所需要花費的最少 乘法數量。 （5 分）（注意：未說明 Dynamic Programming 的計算過程， 不予計分。）

(一)請設計一個 Greedy（貪婪）的演算 法，來解決找錢給顧客的問題，使得找給顧客金額 W 所使用的銅板數量 最少，並依此 Greedy 的演算法列出找給顧客金額 W=$75 的過程。 （15 分）

(二)此 Greedy 演算法適合使用何種資料結構來完成。（5 分）

(三)此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5 分）

(一)請使用 C++或 Python 語言，修改此二元 搜尋法，使其能對未排序的（unsorted）且長度為 n 的陣列 A[0:n1]，進 行三元化搜尋，即以 divide-and-conquer 技巧將此陣列切成三個子陣列， 並在可能包含資料值 x 的子陣列繼續進行 divide-and-conquer 技巧的搜 尋，如果找到則回傳 1，如果找不到則回傳 0。（17 分） （注意：請寫一 個 searching 類別，內含一個 search 功能）

(二)請分析修改後的三元化搜尋 法其最差時間複雜度（worst case time complexity）以 order 的方式表示。 （8 分） （注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）