您的位置 首页 > 数码极客

如何计算斐波那契数列——python计算斐波那契数列前20项!

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“ 兔子数列 ”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以 递推 的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)。

本文介绍斐波那契数列的三种实现,时间复杂度分别为O(2**N),O(N), O(logN)

递归实现

public static int getFib(int n){ if (n < 1) { return 0; } else if(n == 1 || n ==2){ return 1; }else{ return getFib(n - 1) + getFib(n - 2); } }

递归存在的问题就是会重复计算很多值,以5为例,这里的3、2、1都会计算多次,浪费很多资源,我们可以把前面的结果存起来,这样就不需要重复计算前面的值了,也就是O(N)的实现。

O(N)的实现

public static int getFib(int n){

if (n < 1) {

return 0;

} else if(n == 1 || n ==2){

return 1;

}else{

int tmp = 0, res = 1, pre = 1;

for(int i = 3; i <= n; i++){

tmp = res;

res = res + pre;

pre = tmp;

}

return res;

}

}

这里是用变量来存储中间的值,也可以使用一个数组把中间结果全部都存储起来,这样就可以得到整个数列的值了。这个也是很多动态规划使用的方法,先写出暴力求解的方法,再通过中间变量修改成动态规划。

O(logN)

logN的实现主要是第N的值直接可以通过矩阵乘法算出来。

所以只要计算出矩阵的n-2次方就可以计算出第N项的值了。怎么把一个矩阵的n次方在logN的时间内算出来了。

这里以整数为例,假设求10的64次方,假如一次一次的剩是需要剩64次的,时间复杂度是O(N)。但是10**64 = 10**32 X 10**32,这里我们只需要算出10的32次方,32次方可以通过16次方算出来,8,4..2..1, 这样只需要计算6次就可以了。

public static int getFib(int n){ if (n < 1) { return 0; } else if(n == 1 || n ==2){ return 1; } else { int [][] base={{1,1},{1,0}}; int [][] res=matrixPower(base,n-2); return res[0][0]+res[1][0]; } } //递归版本 public static int[][] matrixPower(int[][] m,int p){ if(p==0) { return null; } else if (p==1) { return m; } else { //这里也可以修改成非递归的方式 int[][] res=matrixPower(m, p/2); //如果是偶数次方,直接就是2分之次方相乘 res = muliMatrix(res,res); //如果是奇数还需要再乘个数 if(p % 2 == 1){ res = muliMatrix(res, m); } return res; } } //非递归版本 public static int[][] matrixPower(int[][] m,int p){ int[][] res = new int[m.length][m[0].length]; for (int i = 0; i < res.length; i++) { res[i][i] = 1; } int[][] tmp = m; for (; p != 0; p = p/2) { if (p % 2 == 1) { res = muliMatrix(res, tmp); } tmp = muliMatrix(tmp, tmp); } return res; } public static int[][] muliMatrix(int[][] m1, int[][] m2) { int[][] res = new int[m1.length][m2[0].length]; for (int i = 0; i < m1.length; i++) { for (int j = 0; j < m2[0].length; j++) { for (int k = 0; k < m2.length; k++) { res[i][j] += m1[i][k] * m2[k][j]; } } } return res; }

希望对大家有所帮助,有帮助记得点赞哦!可以关注下,后面持续分享编程类的文章,谢谢!

责任编辑: 鲁达

1.内容基于多重复合算法人工智能语言模型创作,旨在以深度学习研究为目的传播信息知识,内容观点与本网站无关,反馈举报请
2.仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证;
3.本站属于非营利性站点无毒无广告,请读者放心使用!

“如何计算斐波那契数列,python计算斐波那契数列前20项,如何计算斐波那契数列某一项的整除问题,如何计算斐波那契数列的时间复杂度,如何计算斐波那契数列0.23”边界阅读