java实现斐波那契数列的三种⽅法
Java实现斐波那契数列的三种⽅法
什么是斐波那契数列
这⾥借⽤⼀下度娘的⼀段话：斐波那契数列（Fibonacci sequence），⼜称黄⾦分割数列、因数学家列昂纳多·斐波那契
（Leonardoda Fibonacci）以兔⼦繁殖为例⼦⽽引⼊，故⼜称为“兔⼦数列”，指的是这样⼀个数列：1、1、2、3、5、8、13、
java的tostring方法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("数组内容：" + String(arr));
return arr[n - 1];
}
OK，到这⾥java实现斐波那契数列的三种写法就全部写完了，如果⼤家还有其他⽅法，欢迎交流~

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。