中等 · 滑動對

斐波那契數

F(0)=0、F(1)=1、F(n)=F(n−1)+F(n−2)。用滑動對算——再回頭對比第 5 課的指數級遞迴。

題目

輸入:一個整數 n(0 ≤ n ≤ 45)。

輸出:F(n),其中 F(0) = 0,F(1) = 1。(F(45) = 1,134,903,170 —— 能裝進 int 的最大值。)

樣例:

輸入	輸出
`10`	`55`
`20`	`6765`

Program.cs — 你的解答

"用我的輸入試跑"的自定義輸入

判題完全在你的瀏覽器裡對隱藏測試執行。程式碼隨打隨存(本地)。Ctrl+Enter 判題。

提示 1 —— 滑動對

兩個變數 a = 0, b = 1。每輪:int t = a + b; a = b; b = t;。n 輪之後,a 就是 F(n)。

提示 2 —— 為什麼不用第 5 課的遞迴?

遞迴算 Fib(45) 要約 20 億次呼叫。滑動對只要 45 次。同樣的數學,指數級的成本差——這就是演算法思維。

解答(先自己試!)

int n = int.Parse(Console.ReadLine());
int a = 0, b = 1;
for (int i = 0; i < n; i++) { int t = a + b; a = b; b = t; }
Console.WriteLine(a);

你已經到了題庫的頂——回目錄複習,或去讀第 5 課看看遞迴什麼時候才是對的工具。