首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数:6186 时间限制: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

输入

3

输出

3
示例2

输入

5

输出

8
BNK头像 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)
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)
用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)
要用动态规划,递归会超时
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)
递归过多重复计算 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)
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)
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)
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)
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)
#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)
这个题用递归来做就简单很多吧,望采纳
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)
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)
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)
function fib(n) {
    let db = [];
    db[0] = 1;
    db[1] = 1;
    for (let i = 2; i <= n; i++) {
        db[i] = db[i - 1] + db[i - 2];
        db[i] %= 1000000007;
    }
    return db[n];
}
哪位给看下,怎么也过了不,本地和力扣跑没问题啊
编辑于 2020-09-25 09:39:32 回复(0)