斐波那契数列(实现和思路)

KLQ 2020-05-13 09:50:04 java常见问答 4788

今天要给大家分享的实例就是和斐波那契数列相关的内容,下面一起来看看相关题目以及问题的解决思路和代码实现方式吧!

题目:

输入一个整数n,请输出斐波那契数列的第n项

注:

从0开始,第0项为0,第1项是1

n<=39

思路1:

尾递归

代码实现:

public class Solution {
    public int Fibonacci(int n) {
        return Fibonacci(n,0,1);
    }
     
     
    private static int Fibonacci(int n,int acc1,int acc2){
        if(n==0) return 0;
        if(n==1) return acc2;
        else     return Fibonacci(n - 1, acc2, acc1 + acc2);
         
    }
}

思路2:

考虑负数,大数,算法的复杂度,空间的浪费。

代码实现:

public class Solution {
    public int Fibonacci(int n) {
        //方法1:用递归,系统会让一个超大的n来让Stack Overflow,所以
        //递归就不考虑了
         
        //使用迭代法,用fn1和fn2保存计算过程中的结果,并复用起来
        int fn1 = 1;
        int fn2 = 1;
         
        //考虑出错情况
        if (n <= 0) {
            return 0;
        }
        //第一和第二个数直接返回
        if (n == 1 || n == 2) {
            return 1;
        }
 
        //当n>=3时,走这里,用迭代法算出结果
        //这里也说明了,要用三个数操作的情况,其实也可以简化为两
        //个数,从而节省内存空间
        while (n-- > 2) {
            fn1 += fn2;
            fn2 = fn1 - fn2;
        }
        return fn1;
    }
}

思路3

代码实现:

/*
     * O(logN)解法:由f(n) = f(n-1) + f(n-2),可以知道
     * [f(n),f(n-1)] = [f(n-1),f(n-2)] * {[1,1],[1,0]}
     * 所以最后化简为:[f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2)
     * 所以这里的核心是:
     * 1.矩阵的乘法
     * 2.矩阵快速幂(因为如果不用快速幂的算法,时间复杂度也只能达到O(N))
     */
public class Solution {
    public int Fibonacci(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        //底
        int[][] base = {{1,1},
                        {1,0}};
        //求底为base矩阵的n-2次幂
        int[][] res = matrixPower(base, n - 2);
        //根据[f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2),f(n)就是
        //1*res[0][0] + 1*res[1][0]
        return res[0][0] + res[1][0];
    }
     
    //矩阵乘法
    public int[][] multiMatrix(int[][] m1,int[][] m2) {
        //参数判断什么的就不给了,如果矩阵是n*m和m*p,那结果是n*p
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }
    /*
     * 矩阵的快速幂:
     * 1.假如不是矩阵,叫你求m^n,如何做到O(logn)?答案就是整数的快速幂:
     * 假如不会溢出,如10^75,把75用用二进制表示:1001011,那么对应的就是:
     * 10^75 = 10^64*10^8*10^2*10
     * 2.把整数换成矩阵,是一样的
     */
    public int[][] matrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];
        //先把res设为单位矩阵
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        } //单位矩阵乘任意矩阵都为原来的矩阵
        //用来保存每次的平方
        int[][] tmp = m;
        //p每循环一次右移一位
        for ( ; p != 0; p >>= 1) {
            //如果该位不为零,应该乘
            if ((p&1) != 0) {
                res = multiMatrix(res, tmp);
            }
            //每次保存一下平方的结果
            tmp = multiMatrix(tmp, tmp);
        }
        return res;
    }
     
}

以上就是今天的实例分享了,更多相关实例请继续关注本站的java实例栏目了解吧。

推荐阅读:

二分法查找(思路和实现),二分法查找是什么?

求数值的整数次方(思路和实现)

调整数组顺序使奇数位于偶数前面(思路和实现)