1147: 零起点学算法54——Fibonacci

小鱼儿 2023-01-11 08:44 165阅读 0赞

## Description ##

Fibonacci数列定义为（1,1,2,3,5,8,.....），即每个元素是前两个元素的和。如果一个Fibonacci数与所有小于它的Fibonacci数互质，那么称之为Fibonacci质数。  
现在要求你输出前n个Fibonacci数  
The Fibonacci Numbers \{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...\} are defined by the recurrence:  
F(0)=0  
F(1)=1  
F(i)=F(i-1)+F(i-2)  
Write a program to calculate the Fibonacci Numbers.

## Input ##

The first line of the input file contains a single integer T, the number of test cases. The following T lines,each contains an integer n ( 0 <= n <= 45 ), and you are expected to calculate Fn

## Output ##

Output Fn on a separate line.

## Sample Input ![5f8f312f51791b8bb0ed0ae07c2ffa43.gif][] ##

5
    0
    3
    5
    9
    20

## Sample Output ##

0
    2
    5
    34
    6765

## Source ##

[零起点学算法][Link 1]

## Code ##

#include<stdio.h>
    #include<iostream>
    using namespace std;
    ///F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)（n≥2,n∈N*）
    int Fibonacc(int n)
    {
        if(n==0)
            return 0;
        else if(n==1)
            return 1;
        else
            return Fibonacc(n-1)+Fibonacc(n-2);
    }
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            int n;
            cin>>n;
            cout<<Fibonacc(n)<<endl;
        }
    }

第一遍代码如图，结果显示超时。题目要求n最大为45，算出最终结果耗时14s.本题我使用的是递归，时间复杂度较高，因此会有超时问题。在网上搜索其他人的代码，发现使用数组存储会比较好。

#include<stdio.h>
    #include<iostream>
    using namespace std;
    ///F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)（n≥2,n∈N*）
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            int n;
            int a[50]={0,1};
            cin>>n;
            for(int i=2;i<=n;i++)
            {
                a[i]=a[i-1]+a[i-2];
            }
            cout<<a[n]<<endl;
        }
    }

在最后一个循环的地方除了点错，一开始循环的条件是i<n，结果发现每次输出的a\[n\]都是0.后来发现是下标的问题，所以把循环的条件改成了i<=n;

[5f8f312f51791b8bb0ed0ae07c2ffa43.gif]: /images/20221119/ee4965d855964700a84c4343f5cadb79.png
[Link 1]: https://oj.wustacm.top/problemset.php?search=%E9%9B%B6%E8%B5%B7%E7%82%B9%E5%AD%A6%E7%AE%97%E6%B3%95&searchmode=source&soj=0