首页 > 试题广场 >

求斐波那契（Fibonacci）数列的第 n 项

[编程题]求斐波那契（Fibonacci）数列的第 n 项
  • 热度指数：898 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解 
斐波那契数列（Fibonacci sequence），又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、…... 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例1

输入

1

输出

1
示例2

输入

5

输出

5

备注:
0 <= n <= 100
算法知识视频讲解
添加回答
施工段头像 施工段
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int Fibonacci (int n) {
        // write code here
        if(n==0||n==1){
            return n;
        }
        else{
            return Fibonacci(n-1)+Fibonacci(n-2);
        }
    }
}
发表于 2021-12-04 14:20:47 回复(0)
pein531头像 pein531
根据斐波那契数列的通项公式迭代求解 
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int Fibonacci (int n) {
        // write code here
        if(n == 1)
            return 1;
        else if(n == 2)
            return 1;
        else{
            int p = 1, q = 1;
            int r = 0;
            for(int i = 2; i < n; i++){
                r = p + q;
                p = q;
                q = r;
            }
            return r;
        }
    }
}

发表于 2021-09-28 09:49:00 回复(0)
C/C++
神码_头像 神码_ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int Fibonacci(int n) {
        if(n<=1)
        {
            return n;
        }
        else
        {
            return Fibonacci(n-1)%1000000007+Fibonacci(n-2)%1000000007;
        }
    }
};

发表于 2023-09-30 21:38:25 回复(0)
C/C++
ت20181024193444头像 ت20181024193444 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 */
int Fibonacci(int n ) {
    if(n==0){
        return 0;
    }else if(n==1){
        return 1;
    }else{
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}


发表于 2023-03-30 20:16:33 回复(0)
牛客348677018号头像 牛客348677018号
python3

if n==0 or n==1:
            return n
        else:
            return self.Fibonacci(n-1)+self.Fibonacci(n-2)
发表于 2022-08-14 13:24:14 回复(0)
先胖三斤做个预实验头像 先胖三斤做个预实验 
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
    def Fibonacci(self , n ):
        # write code here
        a,b = 0,1
        for i in range(n):
            a,b = b , a + b
            b = b % 1000000007
        return a

#
#
# @param n int整型
# @return int整型
#
classSolution:
    defFibonacci(self, n ):
        # write code here
        a,b =0,1
        fori inrange(n):
            a,b =b , a +b
            b =b %1000000007
        returna
发表于 2022-08-08 21:50:47 回复(0)
jkslfkt头像 jkslfkt
使用递归即可求解
importjava.util.*;
publicclassSolution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    publicintFibonacci (intn) {
        // write code here
        if(n==0){
            return0;
        }
        if(n==1){
            return1;
        }else{
            returnFibonacci(n-1)+Fibonacci(n-2);
        }
    }
}
发表于 2022-03-04 21:46:22 回复(0)
4fbd81e头像 4fbd81e 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n ):
        a,b=0,1
        mod=1000000007
        for i in range(n):
            a,b=b%mod,(a+b)%mod
        return a    
    
    

发表于 2022-01-20 12:19:14 回复(0)
牛客145121328号头像 牛客145121328号
    int Fibonacci(int n) {
        // write code here
        vector<int> dp(101, 0);
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= 100; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }  
        return dp[n];
    }
发表于 2021-11-15 19:50:30 回复(0)
猫猫小宝头像 猫猫小宝
classSolution:
    defFibonacci(self, n ):
        # write code here
        s0=0
        s1=1
        sum=s0+s1
        i=1
        mod=1000000007
        ifn==0:
            return0
        ifn==1000000008:
            return1
        whilei<n:
            sum=s0+s1
            s0=s1
            s1=sum
            i=i+1
        f=sum%mod
        returnf
发表于 2021-09-03 04:21:05 回复(0)
牛客985456093号头像 牛客985456093号
class Solution:
    def fib(self, n):                         
        bef =0
        aft =1
        nex =1
        if n ==0:                      
            return0                    
        elif n ==1:                    
            return1                    
        else:                           
            count =2                   
            while count <=n:           
                nex =bef +aft         
                bef =aft               
                aft =nex               
                count +=1              
            return nex %1000000007                                         
a=Solution()                                    
print(a.fib(8))   


为什么这个答案会错误呢？pychram上运行过没问题啊
发表于 2021-07-17 17:26:16 回复(0)
提交观点

问题信息

中国电子云 测试开发工程师 测试工程师 2021
上传者：小小
难度：
11条回答 3414浏览

热门推荐

通过挑战的用户

相关试题

求斐波那契（Fibonacci）数列的第 n 项

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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