Wikioi 天梯 Fibonacci數列 3（1978）

題目描述 Description

斐波納契數列是這樣的數列：

f1 = 1

f2 = 1

f3 = 2

f4 = 3

....

fn = fn-1 + fn-2

輸入一個整數n

求fn

輸入描述 Input Description

一個整數n, n<= 40

輸出描述 Output Description

一個整數fn

樣例輸入 Sample Input

3

樣例輸出 Sample Output

2

資料範圍及提示 Data Size & Hint

n<=40

很高興，比起上一題，本題很能展現遞推的優越性（其實pascal語言由于申請棧空間時有時間損耗，是以遞推算法對于p黨來說普遍優于遞歸算法）（RE：202也算一條吧~~）

本題既然給出了規律，那麼問題其實就是根據規律依靠已知（一般是fib[1]和fib[2]）求未知（fib[n]）。

規律展現了這樣的遞推式：fib[n]=fib[n-1]+fib[n-2]

首先遞歸實作十分簡單（這也是遞歸的好處，很難想出遞推順序的果斷用遞歸騙分），不斷遞歸直到n=1 or 2。

但是遞歸過程中（沒有記憶化）會造成重複計算，由于計算f[n]和f[n-1]時，都用到f[n-2]，然而兩者的計算過程是獨立進行的，是以f[n-2]就悲催地被計算了兩次，每次計算都要遞歸到最深層。這樣一來有形的時間就增加了一倍（還有上文說過的pascal缺點）。這是遞推就大顯身手。

如果說遞歸是被動索取，那麼遞推就是主動探索。遞推由已知出發，不斷把未知變成已知，直到所求的答案也變成已知。

那麼為了使算過的數不被忘掉，我們需要數組來實作，不斷計算fib[n]，把它存在f數組的f[n]中，下次用到fib[n]時直接調用f[n]的值。

遞推對pascal來說，一不爆棧，二節省時間，這是遞歸所沒有的。

算法描述：讀入n，依次計算fib[i]的值，直到i=n。輸出f[n]。

Program fib;
Var
	n,i:longint;
	f:array[1..100]of longint;
	
Begin
	readln(n);
	fillchar(f,sizeof(f),0);
	f[1]:=1;
	f[2]:=1;
	for i:=3 to n do f[i]:=f[i-1]+f[i-2];
	writeln(f[n]);
End.