【經典算法題-2】費式數列（Fibonacci數列）

歡迎關注公衆号[搞前端的半夏]，回複[算法]，擷取各種算法資料。

說明

Fibonacci為1200年代的歐洲數學家，在他的着作中曾經提到：「若有一隻免子每個月生一隻小免子，一個月後小免子也開始生産。起初隻有一隻免子，一個月後就有兩隻免子，二個月後有三隻免子，三個月後有五隻免子（小免子投入生産）…。

注意新生的小免子需一個月成長期才會投入生産，類似的道理也可以用于植物的生長，這就是Fibonacci數列，一般習慣稱之為費氏數列，例如以下： 1、1 、2、3、5、8、13、21、34、55、89…

解法

依說明，我們可以将費氏數列定義為以下：

fn = fn-1 + fn-2　　 if n > 1

fn = n　　　　　　 if n = 0, 1

#include <stdio.h> 
#include <stdlib.h> 

#define N 20 

int main(void) { 
	int Fib[N] = {0}; 
	int i; 
	
	Fib[0] = 0; 
	Fib[1] = 1; 
	
	for(i = 2; i < N; i++) 
	Fib[i] = Fib[i-1] + Fib[i-2]; 
	
	for(i = 0; i < N; i++) 
	printf("%d ", Fib[i]); 
	printf("\n"); 
	return 0; 
}

           

歡迎關注公衆号[搞前端的半夏]，回複[算法]，擷取各種算法資料。