首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：45409 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
用 JavaScript 实现斐波那契数列函数,返回第n个斐波那契数。 f(1) = 1, f(2) = 1 等
算法知识视频讲解
添加回答
HTML/CSS/JavaScript
爸爸a头像 爸爸a 
function fibonacci(n) {
    return n <= 2 ? 1 : fibonacci(n-1) + fibonacci(n-2)
}
我的更简单
发表于 2023-05-22 14:44:54 回复(0)
HTML/CSS/JavaScript
HH123_3头像 HH123_3 
function fibonacci(n) {
    let f1 =1 ,f2 = 1;
    for(let i = 3; i <= n; ++i) {
        [f1, f2] = [f2, f1+f2];
    }
    return f2;
}

发表于 2023-05-20 21:23:29 回复(0)
HTML/CSS/JavaScript
书山仰止头像 书山仰止 
function fibonacci(n) {
    if(n === 1 || n === 2) return 1;
    return fibonacci(n-2)+fibonacci(n-1);
}

发表于 2023-05-16 23:16:46 回复(0)
HTML/CSS/JavaScript
弓箭是谁的从前头像 弓箭是谁的从前
function fibonacci(n) {
    //先找出斐波那契数列的规律
    //1 1 2 3 5 8 13 21
   //写出关系
    if(n>2)
    {let nworth=fibonacci(n-1)+fibonacci(n-2)
        return nworth
    }
    if(n==1||n==2)
     {
    return 1
     }

        
}
发表于 2023-05-11 17:47:06 回复(0)
HTML/CSS/JavaScript
牛客205160422号头像 牛客205160422号
function fibonacci(n) {
  if(n==1|n==2){
    return 1
  }
  if(n>2){
   return  fibonacci(n-1)+fibonacci(n-2)
  }
  }
发表于 2023-04-10 15:19:30 回复(0)
HTML/CSS/JavaScript
一个反骨仔头像 一个反骨仔 
function fibonacci(n) {
    if (n < 3) {
        return 1;
    }
    let arr = [];
    arr[0] = 1;
    arr[1] = 1;
    for (let i = 2; i < n; i++) {
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n-1]
}

发表于 2022-09-03 21:58:35 回复(0)
HTML/CSS/JavaScript
牛客98748904号头像 牛客98748904号 
function fibonacci(n) {
    if(n==1||n==2){
        return 1
    }
    if(n>=3){
      return   fibonacci(n-2)+fibonacci(n-1)
    }

发表于 2022-08-09 16:46:13 回复(0)
HTML/CSS/JavaScript
牛客803673324号头像 牛客803673324号 
function fibonacci(n) {
    let a=1,b=1;
    while(n>2){
        [a,b,n] = [b,a+b,n-1];
    }
    return b;
}
发表于 2022-07-19 16:00:01 回复(0)
HTML/CSS/JavaScript
🌼🐔冇头像 🌼🐔冇 
//递推
function fibonacci(n) {
    fib = (cur, next, n) => n === 0 ? cur : fib(next, cur + next, n - 1)
    return fib(0, 1, n)
}

发表于 2022-07-13 22:47:38 回复(0)
HTML/CSS/JavaScript
liyfn头像 liyfn 
function fibonacci(n) {
        if (n === 0) return 0;
        if (n === 1) return 1;
        return fibonacci(n-2) + fibonacci(n - 1)
}

发表于 2022-06-23 21:24:40 回复(0)
HTML/CSS/JavaScript
希予头像 希予 
function fibonacci(n) {
    let arr = [1,1];
    for(let i = 2;i < n;++i){
        if(i % 2 === 0){
            arr[0] += arr[1];
        }else{
            arr[1] += arr[0]
        }
    }
    return n % 2 === 0 ? arr[1] : arr[0];
}
当动态规划做的...
发表于 2022-04-24 22:10:03 回复(0)
HTML/CSS/JavaScript
载梦覆星河头像 载梦覆星河

斐波那切数列-兔子序列

function fibonacci(n) {
    // 利用递归去做，当n = 1 和 n = 2,所对应的值都是1.
    if(n == 1 || n == 2 ) {
        return 1;
    } 
    从第三项开始，后面的值是前两项值的和，2 = f(3) = f(1) + f(2)  3 = f(4) =f(2) +f(3)
     return fibonacci(n-1) + fibonacci(n-2);    
}
发表于 2022-03-30 10:33:20 回复(0)
HTML/CSS/JavaScript
小文同学在努力头像 小文同学在努力 
function fibonacci(n) {
    if(n < 1) return -1;
    let a = 1;
    let b = 1;
    for(let i = 2; i < n; i++) {
        b = a + b;
        a = b - a;
    }
    return b;
}

发表于 2022-03-26 17:02:06 回复(0)
HTML/CSS/JavaScript
huaxifn头像 huaxifn 
function fibonacci(n) {
    if(n==1 || n==2){
        return 1;
    }
    return fibonacci(n-1)+fibonacci(n-2);
}

发表于 2022-02-14 17:10:57 回复(0)
HTML/CSS/JavaScript
C.T.F头像 C.T.F

（1）递归+dfs

类似一个二叉树前序遍历，左儿子=f(n-1)，右儿子=f(n-2)，递归遍历

时间复杂度：O(2^n) 主要来自递归产生重复节点调用（重复子问题） 
function fibonacci(n) {
    if(n==0)return 0;
    if(n==1)return 1;
    let left=fibonacci(n-1);
    let right=fibonacci(n-2);
    return left+right;
}

（2）记忆化搜索，消除重复解

以空间换时间，定义存储重复解的空间，每次计算时判断是否已求出，求出则直接返回回溯，否则将新求出的存入 

function fibonacci(n) {
    let arr=[]
    arr.fill(-1)
    
    function dfs(n,arr){
        if(n==0)return 0;
        if(n==1)return 1;
        if(arr[n]!=undefined){
            return arr[n]
        }
        let left=fibonacci(n-1);
        let right=fibonacci(n-2);
        arr[n]=left+right
        return left+right;
    }
    return dfs(n,arr)
}

（3）动态规划+空间压缩dp

只记录前面两个状态 

function fibonacci(n) {
    if(n<=1) return n;
    let pre=0;
    let prre=1;
    for(let i=2;i<=n;i++){
        let t=pre+prre;
        pre=prre;
        prre=t;
    }
    return prre;
}
发表于 2022-01-24 17:23:12 回复(0)
HTML/CSS/JavaScript
牛客234437965号头像 牛客234437965号
加cache咋没啥提升？
发表于 2022-01-17 14:54:00 回复(0)
HTML/CSS/JavaScript
牛客582533844号头像 牛客582533844号 
function fibonacci(n) {
                let array = []
                array.length = n+1
                array[0] = 0 
                array[1] = 1
                for (let i = 2; i < array.length ; i++){
                    array[i] = array[i-1] + array[i-2]
                }
                return array[n]
            }

发表于 2022-01-17 10:19:28 回复(0)
HTML/CSS/JavaScript
牛客833244076号头像 牛客833244076号
function fibonacci(n) {
    let l = 1, r = 1
    for (let i = 0; i < n - 2; i++) {
        const pr = r
        r = l + r
        l = pr
     }
      return r
}
发表于 2022-01-14 13:30:50 回复(0)
HTML/CSS/JavaScript
__sgf__头像 __sgf__ 
function fibonacci(n) {
    return (n == 1 || n == 2) ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}

发表于 2022-01-06 15:27:09 回复(0)
提交观点

问题信息

难度：
34条回答 27278浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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