Java 实现斐波那契数列
斐波那契数列是一个经典的数学序列，其中每个数字是前两个数字的和，以下是几种在 Java 中实现斐波那契数列的方法：
（图片来源网络，侵删）
递归实现（简单但效率低）
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
int n = 10;
System.out.println("斐波那契数列第 " + n + " 项是: " + fibonacci(n));
}
}
迭代实现（高效）
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int fib = 1;
int prevFib = 1;
for (int i = 2; i < n; i++) {
int temp = fib;
fib += prevFib;
prevFib = temp;
}
return fib;
}
public static void main(String[] args) {
int n = 10;
System.out.println("斐波那契数列第 " + n + " 项是: " + fibonacci(n));
}
}
使用数组存储中间结果（空间换时间）
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int[] fibArray = new int[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n; i++) {
fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
return fibArray[n];
}
public static void main(String[] args) {
int n = 10;
System.out.println("斐波那契数列第 " + n + " 项是: " + fibonacci(n));
}
}
打印斐波那契数列前n项
public class Fibonacci {
public static void printFibonacci(int n) {
int t1 = 0, t2 = 1;
System.out.print("前 " + n + " 项斐波那契数列: ");
for (int i = 1; i <= n; ++i) {
System.out.print(t1 + " ");
int sum = t1 + t2;
t1 = t2;
t2 = sum;
}
}
public static void main(String[] args) {
int n = 10;
printFibonacci(n);
}
}
使用BigInteger处理大数
import java.math.BigInteger;
public class Fibonacci {
public static BigInteger fibonacci(int n) {
if (n <= 1) {
return BigInteger.valueOf(n);
}
BigInteger fib = BigInteger.ONE;
BigInteger prevFib = BigInteger.ONE;
for (int i = 2; i < n; i++) {
BigInteger temp = fib;
fib = fib.add(prevFib);
prevFib = temp;
}
return fib;
}
public static void main(String[] args) {
int n = 100;
System.out.println("斐波那契数列第 " + n + " 项是: " + fibonacci(n));
}
}
性能比较
- 递归方法：简单直观，但时间复杂度为O(2^n)，效率低，不适合大n值
- 迭代方法：时间复杂度O(n)，空间复杂度O(1)，是最优解
- 数组方法：时间复杂度O(n)，空间复杂度O(n)，适合需要多次访问的情况
- BigInteger方法：可以处理非常大的数，但计算速度较慢
对于大多数实际应用场景,迭代方法是最好的选择。
（图片来源网络，侵删）
