首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列

热度指数：6223 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

形如1, 1, 2, 3, 5, 8, 13, 21, 34, 55的数列，后一位是前面两位相加（斐波那契数列），写出函数要求找到第 N 位是多少，如：fib(3) => 3 ， fib(5) => 8, 要求时间复杂度为O(n)。

输入描述:

输入一个正整数N（0<=N<=50）

输出描述:

输出第n项的数值

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

BNK

function fib(n){
    let top=1,bottom=0,res=0
    for(let i=0;i<n;i++){
        res=top+bottom
        bottom=top
        top=res
    }
    return res
}

发表于 2020-03-07 08:29:20 回复(13)

HEXOGEN

const fib = (num) => {
    const triple = [0, 0, 1];
    for (let i = 0; i < num; i++) {
        [triple[0], triple[1], triple[2]] = [triple[1], triple[2], triple[1] + triple[2]];
    }
    return triple[2];
};

print(fib(parseInt(readline())));

发表于 2020-03-22 22:47:49 回复(4)

萌萌萌哒

JavaScript 2020美团-斐波那契数列😎dp

const readline = require('readline') const rl = readline.createInterface({ input: process.stdin, ouput: process.stdout }) let inArr = [] rl.on('line', line=>{ if(!line) return inArr.push(line.trim()) if(inArr.length === 1){ let n = +inArr[0] let dp = [1,1,2] for (let i = 3; i < n+1; i++) { dp[i]= dp[i-1]+dp[i-2] } console.log(dp[n]) } })

发表于 2020-03-08 18:35:19 回复(0)

cating

用js写的，但是一直说输出为空值，要怎么解决呢？

function fib(n) {
  let last = 1;
  let last2 = 0;
  let current = last2;
  for (let i = 1; i <= n; i++) {
    current = last + last2;
    last2 = last;
    last = current;
  }
  return current;
}

发表于 2020-09-10 10:17:18 回复(1)

牛客57482729号

var fib = function(index){
    let res = 1
    for(let i = 1;i < index; i++){
        res += fib(i - 1)
    }
    return res
}

在编译器上对的，牛客上不通过，我这对吗🤣

发表于 2022-07-10 18:29:46 回复(0)

牛客637168969号

要用动态规划，递归会超时

let n = "";
while(n = readline()){
    let dp = new Array(n+1);
    dp[0] = 1;
    dp[1] = 1;
    for(let i = 2;i<=n;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    console.log(dp[n]);
}

发表于 2022-06-19 21:07:02 回复(0)

C/C++

勤能补拙i

递归过多重复计算 T=O(n^2)

记录数据迭代 T=O(n)

矩阵快速幂 T=O(logn)

以下矩阵快速幂法：

#include <iostream>
#include <cstdio> 
#include <cstdlib> 
using namespace std;

struct Martix{
    int row,col;
    long long martix[2][2];
    Martix(){}
    Martix(int r,int c):row(r),col(c){}
    Martix(int n) {        //单位方阵构造函数
        this->row = n;
        this->col = n;
        this->martix[0][0] = 1;
        this->martix[1][1] = 1;
        this->martix[0][1] = 0;
        this->martix[1][0] = 0;
    }
};

Martix multiply(Martix x,Martix y){        //矩阵乘法
    Martix answer=Martix(x.row,y.col);
    for(int i=0;i<answer.row;++i)
        for(int j=0;j<answer.col;++j)
        {
            answer.martix[i][j]=0;
            for(int k=0;k<x.col;++k)
                answer.martix[i][j]+=(x.martix[i][k]*y.martix[k][j]);
        }
    return answer;
}

long long answer(int n){
    if(n==0 || n==1){
        return 1;
    }
    if(n==2){
        return 2;
    }
    else
    {   n-=1;
        Martix base=Martix(2,2);
        Martix ans=Martix(2);
        base.martix[0][0]=1;
        base.martix[0][1]=1;
        base.martix[1][0]=1;
        base.martix[1][1]=0;
        while(n!=0){
        if(n%2==1){
            ans=multiply(ans,base);
        }
        n>>=1;
        base=multiply(base,base);
    }
    return ans.martix[0][0];
    }
}

int main(){
        int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%lld\n",answer(n+1));
    }
return 0;
}

发表于 2022-02-18 11:07:37 回复(0)

牛客617387420号

import sys
class Solution:
    def func(self, n):
        if n == 0:
            return 1
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]
                   
if __name__ == '__main__':
    solution = Solution()
    n = int(sys.stdin.readline().strip())
    print(solution.func(n))

发表于 2020-04-08 09:05:22 回复(0)

Golden_Crane

import java.util.Scanner;
public class Main{
    public static long fib(int num) {
        if(num==0||num==1) 
            {
                return 1;
            }
        long [] it=new long [1000];
        it[0]=1;
        it[1]=1;
        long result=0;
        for (int i = 2; i <=num; i++) {
            it[i]=it[i-1]+it[i-2];
            result=it[i];
        }   
        
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
    System.out.println(fib(num));
    sc.close(); 
}
}

