# 費氏數列

November 28, 2021

``````F₀ = 0
F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂
``````

## 解法思路

``````Procedure FIB(N)
IF (N = 0 OR N = 1)
RETURN N
ELSE
RETURN FIB(N - 1) + FIB(N - 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² + f2²
``````

``````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]
``````

``````F₀ = 0
F₁ = 1
Fₙ = X * Fₙ₋₁ + Y * Fₙ₋₂
``````

## 程式實作

``````#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<>();
{
}

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: UTF-8
fibonacci = -> {
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]
}
}.call

print "輸入個數："
length = gets.to_i
0.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 = 0
fibonacci 1 = 1
fibonacci n = addPrevsRecusivelyUntilCounterIsN (fib 1) (fib 0) 2 n

| counter == n = result
| otherwise = addPrevsRecusivelyUntilCounterIsN result prev1 (counter + 1) n
where result = prev1 + prev2

main = 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]).
``````
``````# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

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)))
``````