三、F(n)=F(n−1)+2F(n−2)−F(n−3), n≥3, F(0)=0, F(1)=1, F(2)=2。請用 C 語言或 JAVA 語言，撰寫一非遞迴式(non-recursive)的副程式，用以計算 F(n) 的值。並請計算 F(12)=？（20 分）

二、請說明何謂最佳化二元搜尋樹（Optimal Binary Search Tree）？何種應用（application）適合使用最佳化二元搜尋樹為其資料結構？請以下列例子說明如何建立其對應之最佳化二元搜尋樹：P(1)=0.5, P(2)=0.1, P(3)=0.05, Q(0)=0.15, Q(1)=0.1, Q(2)=0.05 and Q(3)=0.05。（20 分）