题目描述

以下数列0 1 1 2 3 5 8 13 21 …被称为斐波纳契数列。

这个数列从第3项开始，每一项都等于前两项之和。

输入一个整数N，请你输出这个序列的前N项。

输入格式
一个整数N。

输出格式
在一行中输出斐波那契数列的前N项，数字之间用空格隔开。

样例

输入样例：
5
输出样例：
0 1 1 2 3

算法1

(暴力模拟) $O(n)$

时间复杂度分析：对于n以内的数每个用递推公式算一遍

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,feibo[99999];
int main(){
    scanf("%d",&n);
    feibo[1]=0,feibo[2]=1;
    for(int i=3;i<=n;++i) feibo[i]=feibo[i-1]+feibo[i-2];
    for(int i=1;i<=n;++i) printf("%d ",feibo[i]);
    return 0;
}