编写程序，从键盘读入一个整数n，然后输出斐波那契数列的前n项到屏幕，项与项之间使用空格分隔。

Question

输入格式

一共1行数据，包含一个整数n。

输出格式

输出1行，项与项之间使用空格分隔，即用n-1个空格分隔n项数据，行末没有空格也没有换行符。

Answer 1

#include <iostream>
using namespace std;
const int mod = 1000000009;
// 第一步
int f[10000];
int fib(int x) {
    if (f[x]){
        return f[x];
    }
    if (x <= 2) {
        return f[x]=1;
    }
    else {
        return f[x]=(fib(x - 1) + fib(x - 2))%mod;
    }
}

int main() {
    int n;
    cin >> n;

for (int i=1;i<=n;i++){

    cout << fib(i) << endl;

}
   
    return 0;
}