软件工程头歌一起维护代码第2关：数列计算的预防性维护

任务描述

本关任务：斐波那契数列数列的计算是一个经典的递归问题，但是递归计算的节点个数是O(2n) 的级别的，存在大量重复计算。时间复杂度是O(2n)，一秒内大约能算到第三四十项。
为了改进未来的可维护性或可靠性，或为了给未来的改进奠定更好的基础而修改软件,这被称为软件的预防性维护。
请你实现更加高效的方式，输入一个整数n，求斐波那契数列的第n项。
假定从0开始，第0项为0。为了防止结果溢出int范围，结果需要对1000000007取模。
输入样例：

1. 5

输出样例

1. 5

解释：输入5，表示求斐波那契数列数列的第五项，0，1，1，2，3，5...第5项为5，则输出5.

编程要求

根据提示，在右侧编辑器补充代码，计算并输出结果。

测试说明

平台会对你编写的代码进行测试。

开始你的任务吧，祝你成功！

答案

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

// 预防性维护后的代码

int F(int n) {

    //请在此处添加代码,输出斐波那契数列的第n项

    /********** Begin *********/

    if(n==1||n==2)return 1;

    else

    {

        int f1=1,f2=1,f3;

        for(int i=0;i<n-2;i++)

            {

                f3=(f1+f2)%MOD; 

                f1=f2;f2=f3;

            }

        return f3;

    }

    /********** End **********/

}

int main() {

    int n;

    cin >> n;

    cout << F(n) << endl;

    return 0;

}