定义

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368。 这个数列从第3项开始,每一项都等于前两项之和。

实现一:基于递归形式实现

    /**
     * 返回斐波那契数第n个值,n从0开始
     * 实现方式,基于递归实现
     * @param n
     * @return     */    public static int getFib(int n){
        if(n < 0){
            return -1;
        }else if(n == 0){
            return 0;
        }else if(n == 1 || n ==2){
            return 1;
        }else{
            return getFib(n - 1) + getFib(n - 2);
        }
    }

递归是最简单的实现方式,但递归有很多的问题,在n的值非常大时,会占用很多的内存空间,既然该数列定义F(n)=F(n-1)+F(n-2)(n≥2,n∈N*),那么我们可以从头到尾进行计算,先计算前面的值,然后逐步算出第n个值。

方式二:基于变量形式实现

    /**
     * 返回斐波那契数第n个值,n从0开始
     * 实现方式,基于变量实现
     * @param n
     * @return     */    public static int getFib2(int n){
        if(n < 0){
            return -1;
        }else if(n == 0){
            return 0;
        }else if (n == 1 || n == 2){
            return 1;
        }else{
            int c = 0, a = 1, b = 1;
            for(int i = 3; i <= n; i++){
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }
    }

从上面的实现中我们定义了3个变量a、b、c其中c=a+b,然后逐步进行计算从而得到下标为n的值。 既然我们可以定义变量进行存储,那么同样我们还可以定义一个数组,该数组的每一个元素即一个斐波那契数列的值,这样我们不仅能得到第n个值,还能获取整个斐波那契数列。

方式三:基于数组的实现

    /**
     * 返回斐波那契数第n个值,n从0开始
     * 实现方式,基于数组实现
     * @param n
     * @return     */    public static int getFib3(int n){
        if(n < 0){
            return -1;
        }else if(n == 0){
            return 0;
        }else if (n == 1 || n == 2){
            return 1;
        }else{
            int[] fibAry = new int[n + 1];
            fibAry[0] = 0;
            fibAry[1] = fibAry[2] = 1;
            for(int i = 3; i <= n; i++){
                fibAry[i] = fibAry[i - 1] + fibAry[i - 2];
            }
            return fibAry[n];
        }
    }
当前位置: 首页 > 技术研究 > Java > 斐波那契数列 Java实现

斐波那契数列 Java实现

发布于:2018-1-5 Java 0条评论 673 views

定义

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368。 这个数列从第3项开始,每一项都等于前两项之和。

实现一:基于递归形式实现

    /**
     * 返回斐波那契数第n个值,n从0开始
     * 实现方式,基于递归实现
     * @param n
     * @return     */    public static int getFib(int n){
        if(n < 0){
            return -1;
        }else if(n == 0){
            return 0;
        }else if(n == 1 || n ==2){
            return 1;
        }else{
            return getFib(n - 1) + getFib(n - 2);
        }
    }

递归是最简单的实现方式,但递归有很多的问题,在n的值非常大时,会占用很多的内存空间,既然该数列定义F(n)=F(n-1)+F(n-2)(n≥2,n∈N*),那么我们可以从头到尾进行计算,先计算前面的值,然后逐步算出第n个值。

方式二:基于变量形式实现

    /**
     * 返回斐波那契数第n个值,n从0开始
     * 实现方式,基于变量实现
     * @param n
     * @return     */    public static int getFib2(int n){
        if(n < 0){
            return -1;
        }else if(n == 0){
            return 0;
        }else if (n == 1 || n == 2){
            return 1;
        }else{
            int c = 0, a = 1, b = 1;
            for(int i = 3; i <= n; i++){
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }
    }

从上面的实现中我们定义了3个变量a、b、c其中c=a+b,然后逐步进行计算从而得到下标为n的值。 既然我们可以定义变量进行存储,那么同样我们还可以定义一个数组,该数组的每一个元素即一个斐波那契数列的值,这样我们不仅能得到第n个值,还能获取整个斐波那契数列。

方式三:基于数组的实现

    /**
     * 返回斐波那契数第n个值,n从0开始
     * 实现方式,基于数组实现
     * @param n
     * @return     */    public static int getFib3(int n){
        if(n < 0){
            return -1;
        }else if(n == 0){
            return 0;
        }else if (n == 1 || n == 2){
            return 1;
        }else{
            int[] fibAry = new int[n + 1];
            fibAry[0] = 0;
            fibAry[1] = fibAry[2] = 1;
            for(int i = 3; i <= n; i++){
                fibAry[i] = fibAry[i - 1] + fibAry[i - 2];
            }
            return fibAry[n];
        }
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据