查找斐波纳契数列中第 N 个数

文章目录[隐藏]

题目

查找斐波纳契数列中第 N 个数

很多朋友看到“纳契”是不是很开心,这个 纳契 可不是“纳妾”,呵呵呵

所谓的斐波纳契数列是指

前 2 个数是 0 和 1 。

第 i 个数是第 i-1 个数和第 i-2 个数的和。

斐波纳契数列的前 10 个数字是

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

示例

给定 1,返回 0

给定 2,返回 1

给定 10,返回 34

分析

简单的想法就是递归,规则很明显了,但是有没有更好的解法呢?

 

Just Try

请你自动动手试一下:在线编程环境

想想有没有其他思路?

想想时间和空间复杂度,能否优化一下

真的做不到么?

let you think, think makes you happy!

 

参考答案

思路:递归

代码很简单,看下就会了

function fibonaqi(n){
  if(n==1) return 0;
  if(n==2) return 1;
  return fibonaqi(n-1)+fibonaqi(n-2)
}
function main(param) {
  console.show(fibonaqi(param))
}
main(10)

PS:思考一下性能问题,试试把入参改成100? 是不是会卡死一段时间? 经我测试入参在45的时候还可以勉强算出来。

思路:动态规划

看到一篇博客介绍动态规划,优化上面递归的方法,new 了一个长度为 n+1 的数组,用于存放 f(0) 到 f(n) 这 n+1 个状态的计算结果。实测效果提升显著。

动态规划就是:将原问题拆解成若干子问题,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。

let temp = []
function fibonaqi(n){
  if(n==1) return 0;
  if(n==2) return 1;
  if(!temp[n]){
    temp[n] = fibonaqi(n-1)+fibonaqi(n-2)
  }
  return temp[n]
}
function main(...param) {
  console.show("参数:" + param, "结果:" + JSON.stringify(fibonaqi(param)))
  testPerformance(fibonaqi, param)
}
main(40);

思路:正向计算

比如让我计算第10个,我就挨个计算前10个,然后返回,因为正好和斐波那契数列的规则相似,所以一层循环就可以计算完。

function fibonaqi(n){
  let arr=[0,1]
  for(let i=2;i<n;i++){
    arr[i] = arr[i-1] + arr[i-2]
  }
  return arr[n-1]
}
function main(param) {
  console.show(fibonaqi(param))
}
main(10)

代码复制到在线编程环境试一下:在线编程环境

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 查找斐波纳契数列中第 N 个数

赞 (2) 打赏

评论 0

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