フィボナッチ数列

フィボナッチ数列とは、次のような数列という。

$\left\{ \begin{array}{ll} f_n = f_{n-1} + f_{n-2} & n \geq 3 \\ f_1 = f_2 = 1 & \end{array}\right.$

すなわち、この数列の第n項は、第(n-1)項と第(n-2)を加えたものである。 但し、第1項と第2項はともに１である。 これを実装すると以下のようになる。

long int fib( unsigned int n){

if( n >= 3 ){

return( fib(n-1) + fib(n-2));

}

if( n == 1 || n == 2 ){

return(1L);

}

}

上記のフィボナッチ数列計算関数を呼び出すメインプログラムと、 その実行結果を以下に示す。

#include <stdio.h>

void main(){

unsigned int n;

printf(”フィボナッチ数列\n”);

for(n = 1; n <= 12; n++){

printf(”%2d : %ld\n”, n, fib(n));

}

}

フィボナッチ数列

1 : 1

2 : 1

3 : 2

4 : 3

5 : 5

6 : 8

7 : 13

8 : 21

9 : 34

10 : 55

11 : 89

12 : 144