Fibonacci numbers (斐波那契數列)

義大利數學家 Fibonacci 所發明,他描述兔子生長的數目時用上了這數列,假設兔子每個月都會生產小兔子,如此不停的繁衍,且兔子永不死去 此數列常在程式演算法的教科書中出現,數列的解法有很多種,以下列出幾個簡單的 Java 程式解法

簡單表達式

F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2

遞迴解法

public long fib(int n) {
    if (n < 2) return n;   
    else return fib(n - 1) + fib(n - 2);
}

迴圈解法

public long fib(int n) {
    if (n < 2)
        return n;

    long x = 0L;
    long y = 1L;
    long temp = 0L;

    for (int i = 2; i <= n; i++) {
        temp = y;
        y = x + y;
        x = temp;
    }
    return y;
}

Fork / Join 解法

import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

public class Fibonacci extends RecursiveTask<Long> {

    private final int n;

    Fibonacci(int n) {
        this.n = n;
    }

    @Override
    public Long compute() {
        if (n < 2) return (long) n;

        final Fibonacci f1 = new Fibonacci(n - 1);
        final Fibonacci f2 = new Fibonacci(n - 2);
        f1.fork();
        return f2.compute() + f1.join();
    }
 
    public static void main(String[] args) {
        final ForkJoinTask<Long> fjt = new Fibonacci(Integer.parseInt(args[0]));
        new ForkJoinPool().execute(fjt);
        try {
            System.out.println(fjt.get());
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
    }
}

Memoization 解法
記憶前幾次計算過的結果,避免重覆的計算,藉此來提高運算速度

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    private static Map<Integer, Long> cache = new HashMap<>();

    public static long fib(int n) {
        if (n < 2) return n;
        return cache.computeIfAbsent(n, k -> Math.addExact(fib(k - 1), fib(k - 2)));
    }

    public static void main(String args[]) {
        fib(Integer.parseInt(args[0]));
    }
}

參考 :
http://en.wikipedia.org/wiki/Fibonacci_number
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2