斐波那契数列(Fibonacci)的几种实现

斐波那契数列，定义：

斐波那契数列.jpg

递归求解

普通递归

    public int Fib(int n) {
        if(n <= 1) {
            return n;
        }
        return Fib(n-1) + Fib(n - 2);
        
    }

尾递归

    public int Fib(int n) {
        return Fib(n, 0, 1);
    }
    
    public int Fib(int n, int acc1, int acc2) {
        if(n == 0) 
            return 0;
        if(n == 1)
            return acc2;
        return Fib(n -1, acc2, acc1 + acc2);
        
    }

非递归递推解

    public int Fib(int n) {
        int []a = new int[1000];
        a[0] = 0;
        a[1] = 1;
        for(int i = 2; i < 1000; i++) {
            a[i] = a[ i-1 ] + a[ i-2 ];
        }
        return a[n];
    }

利用矩阵计算

通过矩阵的快速幂实现

    public int Fib(int n) {
        Matrix ans = new Matrix(1, 0, 0, 1);
        Matrix base = new Matrix(1, 1, 1, 0);
        while(n > 0) {
            if((n & 1) == 1) {
                ans = mlti(base, ans);
            }
            base = mlti(base, base);
            n >>= 1;
        }
        printM(ans);
        return ans.m[1][0];
        
    }

    public Matrix mlti(Matrix a, Matrix b) {
        Matrix tmp = new Matrix(0, 0, 0, 0);
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                for(int k = 0; k < 2; k++) {
                    tmp.m[i][j] = tmp.m[i][j] + a.m[i][k] * b.m[k][j];
                }
            }
        }
        return tmp;
    }

Matrix.class:

public class Matrix {
    public int[][] m = new int[2][2];
    public Matrix(int a, int b, int c, int d) {
        m[0][0] = a;
        m[0][1] = b;
        m[1][0] = c;
        m[1][1] = d;
    }
}