一、题目描述
大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项。
斐波那契数列满足如下
二、解题思路
2.1 普通处理方式
使用递归直接计算
int fib(int n) {
if (n == 1 || n == 2) return 1;
return fib(n - 1) + fib(n - 2);
}
这种方法是学习软件开发或者算法时最原始,最容易理解的方法。但是缺点很多
- 1、未对n进行参数检查;
- 2、性能差,数据量比较大的时候,计算很慢;
- 3、返回结果时int类型,能支持的n很小;
2.2 分析优化及处理
如果使用递归求解,会重复计算一些子问题。例如,计算 f(4) 需要计算 f(3) 和 f(2),计算 f(3) 需要计算 f(2) 和 f(1),可以看到 f(2) 被重复计算了。
递归是将一个问题划分成多个子问题求解。动态规划也是如此,但是动态规划会把子问题的解缓存起来,从而避免重复求解子问题。
public int Fibonacci(int n) {
if (n <= 1)
return n;
int[] fib = new int[n + 1];
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = fib[i - 1] + fib[i - 2];
return fib[n];
}
考虑到第 i 项只与第 i-1 和第 i-2 项有关,因此只需要存储前两项的值就能求解第 i 项,从而将空间复杂度由 O(N) 降低为 O(1)。
尤其时n数值比较大时,可以降低很多内存占用,避免栈溢出。
public int Fibonacci(int n) {
if (n <= 1)
return n;
int pre2 = 0, pre1 = 1;
int fib = 0;
for (int i = 2; i <= n; i++) {
fib = pre2 + pre1;
pre2 = pre1;
pre1 = fib;
}
return fib;
}
三、再优化,支持更大的参数n和更大的返回结果
由于int只有4个字节,能处理的n比较小,因此可以考虑用long、BigInteger处理
3.1 long版本
对n进行参数检查,由于long是8个字节,要考虑到返回的结果不能超过long的最大值。
public long fibLongPlus(int n) {
if (n <= 0) {
return 0;
}
if (n >= 92) {
throw new IllegalArgumentException("n is too large to compute within available memory");
}
// base case
long a = 0;
long b = 1;
// 状态转移
long temp;
for (int i = 2; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return b;
}
3.2 BigInteger版本
BigInteger可以支持更大的n,支持更大的结果返回
public BigInteger fibPlus(int n) {
if (n <= 0) {
return BigInteger.ZERO;
}
// 考虑到内存和性能,n最大限制为1_000_000
if (n > 1_000_000) {
throw new IllegalArgumentException("n is too large to compute within available memory");
}
// base case
BigInteger pre1 = BigInteger.ZERO;
BigInteger pre2 = BigInteger.ONE;
// 状态转移
BigInteger fib;
for (int i = 2; i <= n; i++) {
fib = pre1.add(pre2);
pre1 = pre2;
pre2 = fib;
}
return pre2;
}
四、再优化,使用`矩阵快速幂`提升计算性能
4.1 矩阵快速幂实现
/**
* 计算两个2x2矩阵的乘积。
*
* @param a 第一个矩阵
* @param b 第二个矩阵
* @return 两个矩阵的乘积
*/
private BigInteger[][] matrixMultiply(BigInteger[][] a, BigInteger[][] b) {
// 创建结果矩阵
BigInteger[][] result = new BigInteger[2][2];
// 遍历结果矩阵的行
for (int i = 0; i < 2; i++) {
// 遍历结果矩阵的列
for (int j = 0; j < 2; j++) {
// 初始化结果矩阵的当前元素为0
result[i][j] = BigInteger.ZERO;
// 遍历乘法的中间索引
for (int k = 0; k < 2; k++) {
// 执行矩阵乘法
result[i][j] = result[i][j].add(a[i][k].multiply(b[k][j]));
}
}
}
// 返回结果矩阵
return result;
}
/**
* 使用矩阵快速幂算法计算矩阵的n次幂。
*
* @param matrix 要计算幂的矩阵
* @param n 幂次
* @return 矩阵的n次幂的结果
*/
private BigInteger[][] matrixPower(BigInteger[][] matrix, int n) {
BigInteger[][] result = new BigInteger[][]{
// 初始化结果矩阵为单位矩阵
{BigInteger.ONE, BigInteger.ZERO},
{BigInteger.ZERO, BigInteger.ONE}
};
// 当幂次大于0时循环
while (n > 0) {
// 如果幂次是奇数
if ((n & 1) == 1) {
// 将结果矩阵乘以原矩阵
result = matrixMultiply(result, matrix);
}
// 将原矩阵平方
matrix = matrixMultiply(matrix, matrix);
// 幂次减半
n >>= 1;
}
// 返回结果矩阵
return result;
}
/**
* 使用矩阵快速幂算法计算斐波那契数列的第n项。
*
* @param n 斐波那契数列的项数
* @return 斐波那契数列的第n项
*/
public BigInteger fibPlus(int n) {
// 如果n小于等于0,返回0
if (n <= 0) {
return BigInteger.ZERO;
}
// 限制n大小
if(n > 1_000_000_0){
throw new IllegalArgumentException("n is too large to compute within available memory");
}
// 创建斐波那契变换矩阵
BigInteger[][] fibMatrix = new BigInteger[][]{
{BigInteger.ONE, BigInteger.ONE},
{BigInteger.ONE, BigInteger.ZERO}
};
// 计算斐波那契变换矩阵的n-1次幂
BigInteger[][] result = matrixPower(fibMatrix, n - 1);
// 返回结果矩阵的第一行第一列元素,即斐波那契数列的第n项
return result[0][0];
}
4.2 单元测试
4.2.1 测试小数据量
@Test
public void test_fibPlus() {
for (int i = 0; i < 100; i++) {
// 设置要计算的斐波那契数列的项数
int n = i;
// 输出斐波那契数列的第n项
System.out.println("Fibonacci(" + n + ") = " + fibPlus(n));
}
}
输出结果
Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34
Fibonacci(10) = 55
Fibonacci(11) = 89
Fibonacci(12) = 144
Fibonacci(13) = 233
Fibonacci(14) = 377
Fibonacci(15) = 610
Fibonacci(16) = 987
Fibonacci(17) = 1597
Fibonacci(18) = 2584
Fibonacci(19) = 4181
Fibonacci(20) = 6765
Fibonacci(21) = 10946
Fibonacci(22) = 17711
Fibonacci(23) = 28657
Fibonacci(24) = 46368
Fibonacci(25) = 75025
Fibonacci(26) = 121393
Fibonacci(27) = 196418
Fibonacci(28) = 317811
Fibonacci(29) = 514229
Fibonacci(30) = 832040
Fibonacci(31) = 1346269
Fibonacci(32) = 2178309
Fibonacci(33) = 3524578
Fibonacci(34) = 5702887
Fibonacci(35) = 9227465
Fibonacci(36) = 14930352
Fibonacci(37) = 24157817
Fibonacci(38) = 39088169
Fibonacci(39) = 63245986
Fibonacci(40) = 102334155
Fibonacci(41) = 165580141
Fibonacci(42) = 267914296
Fibonacci(43) = 433494437
Fibonacci(44) = 701408733
Fibonacci(45) = 1134903170
Fibonacci(46) = 1836311903
Fibonacci(47) = 2971215073
Fibonacci(48) = 4807526976
Fibonacci(49) = 7778742049
Fibonacci(50) = 12586269025
Fibonacci(51) = 20365011074
Fibonacci(52) = 32951280099
Fibonacci(53) = 53316291173
Fibonacci(54) = 86267571272
Fibonacci(55) = 139583862445
Fibonacci(56) = 225851433717
Fibonacci(57) = 365435296162
Fibonacci(58) = 591286729879
Fibonacci(59) = 956722026041
Fibonacci(60) = 1548008755920
Fibonacci(61) = 2504730781961
Fibonacci(62) = 4052739537881
Fibonacci(63) = 6557470319842
Fibonacci(64) = 10610209857723
Fibonacci(65) = 17167680177565
Fibonacci(66) = 27777890035288
Fibonacci(67) = 44945570212853
Fibonacci(68) = 72723460248141
Fibonacci(69) = 117669030460994
Fibonacci(70) = 190392490709135
Fibonacci(71) = 308061521170129
Fibonacci(72) = 498454011879264
Fibonacci(73) = 806515533049393
Fibonacci(74) = 1304969544928657
Fibonacci(75) = 2111485077978050
Fibonacci(76) = 3416454622906707
Fibonacci(77) = 5527939700884757
Fibonacci(78) = 8944394323791464
Fibonacci(79) = 14472334024676221
Fibonacci(80) = 23416728348467685
Fibonacci(81) = 37889062373143906
Fibonacci(82) = 61305790721611591
Fibonacci(83) = 99194853094755497
Fibonacci(84) = 160500643816367088
Fibonacci(85) = 259695496911122585
Fibonacci(86) = 420196140727489673
Fibonacci(87) = 679891637638612258
Fibonacci(88) = 1100087778366101931
Fibonacci(89) = 1779979416004714189
Fibonacci(90) = 2880067194370816120
Fibonacci(91) = 4660046610375530309
Fibonacci(92) = 7540113804746346429
Fibonacci(93) = 12200160415121876738
Fibonacci(94) = 19740274219868223167
Fibonacci(95) = 31940434634990099905
Fibonacci(96) = 51680708854858323072
Fibonacci(97) = 83621143489848422977
Fibonacci(98) = 135301852344706746049
Fibonacci(99) = 218922995834555169026
4.2.2 测试大数据量
n=1_000_000 时很快,不到1秒。
再大一些(比如n=1_000_000_0)的时候,计算就比较慢了
- 测试 1_000_000_0
@Test
public void test_fibPlus() {
int n = 1_000_000_0;
System.out.println("Fibonacci(" + n + ") = " + fibPlus(n));
}
测试大数结果(结果太长了,发布不了,就不展示了,感兴趣的可以自己写UT验证下)
Fibonacci(10000000) = 1129834378225399760317063637745866372944837190489040881513577643245534731167933137524219777458247745488503329541529737982917618975273928543637913029320511080393607160947067632276156828424897006419736620682555596286851200164878524757142799029763435331462543748832574728019186803442609337613122078718093224952473835489645047696411558824438103526892104885863028289108.............
标签:BigInteger,数列,int,矩阵,斐波,000,Fibonacci,那契
From: https://blog.csdn.net/yyp0719/article/details/141186667