首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：1270994 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 的数列
数据范围：
要求：空间复杂度 ，时间复杂度 ，本题也有时间复杂度 的解法


输入描述:
一个正整数n


输出描述:
输出一个正整数。
示例1

输入

4

输出

3

说明

根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。
示例2

输入

1

输出

1
示例3

输入

2

输出

1
算法知识视频讲解
添加回答
推荐
fanhk头像 fanhk
c++动态规划版 
class Solution {
public:
    int Fibonacci(int n) {
        int f = 0, g = 1;
        while(n--) {
            g += f;
            f = g - f;
        }
        return f;
    }
};

编辑于 2015-06-19 17:21:55 回复(110)
Javascript
让诺头像 让诺

JS

function Fibonacci(n)
{
    if (n < 0 || Math.floor(n) !== n) {
          return -1;
        }
        if (n === 1 || n === 2) {
          return 1;
        }
        const cache = [1, 1];
        for (let i = 3; i < n; i++) {
          const temp = cache[1] + cache[0];
          cache[0] = cache[1];
          cache[1] = temp;
        }
        return cache[0] + cache[1];
}
module.exports = {
    Fibonacci : Fibonacci
};
发表于 2022-05-25 11:48:50 回复(0)
Javascript
纯海之蓝头像 纯海之蓝
function Fibonacci(n)
{
    // write code here
    let l = 0;
    let res = 0;
    let r = 1
    let arr = []
    for(let i=0; i<n; i++) {
        if(i == 0) {
          arr.push(1)
        } else {
          res = l + r
          l = r
          r = res
          arr.push(res)
        }
    }
    return arr[n - 1]
}
module.exports = {
    Fibonacci : Fibonacci
};
发表于 2022-04-02 10:19:21 回复(0)
Javascript
lsh108头像 lsh108
function Fibonacci(n)
{ 
  var arr = [0,1,1]
  for(let i=3;i<n+1;i++){
      arr[i] = arr[i-1] + arr[i-2]
  }
   return arr[n]
}
发表于 2021-10-28 13:05:52 回复(0)
Javascript
星辰大地头像 星辰大地
function Fibonacci(n){
    if(n==2 || n==1) return 1
    // 方法一：使用递归
    return Fibonacci(n-1)+Fibonacci(n-2);
    // 方法二：动态规划使用数组
//     let dp = [];
//     let i =3;
//     dp[1] = 1;
//     dp[2] = 1;
//     while(i<=n){
//         dp[i] = dp[i-1]+dp[i-2];
//         i++;
//     }
//     return dp[n];
    // 方法三：动态规划，
//     let a= 1, b=1, i= 1;
//     for(i=1;i<n-1;i++){
// //         a,b = b, a+b;
//         let t=0;
//         t = a;
//         a = b;
//         b = t+b;
//     }
//     return b;
}

module.exports = {Fibonacci}
发表于 2021-10-16 17:04:05 回复(0)
Javascript
println()头像 println() 
function Fibonacci(n)
{
    // write code here
    if(n == 0) return 0
    if(n <=2){
        return 1
    }
    return Fibonacci(n-2)+Fibonacci(n-1)
}
module.exports = {
    Fibonacci : Fibonacci
};

发表于 2021-09-22 11:29:16 回复(0)
Javascript
雅君头像 雅君 
  if (n == 0) {
        return 0
    } else if (n == 1 || n == 2) {
        return 1
    }  else   {
        return Fibonacci(n-1) + Fibonacci(n-2)
    }

发表于 2021-09-05 17:45:53 回复(0)
Javascript
牛客477650639号头像 牛客477650639号
果然直接递归份数很低 
function Fibonacci(n)
{
    // write code here
    if(n === 0) return 0;
    if(n === 1) return 1;
    
    return Fibonacci(n-1) + Fibonacci(n-2)
}
module.exports = {
    Fibonacci : Fibonacci
};


发表于 2021-08-31 16:50:09 回复(1)
Javascript
夜寻极光。头像 夜寻极光。
递归注意点就是要有出口。
function Fibonacci(n)
{
    // write code here
    if(n==0){
        return 0;
    }
    if(n==1){
        return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2)
}

发表于 2021-08-19 13:35:27 回复(0)
JavaScript
gai溜子头像 gai溜子
function Fibonacci(n,a=1,b=1)
{
    // write code here
    return n <= 0 ? 0 : n <= 2 ? b : Fibonacci(n-1,b,a+b);
}
发表于 2021-06-01 15:20:35 回复(0)
JavaScript
牛客65959761号头像 牛客65959761号 
function Fibonacci(n)
{
    // write code here
    let ret = [0, 1];
    for(let t = 2; t <= n; t++) {
      ret[t] = ret[t-2] + ret[t-1];
    }
    return ret[n];
}

