首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：15394 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 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
算法知识视频讲解
添加回答
Python 3
牛客嗷嗷头像 牛客嗷嗷 
a, b = 0, 1
n = int(input())
for _ in range(n):
    a, b = b, a + b
print(a)

发表于 2022-09-13 14:41:52 回复(1)
C++
Spectre_头像 Spectre_ 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 时间复杂度O(N)，空间复杂度O(1)
    int dp1 = 1, dp2 = 1, dp3 = 1;
    if (n < 3) {
        cout << dp3;
        return 0;
    }
    for (int i = 3; i <= n; ++i) {
        dp3 = dp1 + dp2;
        dp1 = dp2;
        dp2 = dp3;
    }
    cout << dp3;
    return 0;
}

发表于 2022-10-30 20:45:19 回复(0)
C++
萌新啊！头像 萌新啊！
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1 || n == 2) {
        cout << 1;
        return 0;
    }
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        if (i & 1) b += a;
        else a += b;
    }
    if (n & 1) cout << b;
    else cout << a;
    return 0;
}
发表于 2023-02-27 13:14:40 回复(0)
matlab
LuckyYing头像 LuckyYing
clc
clear

N_inp = input('');                                          % 输入 正整数 n

fib_list = zeros(N_inp, 1);                                 % 开辟内存

fib_list(1:2, 1) = 1;                                       % n = 1, 2 均 为 1

if N_inp > 2
    for i = 3:N_inp

        fib_list(i) = fib_list(i-2) + fib_list(i-1);        % 贝尔曼方程
    end
end

fprintf('%d', fib_list(N_inp))                                  % 打印 输出
编辑于 2024-01-27 14:53:28 回复(0)
LuckyYing头像 LuckyYing
clc
clear

N_inp = input('');                                          % 输入 正整数 n

fib_list = zeros(N_inp, 1);                                 % 开辟内存

fib_list(1:2, 1) = 1;                                       % n = 1, 2 均 为 1

if N_inp > 2
    for i = 3:N_inp

        fib_list(i) = fib_list(i-2) + fib_list(i-1);        % 贝尔曼方程
    end
end

fprintf('%d', fib_list(N_inp))                                  % 打印 输出
编辑于 2024-01-27 14:53:26 回复(0)
Kotlin
小林望北头像 小林望北 
import java.util.*

fun main() {
    val n = readLine()!!.toInt()
//    val n = 4
    println(fib(n))
}

private fun fib(n: Int): Int {
    // 1 1 2 3 5 8
    if (n < 1) return 0
    if (n == 1) return 1
    if (n == 2) return 1

    val dp = IntArray(n + 1)
    dp[1] = 1
    dp[2] = 1
    for (i in 3..n) {
        dp[i] = dp[i - 2] + dp[i - 1]
    }
    return dp[n]
}
发表于 2023-12-10 03:44:19 回复(0)
希望offer多多的太平湖水怪很喜欢吃卤蛋头像 希望offer多多的太平湖水怪很喜欢吃卤蛋 
public static int getInt(int num){
    if(num == 1 || num == 2){
        return 1;
    }else{
        return getInt(num-1)+getInt(num-2);
    }
}

发表于 2023-08-29 14:29:41 回复(0)
C++
_Blossom_头像 _Blossom_
#include <iostream>
using namespace std;

int fib(int k){
    if(k==1||k==2) return 1;
    else return fib(k-1)+fib(k-2);
}
int main() {
    int a;
    cin>>a;
    cout<<fib(a);
}
// 64 位输出请用 printf("%lld")
发表于 2023-08-18 19:21:35 回复(0)
可道非常道头像 可道非常道 
n = int(input())
a=1
b=1
if n <=2:
    print(1)
else:
    for i in range(2,n):
        new = a+b
        a=b
        b= new
    print(new)

发表于 2023-08-15 10:17:51 回复(0)
C
君阮池头像 君阮池
#include <stdio.h>

int fib ( int x )
{
   if( x == 1 || x == 2 )
   {
       return 1;
   }
   else
   {
    return fib ( x - 1 ) + fib ( x - 2 );
   }
}

