前言

前一篇文章我使用递归算法完成了斐波那契数列这道经典例题，相关的文章见我之前写的关于递归算法一方面的笔记：【C++学习笔记】递归算法的初步理解与应用 – 小改学习志。

不过递归虽然无脑，但是把代码交上去：诶，这代码提交上去都超2000ms我还拿分吗，不仅超时间限制不知道多少了，关键都报Runtime Error了，就没有更加强势可以过测试点的方法吗？我只想说：有的东西，有的有的，这样强势的方法直接叫上循环和数组老祖就能搞定。

题目信息

斐波那契数列是指这样的数列：数列的第1个和第2个数都为1，接下来每个数都等于前面两个数之和。给出一个正整数k，要求菲波那契数列中第k个数是多少（1≤k≤46）。

分析题目

正儿八经看这题目，其实这题目是很简单的。我们仔细分析一下：

• 这题我们知道数据范围k小于等于46，并且也没有其他多余的量，我们优先考虑使用一维数组，为了方便，我们定义一个数组：list[47]（为什么是47，因为数组索引从0开始，我们为了方便我们不管0，这样我们就可以从1开始数了，所以长度得设置成47）
• 观察发现，这个数列从第三项开始就等于前两项之和，我们就可以知道这个数列中， 除第一第二项，其余的项满足此规律：a_n+1=a_n+a_n-1，其中n≥2。
• 我们可以把这个数组写成list[47] = {0, 1, 1, 2}，这样我们后面就可以写个循环，定义一个整型变量k，这样我们写一个for循环，因为我们已知前面三项，所以后面的项也都满足：a_n+1=a_n+a_n-1，于是我们想算第4项，我们就可以写成：a[4] = a[4 - 1] + a [4 - 2]，这样就轻松求出后一项了。
• 把4替换成一个临时的整型变量i，i的最小值为4，i≤k，且每次循环后i自增1，这样我们在循环结束时就可以进行输出这个结果了，程序也就这么结束了，我们也大致捋清了程序的运行思路了。

参考代码

定义变量k，以及整型一维数组list[47] = {0，1， 1，2}，输入k值，然后进行循环，算出list[k]项，然后再输出，这程序就这么写完了，代码如下：

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

大致总结

条条大路通罗马，当递归算法实现斐波那契数列时容易出现Runtime Error这个错误时，我们不妨使用一维数组和for循环来替代递归，优化了这个程序。

时间也不早了，晚安。

（明早终于不用被竞赛教练制裁了）