首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列

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

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列是一个满足 $fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right.$ 的数列

数据范围： $1\leq n\leq 40$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$ ，本题也有时间复杂度 $O(logn)$ 的解法

输入描述:

一个正整数n

输出描述:

输出一个正整数。

示例1

输入

输出

说明

根据斐波那契数列的定义可知，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

输入

输出

示例3

输入

输出

算法知识视频讲解

推荐

fanhk

c++动态规划版

class Solution {
public:
    int Fibonacci(int n) {
        int f = 0, g = 1;
        while(n--) {
            g += f;
            f = g - f;
        }
        return f;
    }
};

编辑于 2015-06-19 17:21:55 回复(110)

一个优雅的程序猿

int Fibonacci(int n ) {
    int res[40], i;
    res[0] = 1;
    res[1] = 1;
    for(i=2; i<n; i++)
        res[i] = res[i-1]+res[i-2];
    return res[n-1];
}

发表于 2024-03-23 22:08:36 回复(0)

徐文达

#include <stdio.h>
#include <malloc.h>

int Fibonacci(int n)
{
    int i = 0;
    int number = 0;
    int* p = NULL;
    int* tem = NULL;

    //为数列开辟空间
    tem = (int*)calloc(n, sizeof(int));

    if (tem == NULL)
    {
        perror("calloc");
        return 1;
    }
    p = tem;

    //往数列中存放数据
    for (i = 0; i < n; i++)
    {
        if (i < 2)
        {
            *(p + i) = 1;
        }
        else
        {
            *(p + i) = *(p + i - 1) + *(p + i - 2);
        }
    }

    number = *(p + i - 1);

    free(p);
    p = NULL;
    tem = NULL;

    return number;
}

编辑于 2024-02-24 19:55:22 回复(0)

西部牛仔达顿

动态规划

