# 費式數列

## 說明

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

1、1 、2、3、5、8、13、21、34、55、89......

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2

## 算法

``Procedure FIB(N)     IF (N = 0 OR N = 1)         RETURN N    ELSE         RETURN FIB(N-1) + FIB(N-2)``

``Procedure FIB(N)    IF (N = 0 OR N = 1)         RETURN N    a = 0;     b = 1;     FOR i = 2 TO N [        temp = b;         b = a + b;         a = temp;     ]    RETURN b; ] ``

``F(0) = 0; F(1) = 1; FOR i<-2 TO N [    F(i) = F(i-1) + F(i-2); ] ``

``Procedure FIB(N)     IF (n <= 1)        RETURN(n);     IF (n = 2)         RETURN(1);     ELSE [         i = n/2;         f1 = FIB(i+1);         f2 = FIB(i);         IF (n mod 2 = 0)            RETURN( f2*(2*f1+f2) );         ELSE             RETURN ( f1**2+f2**2 );     ]] ``

F0 = 0
F1 = 1
Fn = X * Fn-1 + Y * Fn-2

``````def fib(n) {
if n == 0 or n == 1 {
return n
}
return fib(n - 1) + fib(n - 2)
}

iterate(0, 10).forEach(i -> println(fib(i)))``````

``#include <stdio.h> #include <stdlib.h> #define LEN 20 void fill_fibonacci_numbers(int*, int);void print(int*, int len);int main(void) {     int fib[LEN] = {0};         fill_fibonacci_numbers(fib, LEN);    print(fib, LEN);    return 0; } void fill_fibonacci_numbers(int* fib, int len) {    fib[0] = 0;     fib[1] = 1;     int i;    for(i = 2; i < len; i++) {        fib[i] = fib[i-1] + fib[i-2];     }}void print(int* arr, int len) {    int i;    for(i = 0; i < len; i++) { printf("%d ", arr[i]); }     printf("\n");}``

``import java.util.*;public class Fibonacci {    private List<Integer> fib = new ArrayList<>();    {        fib.add(0);        fib.add(1);    }        Integer get(int n) {        if(n >= fib.size()) for(int i = fib.size(); i <= n; i++) {            fib.add(fib.get(i - 1) + fib.get(i - 2));        }        return fib.get(n);    }        public static void main(String[] args) {        Fibonacci fibonacci = new Fibonacci();        for(int i = 0; i < 20; i++) {            System.out.print(fibonacci.get(i) + " ");        }    }}``

``def fibonacci(n, fib = [0, 1]):    if n >= len(fib):        for i in range(len(fib), n + 1):            fib.append(fib[i - 1] + fib[i - 2])    return fib[n]for i in range(0, 20):    print(fibonacci(i), end=' ')``

``def fib(n: Int): Int = n match {    case 0 => 0    case 1 => 1    case _ => fib(n - 1) + fib(n - 2)}(for(i <- 0 until readInt) yield fib(i)).foreach(i => print(i + " "))``

``# encoding: Big5fibonacci = -> {    fib = [0, 1]    -> n {         if n >= fib.size            fib.size.upto(n) do |i|                fib << fib[i - 1] + fib[i - 2]            end        end        fib[n]    }}.callprint "輸入個數："length = gets.to_i0.upto(length - 1) do |i|    print fibonacci.call(i).to_s + ' 'end``

``var fibonacci = function() {    var fib = [0, 1];    return function(n) {        if(n >= fib.length) for(var i = fib.length; i <= n; i++) {            fib[i] = fib[i - 1] + fib[i - 2];        }        return fib[n];    };}();    for(var i = 0; i < 20; i++) { print(fibonacci(i)); }``

``fibonacci 0 = 0fibonacci 1 = 1fibonacci n = addPrevsRecusivelyUntilCounterIsN (fib 1) (fib 0) 2 naddPrevsRecusivelyUntilCounterIsN prev1 prev2 counter n    | counter == n = result    | otherwise = addPrevsRecusivelyUntilCounterIsN result prev1 (counter + 1) n    where result = prev1 + prev2main = sequence [print (fibonacci i) | i <- [0..19]]``

``````fibonacci(0, 0).
fibonacci(1, 1).
fibonacci(N, Result) :- NP1 is N - 1, NP2 is N - 2,
fibonacci(NP1, FP1), fibonacci(NP2, FP2),
Result is FP1 + FP2.

main([Arg0|_]) :-
atom_number(Arg0, N),
fibonacci(N, Result),
writef("The nth %n is %d\n", [Arg0, Result]).``````