int main()
{
    int n;
    while ( scanf ( "%d" , &n)  !=  EOF )
    {
        int ret = fib (n);
        printf ( "%d" , ret );
    }
    return 0;
}
发表于 2023-07-09 20:12:30 回复(0)
bleedingfight头像 bleedingfight
int fib(const int N){
if(N == 1)
return 1;
else if(N == 2)
return 1;
else{
int dp[] = {1,1};
for(int i=3;i<=N;i++){
dp[i%2] = dp[0]+dp[1];
}
return dp[N%2];
}
}
发表于 2023-04-28 23:37:47 回复(0)
代码太难写头像 代码太难写 
#include <stdio.h>
int fibonacci(int n);
int main() {
   int input = 0;
   scanf("%d",&input);
   printf("%d",fibonacci(input));
   
}

int fibonacci(int n)
{
    int f[41];
    f[1] = 1;
    f[2] = 1;
    for(int i = 3;i<=n;i++)
    {
         f[i] = f[i-1]+f[i-2];
    }
  return f[n];
}

发表于 2023-04-16 13:22:19 回复(0)
不太可爱的程序猪头像 不太可爱的程序猪 
public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] dp = new int[40];
		dp[0] = 1;
		dp[1] = 1;
		if(n < 3) {
			System.out.println(1);
		}else {
			for(int i = 2;i < n;i++) {
				dp[i] = dp[i - 1] + dp[i - 2];
			}
			System.out.println(dp[n-1]);
		}
		scan.close();
	}

发表于 2023-04-13 21:28:22 回复(0)
wang9头像 wang9 
#include <stdio.h>

int main() {
    int n;
    int arr[500] = {1, 1};
    while (scanf("%d", &n) != EOF) {
        if (n < 1) {
            return 0;
        } else {
            for (int i = 0; i < n; ++i) {
                if (i == 0 || i == 1) {
                    arr[i] = 1;
                } else {
                    arr[i] = arr[i - 1] + arr[i - 2];
                }
            }
            printf("%d", arr[n-1]);
        }
    }
    return 0;
}

发表于 2023-03-19 14:30:52 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scanf("%d",&n)
    if n<=2{
        fmt.Println(1)
        return
    }
    p,q,r:=1,1,2
    for i:=4;i<=n;i++{
        p=q
        q=r
        r=p+q
    }
    fmt.Println(r)
}

发表于 2023-02-04 10:16:41 回复(0)
Java
圣光·明流火头像 圣光·明流火 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        //while (in.hasNextInt()) { // 注意 while 处理多个 case
            /*int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a + b);*/
            int num = in.nextInt();
            int arr[] = new int[num + 1];
            arr[1] = 1;
            arr[2] = 1;
            for(int i = 3;i <= num ;i++){
                arr[i] = arr[i - 1] + arr[i - 2];
        }
        System.out.println(arr[num]);
    }
    //}
}

发表于 2022-09-23 11:12:31 回复(0)
C++
慕_白头像 慕_白 
#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> dp(n,1);
        for(int i = 2;i < n;++i)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        cout<<dp[n-1];
    }
    return 0;
}

发表于 2022-09-07 20:44:10 回复(0)
Javascript_V8
LivingRose头像 LivingRose 
while(n = +readline()){
    var result =1 ;
    for(let i=0,x =0,y=1;i<n-1;i++ ){
        result = x+y;
         x=y;
        y=result;
       
    }
    console.log(result)
}

发表于 2022-09-05 11:02:01 回复(0)
Python 3
牛客253248209号头像 牛客253248209号 
n =  int(input())
l = [1,1]
if n <=2 :
    print(1)
else:
    for i in range(3,n+1):
        c = l[-1]+l[-2]
        l.append(c)
    print(l[-1])


发表于 2022-08-29 21:41:54 回复(0)
Python 3
壮壮kkk头像 壮壮kkk 
def fib(x):
    if x == 1&nbs***bsp;x == 2:
        return 1
    else:
        return fib(x-1) + fib(x-2)
x = int(input().strip())
print(fib(x))
这个咋超时了呢 QAQ

发表于 2022-08-28 22:44:31 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 快速幂 递归
难度：
45条回答 2555浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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