int Fibonacci(int n ) {
    // write code here
    int arr[40]={0};
    arr[0]=1;
    arr[1]=1;
    int i=2;
    for(i=2;i<=n;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    return arr[n-1];
}

发表于 2023-12-19 19:13:20 回复(0)

牛客869057244号

#include<stdio.h>

int main()

{

int f[40] = { 1,1 }, i, j;

for (i = 2; i < 40; i++)

f[i] = f[i - 1] + f[i - 2];

scanf("%d", &j);

printf("%d\n", f[j-1]);

return 0;

}

这为什么过不了

发表于 2023-10-31 16:28:23 回复(0)

鱼肚白白白

切记是动态规划不是递归。

int Fibonacci(int n ) {
    // write code here
    if(n<=2)
        return 1;
    int a=1,b=1,sum;
    while(n>2)
    {
        sum=a+b;
        a=b;
        b=sum;
        n--;
    }
    return sum;
}

发表于 2022-10-19 22:43:41 回复(0)

恬风吹拂

int Fibonacci(int n ) {
    // write code here
    int a=1,b=1;
    if(n<=2)return 1;
    else
    return (Fibonacci(n-1)+Fibonacci(n-2));
}

发表于 2022-10-19 18:43:31 回复(0)

lmghzzq

int Fibonacci(int n ) {
    // write code here
    static int sum=0;
    if(n==1||n==2) sum=sum+1;
    else Fibonacci(n-1)+Fibonacci(n-2);
    return sum;
}

发表于 2022-10-07 16:43:29 回复(0)

胡晓影

int Fibonacci(int n ) {
//我是来搞笑的，你就说快不快吧
     int a[40]={1,1,2,3,5,8,13,21,34,55,
                89,144,233,377,610,987,1597,2584,4181,6765,
                10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,
                1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155};
     return a[n-1]; 
}

发表于 2022-07-26 23:31:53 回复(2)

聪敏的大白菜向光而行

int Fibonacci(int n ) {
// write code here
if(n==1||n==2)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}

发表于 2022-07-18 17:34:53 回复(0)

✨LAUGH

//动态规划

/**
 * 
 * @param n int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int Fibonacci(int n ) {
    // write code here
    int* s=(int*)malloc(sizeof(int)*n+1);
    s[1]=1;
    s[2]=1;
    for(int i=3;i<=n;i++)
        s[i]=s[i-1]+s[i-2];
    return s[n];
}

发表于 2022-05-06 19:50:12 回复(0)

一个fw狗

int Fibonacci(int n ) {
    // write code here
    if(n==1||n==2)
        return 1;
    return Fibonacci(n-1)+Fibonacci(n-2);//递归实现
}

发表于 2022-03-23 21:22:01 回复(0)

Chromium丶

//递归
/*
int Fibonacci(int n ) {
    if(n == 1 || n == 2) return 1;
    else return Fibonacci(n-2) + Fibonacci(n-1);
    // write code here
}
*/
//动规
int Fibonacci(int n ) {
    int a[n+1];
    a[0] = 0,a[1] = 1;
    for(int i = 2;i<=n;i++) a[i] = a[i-1]+a[i-2];
    return a[n];
}

发表于 2022-03-16 22:54:17 回复(0)

牛客707286683号

int Fibonacci(int n ) {
// write code here
int j=0;
if(n==1||n==2) j=1;
else j=Fibonacci(n-1)+Fibonacci(n-2);
return j;
}
#include<stdio.h>
int main(){
int n=0;
scanf("%d",&n);
printf("%d",Fibonacci(n));
return 0;
}
/*编译有问题，第一次用牛客，求大佬帮忙，非常感谢！

发表于 2022-02-28 22:10:12 回复(0)

牛客471700号

发表于 2022-01-07 18:05:34 回复(0)

牛客_junjun

#include <stdio.h>

/**
*
* @param n int整型
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/

/*int Fibonacci(int n ) //循环算法
{
    int next=0,pre=1,cur=1,i=2;
if(n==1||n==2)
        return 1;
    for(i=3;i<=n;i++)
    {
        next = pre + cur;
        pre = cur;
        cur = next;
    }
    return next;
}
*/
int Fibonacci(int n ) //递归算法
{
    if(n==1||n==2)
        return 1;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

int main()
{
    int n;
    printf("请输入一个大于零的整数\n");
    while(1)
    {
        scanf("%d",&n);
      if(n>0)
          printf("%d\n",Fibonacci(n));
    }
}

发表于 2021-11-30 16:44:16 回复(0)

快支棱起来的小熊猫很美丽

#include <stdio.h>
#include <string.h>
int fib(int x)
{
	/*方法一
	if (x == 1 || x == 2)
		return 1;
	else if (x > 2)
		return (fib(x - 1) + fib(x - 2));
	else
		return 0;
	*/
	/*方法二
	int dp[100] = { 0 };
	dp[1] = 1; dp[2] = 1;
	for (int i = 3; i <= x; i++)
		dp[i] = dp[i - 1] + dp[i - 2];
	return dp[x];
	*/
	//方法三
	int old_old = 1, old = 1, now = 1;//第一、第二均为1，从第三项开始
	for (int i = 3; i <= n; i++)
	{
		now = old + old_old,//将前俩项作为当前项的值
		old_old = old,//将前一项的值给前前一项的值
		old = now;//当前项的值给前一项
	}
	return now;
}
void main() 
{
	int x=0,f=0;
	scanf("%d",&x);
	printf("%d", fib(x));
}

发表于 2021-11-28 22:23:04 回复(0)

谢谢你送花给我

/**
 * 
 * @param n int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int Fibonacci(int n ) 
{
    // write code here
    int sum;
    if(n==1||n==2){
    return 1;
    }
   else 
       n>2;
   {
        sum=Fibonacci(n-1)+Fibonacci(n-2);
      return  sum;}
}

发表于 2021-11-26 13:07:30 回复(0)