書籍分享天地

費伯納西數列

上面這一行數字，前面兩項的和等於後面一項的值。

[0]前面沒有任何東西，所以如果有人輸入0就要寫一個if來返回0。

[1]前面的項次不夠，所以如果有人輸入1就要寫一個if來返回1。

  [2]我們都知道前兩項的和加起來等於第三項，也就是說[2] = [1] +[0]，如果用看的的確是這樣，但是電腦沒有眼睛，所以我們必須告訴電腦規則，我在鍵盤上打2 要如何告訴電腦 [1]+[0]? 不就是[2-1]+[2-2] 就是[1]+[0]。

輸入值用f來代替就可以寫成。

[f] = [f-1] + [f-2]

[5] = [5-1] + [5-2] = [4]+[3]

程式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include<iostream>

int fa(int f)
{
	if(f == 0) return 0;	
	if(f == 1) return 1;
	
	return fa(f-1)+fa(f-2);
}

int main()
{
	std::cout<<fa(3)<<std::endl;
	return 0;
}

fa(0) = 0

fa(1) = 1

fa(2) = fa(1) + fa(0) = 1+0 = 1

fa(3) = fa(2)+fa(1) = 1 + 1 = 2

fa(4) = fa(3)+fa(2) = 2 + 1 = 3

fa(5) = fa(4)+fa(3) = 3 + 2 = 5

每一次的運算都一定要先算出最初的值，才能回傳結果。