Fibonacci数列的定义如下(看百度百科):
F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)
传统方法
首先先看一个传统的基于递归的实现:
public static int fibonacci1(int i) {
if (i < 0) {
throw new IllegalArgumentException("The number should be not less than 0");
}
if (i < 2) {
return i;
}
return fibonacci1(i - 1) + fibonacci1(i - 2);
}
它有几个明显的问题:
1. 占用空间大
每一次递归的跟进,都会在调用栈上压入当前方法的栈帧。如果递归层次太深就会发生 java.lang.StackOverflowError 错误。例如在我的机器上,当调用 fibonacci1(100000) 时就会发生这种错误(应该更早就发生了溢出了)。
2. 效率低
除了占用空间大,效率低也是一个问题。效率低体现在几方法:
- 方法调用
太多的方法调用本向效率就不高
- 重复多
存在太多的重复计算是影响效率的一个方面。例如fibonacci(4)的计算,当计算fibonacci(5)时需要计算,计算fibonacci(6)的时候又要被计算一次。并且这种重复会产生链式反应,因为每一次的计算又是一次递归。
3. 结果不可靠
最后一个问题就是结果不可靠。fibonacci 数列的值增长很快,很快就能达到 java 中 int 能表示的最大值 (fibonacci(46)),并且也很快就能达到long能表达的数值的上限。也就是说上述实现,最多能计算到46,到47的结果就是不可靠的。
解决方案
使用循环
先来解决问题1和问题2。
通常,每一个递归实现都会有一个相应的循环实现可以替代。可使用循环替代,最关键是每次记录两个值:上个值和上上个值,然后每迭代一次将这两个值更新,如下fibonacci2(int):
public static int fibonacci2(int n){
if (n < 0) {
throw new IllegalArgumentException("The number should be not less than 0");
}
if (n < 2) {
return n;
}
int f0 = 0;
int f1 = 1;
for(int i = 2;i<=n;i++){
int f = f0 + f1;
f0 = f1;
f1 = f;
}
return f1;
}
可以使用以下测试示例比较 fibonacci1(int) 和 fibonacci2(int) 的效率:
for(int i = 0;i< 47;i++){
System.out.println(fibonacci1(i));
//System.out.println(fibonacci2(i));
}
一开始的时候,两者都表现的非常快,但是到后来 fibonacci1(int) 出结果的速度越来越慢,而 fibonacci2(int) 的表现还是一如即往。
使用预定值
如果某些值是频繁读取的,则可以预先把结果存到,例如某个数组里,以后就从数组里读值了。例如:
/**
* 构造从 0 - n 对应的 fibonacci 值的数组
*/
public static int[] fibonacci(int n) {
int[] fArray = new int[n+1];
fArray[0] = 0;
fArray[1] = 1;
int length = fArray.length;
for (int i = 2; i < length; i++) {
fArray[i] = fArray[i - 1] + fArray[i - 2];
}
return fArray;
}
这里根据输入的值 n 构造了每个值对应的 fibonacci 值。以后要想取某个值对应的数列,只要从返回的数组里取即可:
int[] fibonacci = fibonacci(46);
for (int i = 0; i < 47; i++) {
System.out.println(fibonacci[i]);
}
结果的正确
上面说了,当计算到 47 的 fibonacci 值时,结果已经超出了 java 的 int 表示的范围。 方法1就是把int换成long,例如:
public static long fibonacci2(int n){
if (n < 0) {
throw new IllegalArgumentException("The number should be not less than 0");
}
if (n < 2) {
return n;
}
long f0 = 0;
long f1 = 1;
for(int i = 2;i<=n;i++){
long f = f0 + f1;
f0 = f1;
f1 = f;
}
return f1;
}
这次表现好一些,到93才开始出问题。
要保证方法本身的正确性,有两个选择:要么限制可计算的数字的上限;要不扩展类型,让结果可以无限制的大。
限制参数
如果结果是int型,则上限是46:
public static int fibonacci2(int n){
if (n < 0 || n > 46 ) {
throw new IllegalArgumentException("The number should be between 0-46");
}
if (n < 2) {
return n;
}
int f0 = 0;
int f1 = 1;
for(int i = 2;i<=n;i++){
int f = f0 + f1;
f0 = f1;
f1 = f;
}
return f1;
}
如果结果是long型,则上限是92:
public static long fibonacci2(int n){
if (n < 0 || n > 92) {
throw new IllegalArgumentException("The number should be between 0-92");
}
if (n < 2) {
return n;
}
long f0 = 0;
long f1 = 1;
for(int i = 2;i<=n;i++){
long f = f0 + f1;
f0 = f1;
f1 = f;
}
return f1;
}
无上限结果
可以使用BigInteger来产生无限的整数,以避免int或long的上限的问题:
public static BigInteger fibonacci3(int n){
if (n < 0) {
throw new IllegalArgumentException("The number should be a positive number");
}
if (n < 2) {
return BigInteger.valueOf(n);
}
BigInteger f0 = BigInteger.valueOf(0);
BigInteger f1 = BigInteger.valueOf(1);
for(int i = 2;i<=n;i++){
BigInteger f = f0.add(f1);
f0 = f1;
f1 = f;
}
return f1;
}
为了提交效率,可能可以使用分段计算的方式:当n<47时使用基于int的计算方法;当n<93时可以使用基于long的计算方法;否则使用基于BigInteger的计算方法。
相关推荐
利用数组计算斐波那契数列
android Handler子线程计算斐波那契数列
计算斐波那契数列,C#
本教程将向您展示如何使用Java编写代码来计算斐波那契数列的第 n 个数字。我们将涵盖循环和递归两种不同的方法,以帮助您理解常用的编程知识点,并逐步解释代码的思路和逻辑斐波那契数列是一个常见的数学序列,在...
本文档提供了两种计算斐波那契的C++代码函数,供网友使用,。主要讲cpp添加到新建项目中运行
汇编语言,两种方法计算斐波那契数列的前22项,斐波那契数列,分别用两种方法:递归调用,普通循环加法,使用DOSBox验证
C语言计算斐波那契数列(Fibonacci sequence), vc 6++可运行源码
labview通过移位寄存器计算斐波那契数列的第n项
linux多线程程序实验,用不同线程完成一个矩阵乘法,以及子进程计算斐波那契数列,父进程输出结果
通过分别用递归法、迭代法、矩阵法以及公式法对斐波那契数列的C++算法进行分析,最终总结并得出计算斐波那契数列在时间效率层面上最优的算法为矩阵法,但综合考虑下来的最优算法为迭代法。
F(N)=F(N-1)+F(N-2) // ...自写的c\c++代码, 使用数组实现加法计算器来计算费波那西数列. 通过设定数组长度, 通过编译后, 可以计算费氏数列的任意一项数值的计算. 如果有问题,可以发邮件和我交流 :) 893222955@qq.com
MATLAB appdesigner设计计算斐波那契数列的笔记
利用Matlab程序计算斐波那契数列的前一百项,输出前100项
递归方法 def fibonacci(n): if n <= 1: return n else: return fibonacci(n-1) + fibonacci(n-2) n = int(input("请输入要计算的斐波那契数列的项数:")) print("斐波那契数列的第", n, "项为:", fibonacci(n)) 2...
Fibonacci数列,用c++编写的,非递归的函数调用求Fibonacci数列的第n项
编写一个Java程序,用于输出Fibonacci数列的前20项。
用VS2010写的,最好也用VS2010打开 用VS2010写的,最好也用VS2010打开 用VS2010写的,最好也用VS2010打开
编写一个函数,根据给定的正整数n,返回斐波那契数列中第n个数字的值。 斐波那契数列是一个数列,每个数字都是前两个数字的和。数列的前两个数字是0和1。数列的前几项是:0, 1, 1, 2, 3, 5, 8, 13, 21, ...
利用递归数列求解著名的Fibonacci数列的各项,用户可自定义输入要求的第n项,输入后即可求出从0到n每一项Fibonacci的值。
//计算2的n次方,n > 0。 const char *power2(unsigned n); //计算斐波那契数列第n项,n > 0。 const char * fib(unsigned n); //计算n的阶乘,n > 0。 const char * fac(unsigned n);