java实现斐波那契数列的三种方法

约定不等于承诺〃 2022-04-16 01:55 179阅读 1赞

## Java实现斐波那契数列的三种方法 ##

**什么是斐波那契数列**

*  这里借用一下度娘的一段话：斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……  
    其规律很明显，从第3个数开始，每个数都等于它前两个数的和。  
    那么通过java可以如何实现斐波那契数列呢？这里介绍三种方法。

**1.通过递归实现**  
通过代码实现以下效果：当你输入n时，会获取斐波那契数列的第n个数的值。

public static int fibonacci(int n){
    
            if (n == 1 || n == 2) {             //特殊情况，分开讨论
                return 1;
            }
            if (n > 2) {
                return fibonacci(n - 1) + fibonacci(n - 2);     //递归调用
            }
            return -1;              //如果输入错误的n，一律返回-1
        }

这种实现方法最简单，也是很容易就能想到的。但是效率太低了，当n>=40时，你会发现计算时间明显变长，当n接近50时，idea运行窗口等了半天才反应过来。  
注意：由于int的取值范围有限，最大值为 （2^32）-1 = 2147483647，当n>46的时候，会发生取值范围溢出的情况，所以这里如果想要验证n>46时的计算耗时情况，请将返回值类型int改为long。 例如第2种方法。就将int改为了long。

**2.通过for循环的方式实现**

public static long fibonacci2(int n) {
            if (n < 1) {
                return -1;
            }
            if (n ==1 || n == 2) {
                return 1;
            }
    
            long a =1l, b= 1l, c =0l;		//定义三个long类型整数
            for (int i = 0; i < n - 2; i++) {
                c = a + b;			//第3个数的值等于前两个数的和
                a = b;			//第2个数的值赋值给第1个数
                b = c;			//第3个数的值赋值给第2个数
            }
            return c;
        }

这种方法相比第1中，明显计算速度提高了不是一点两点，哪怕n>10000，都能瞬间完成计算。

**3.通过for循环和数组的方式实现**  
这种实现方式，其实和第2种实现方式类似，只不过把数据都放到了数组里，可以取出斐波那契数列的第1个一直到第n个的数值。  
同样，这里采用了long类型，防止溢出。

public static long fibonacci3(int n) {
            if (n < 1) {
                return -1;
            }
            if (n == 1 || n == 2) {
                return 1;
            }
    
            long[] arr = new long[n];
            arr[0] = arr[1] = 1;		//第一个和第二个数据特殊处理
            for (int i = 2; i < n; i++) {		
                arr[i] = arr[i -2] + arr[i - 1];    
            }
    
    		//可以得到整个的数列数据 仅n>2
    		System.out.println("数组内容：" + Arrays.toString(arr));
    
            return arr[n - 1];
        }

OK，到这里java实现斐波那契数列的三种写法就全部写完了，如果大家还有其他方法，欢迎交流~