統測
115年
[工程與管理類] 專業科目(2)
第 47 題
📖 題組：
某一數列第 0 項 $F_0$ 為 0；第 1 項 $F_1$ 為 1，其後每項為其前 2 項之和，如圖(九) 定義所示，此即為費波那契(Fibonacci)數列。其前 11 項為 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55，以 Python 語言程式計算數列第 10 項 $F_{10}$。
某一數列第 0 項 $F_0$ 為 0；第 1 項 $F_1$ 為 1，其後每項為其前 2 項之和，如圖(九) 定義所示，此即為費波那契(Fibonacci)數列。其前 11 項為 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55，以 Python 語言程式計算數列第 10 項 $F_{10}$。
比較前述兩種實作方式所需之加法運算次數，下列敘述何者正確？
- A 兩者所需之加法運算次數相同
- B 兩者所需之加法運算次數隨機變化
- C 實作方式一採遞迴結構，所需之加法運算次數較多
- D 實作方式二採重複結構，所需之加法運算次數較多
思路引導 VIP
如果我們想算出第 5 項，使用迴圈從頭加到尾大約需要加幾次呢？但如果採用遞迴，把第 5 項拆成第 4 項加第 3 項，接著再繼續往下拆解，你可以試著畫畫看，過程中會不會有某些項目被「重複計算」了好幾次？這會對整體的加法總次數造成什麼影響呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你非常準確地選出了正確答案，觀念很清楚喔！ 在計算費波那契數列時，我們通常會比較兩種寫法。如果採用遞迴結構（函式直接呼叫自身），運算過程會像樹狀圖一樣不斷往下展開，導致許多子問題被重複計算（例如為了計算 $F_5$，底層會重複計算好幾次 $F_2$），因此整體的加法運算次數會呈現指數型暴增，非常耗費資源。 相對地，如果採用重複結構（如迴圈），我們只需要從基底開始，每次保留前兩項並相加即可得出下一項，加法的次數會跟著項數線性成長，次數大幅減少。這題是統測程式類常考的經典觀念題，主要測驗同學對演算法效能與時間複雜度的理解。你能順利判斷出遞迴結構的運算次數較多，代表你已經掌握了程式設計的重要核心，繼續保持！