斐波那契数列Java三种实现

以你之姓@ 2022-06-01 12:27 154阅读 0赞

关于斐波那契数列在百度百科上的定义如下：   
斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N\*）[百度百科][Link 1]关于斐波那契数列的来源请参见[兔子问题][Link 2]根据其定义我们可以很方便的构建出该数列的数据结构实现。

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

/** * 返回斐波那契数第n个值,n从0开始 * 实现方式，基于递归实现 * @param n * @return * @author mhy2011@163.com * @since 2015年8月18日上午9:41:30 */
        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 * @author mhy2011@163.com * @since 2015年8月18日上午9:32:26 */
        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 * @author mhy2011@163.com * @since 2015年8月18日上午9:22:15 */
        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];
            }
        }

到此3种Java实现斐波那契数列完成，如果大家有其他更好的实现方式欢迎指出

[原文地址][Link 3]

[Link 1]: http://baike.baidu.com/link?url=JaxU_YTxSidcS8VQeglABLPm--5tooOfnrjK2ruP3XMMat5I_79W85nQY8qPGIbkPS_8Km3hyWo-C2EEuf6M0a
[Link 2]: http://baike.baidu.com/link?url=rPwsk64gtGwC16II6PadF6-psKTBtw9SAgK_JVv7Sgo7qRUayUZ_HW585UjP_BMALk674fs5YiDi1XauPSDXF_
[Link 3]: http://blog.csdn.net/u010397369/article/details/47751695