发表于 2021-04-23 15:00:32 回复(0)
JavaScript
王志晗头像 王志晗 
function Fibonacci(n)
{
    // write code here
    let a = 0;
    let b = 1;
    for(let i=1;i<=n;i++){
        a = a + b;
        b = a - b;
    }
    return a;
}

发表于 2021-04-19 15:18:19 回复(0)
JavaScript
可以教我摸鱼嘛头像 可以教我摸鱼嘛 
function Fibonacci(n) {
    // write code here
    let a = [0, 1, 1];

    if (n >= 3) {

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

            a[i] = a[i - 1] + a[i - 2];

        }

    }
        return a[n]
}
用数组暂存数值，递归耗时
发表于 2021-04-01 23:08:52 回复(0)
JavaScript
白下布衣头像 白下布衣
高效递归
这题不一定要写快速算法，用缓存机制一样可以用递归高性能解决 
 // 一对多递归要使用缓存机制来加速
const map = new Map();

function Fibonacci(n) {
  if (n > 1) {
      let result = map.get(n);
      if (result) return result;
      
      result = Fibonacci(n - 1) + Fibonacci(n - 2);
      
      map.set(n, result);
      return result;
  } else {
    return n;
  }
}

module.exports = {
  Fibonacci: Fibonacci,
};


编辑于 2021-03-30 12:58:49 回复(0)
JavaScript
splwany头像 splwany 
function Fibonacci(n)
{
    let [a, b] = [0, 1];
    while (n--) {
        b += a;
        a = b - a;
    }
    return a;
}

编辑于 2021-03-29 14:50:59 回复(0)
JavaScript
IPzzzi头像 IPzzzi
function Fibonacci(n)
{
    var arr=[];
    for(var i=2;i<=39;i++){
        arr[0]=0;
        arr[1]=1;
        arr.push(arr[i-1]+arr[i-2]);
    }
    return arr[n];
}
module.exports = {
    Fibonacci : Fibonacci
};
发表于 2021-03-04 22:03:09 回复(0)
JavaScript
阿b内推工具人头像 阿b内推工具人
js暴力解法：

1.思路：斐波那锲数列公式f(n) = f(n-1)+f(n-2);
  • f(0) = 0;
  • f(1) = 1;
  • f(2) = f(1) + f(0) = 1;
  • f(3) = f(2) + f(1) = 2；
  • f(4) = f(3) + f(2) = 3;
 规律  ：n< 2   结果为n，n>=2    f(n) = f(n-1)+f(n-2)
2.代码 
function Fibonacci(n)
{
    // write code here
    if(n == 0){return 0}
    else if(n <= 2 ){return 1}
    else return Fibonacci(n-1)+Fibonacci(n-2);
}




编辑于 2021-02-01 23:02:08 回复(0)
JavaScript
别卷啦！头像 别卷啦！
尾递归 
function Fibonacci(n)
{
    // write code here
    const fn = (n,temp1 =1, temp2 =1) => {
        if(n<=1) return n 
        if(n===2) return temp2
        return fn(n-1, temp2,(temp1+temp2))
    }
    return fn(n)
}


发表于 2020-12-11 21:05:48 回复(0)
JavaScript
白植程头像 白植程
var fibonacciList = [0, 1];
function Fibonacci(n) {
    // write code here
    let i;
    while (fibonacciList.length <= n) {
        i = fibonacciList.length;
        fibonacciList[i] = fibonacciList[i - 1] + fibonacciList[i - 2];
    }

    return fibonacciList[n];
}
发表于 2020-10-14 16:55:09 回复(0)
JavaScript
咚咚咚，开门，查水表头像 咚咚咚，开门，查水表 
function Fibonacci(n)
{
    let arr = [0, 1]
    for(let i = 2; i <= n; i++){
        arr.push(arr[i-1] + arr[i-2])
    }
    return arr[n]
}
module.exports = {
    Fibonacci : Fibonacci
};

编辑于 2020-09-13 14:48:09 回复(0)
JavaScript
萨弗拉斯的挽歌头像 萨弗拉斯的挽歌 
function Fibonacci(n)
{
    // write code here
    //f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2) 从第三项开始，所在项为前两项之和
    var num0 = 0;
    var num1 = 1;
    var FArray = [0,1]
    for(let i=2;i<=39;i++){
        FArray.push(FArray[i-1]+FArray[i-2]);
    }
    return FArray[n]
    
}
module.exports = {
    Fibonacci : Fibonacci
};

发表于 2020-08-22 11:01:08 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 数组 快速幂 递归
来自：寻找时间黑客在线编程大...
难度：
56条回答 205345浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号