发表于 2020-03-19 23:06:07 回复(1)

_Yee_

function fibo(n) {
    if(n === 0 || n === 1) {
        return 1
    }
    const fibo = [1, 1]
    for (let i = 2; i <= n; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2]
    }
    return fibo[fibo.length-1]
}

不知道为什么不能通过

发表于 2021-09-08 18:03:31 回复(0)

爱交友的ssr在刷题

function fib(n){
   if(n==0||n==1){
       return 1
   }else{
     return  fib(n-1)+fib(n-2);   
   }
}
console.log(fib(5))
//递归的方法

发表于 2021-08-30 20:23:23 回复(0)

lotianveo

#include<iostream>
#include<vector>
#include<algorithm>
#include <vector>
using namespace std;
int n;
vector<int> F(int n,vector<int> f){
    int i=1;
    while(i<=n){
        if(i==1||i==2){
            f.push_back(1);
        }else{
            int m;
            m=f[i-2]+f[i-3];
            f.push_back(m);
        }
        i++;
    }
    return f;

}
int main(){
    vector<int> f;
    scanf("%d", &n);
    n=n+1;
    vector<int> m=F(n,f);
    printf("%d\n",m[n-1]);

    return 0;
}
有没有同学说一下为什么我的用例通过是4/5，我觉得完全没问题啊！！！！！！！！

发表于 2021-08-19 22:21:58 回复(0)

JavaScript

chemmhi

这个题用递归来做就简单很多吧，望采纳
function fib(num){
  if(num === 0 || num ===1){    //如果输入的是0,1，则返回1，递归终止条件
    return 1
  }
  return fib(num-1) + fib(num-2) //返回前一个，和前前一个数列的和
}

编辑于 2021-08-11 14:11:33 回复(1)

拜仁的月饼

typedef long long ll;
#include<cstdio>

ll fibo(int n){
    if(!n || n == 1)
        return 1;
    ll fiboArr[n + 1];
    fiboArr[0] = 1;
    fiboArr[1] = 1;
    for(int i = 2; i <= n; i++)
        fiboArr[i] = fiboArr[i - 2] + fiboArr[i - 1];
    
    return fiboArr[n];
}

int main(){
    int N = 0;
    scanf("%d", &N);
    const ll res = fibo(N);
    printf("%lld", res);
    
    return 0;
}

发表于 2021-08-05 14:20:39 回复(1)

牛客勇

function fun(a) {
    var arr = [1, 1]; //后面数为它前两个数相加，故先直接定义前两个数。
    for(var i = 2; i < a + 3; i++) {
        arr[i] = arr[i - 1] + arr[i - 2]; //当前数为前两个数相加。
    }
    return arr[a]; //返回指定数。
}
console.log(fun(50));

发表于 2021-03-26 21:01:27 回复(0)

啧啧啧！

两个方法一个循环

function fib(num){
let arr =[];
for(let i=0; i <= num; i++){
if(i < 2){
arr.push(1);
}else{
arr.push(arr[i-2]+arr[i-1])
}
}
return arr[num]
}

或者用递归

function fib(num){

if(num < 2){

return 1

}

return fib(num-1)+fib(num-2)

}

发表于 2021-03-18 14:09:08 回复(0)

passion仔

function fib(index) {
    let pre = 1, end = 1;
    for (let i=0;i<index;i++) {
        [pre, end] = [end, pre + end];
    }
    return pre
}

发表于 2021-03-14 15:19:39 回复(0)

稀稀稀稀稀稀奇

#include<iostream>
#include<vector>
using namespace std;
long long help(int n) {
if (n == 1) return 1;
vector<long long> result(n + 2, 0);
result[1] = 1;
for (int i = 2; i <= n+1; ++i) {
result[i] = result[i - 1] + result[i - 2];
}
return result[n+1];
}
int main()
{
int n;
cin >> n;
long long result = help(n);
cout << result;
return 0;

}

第二种解法：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin>>n;
if(n==1)return 1;
vector<long long> dp(n+2,0);
dp[1]=1;
for(int i=2;i<=n+1;i++)
dp[i]=dp[i-1]+dp[i-2];
cout<<dp[n+1];
return 0;
}

编辑于 2021-01-30 18:46:38 回复(0)

假如三月十天

function fb(n){

if（n == 0 || n == 1）{

return1

} else{

returnfb(n-2)+ fb(n-1)

}

发表于 2020-12-10 18:35:13 回复(0)

斐斐王P

function f(n){
    if(n==1&&n==2){
        return 1;
    }else{
        return f(n-1)+f(n-2);
    }
}

发表于 2020-10-15 15:14:13 回复(0)

提交观点

问题信息

美团前端工程师 2020

上传者：小小

难度：

45条回答 121收藏 8587浏览

通过挑战的用户

牛客94948...

2023-03-14 14:34:08
chocoxxxx

2023-03-12 13:09:39
牛客16723...

2023-03-12 11:02:16
牛不牛全看有没...

2023-03-11 20:31:53
YOKI111

2023-03-11 17:45:38

斐波那契数列

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题