LQ0007 数列求值【递推】

题目出处：蓝桥杯2019初赛

题目描述
给定数列1, 1, 1, 3, 5, 9, 17, …，从第4 项开始，每项都是前3 项的和。求
第20190324 项的最后4 位数字。

题目分析
递推计算数列值，每次算出结果的后四位数字。
使用数组存储数列各项的结果，程序逻辑相对简单。
不用数组也可以计算，程序逻辑略微复杂，可以节省存储。

题记
玩程序玩的是时间和空间，要尽量做到程序运行时间短节省空间。

AC的C语言程序（使用数组）如下：

/* LQ0007 数列求值 */

#include 

#define MOD 10000
#define N 20190324

int f[N + 1];

int main()
{
    f[1] = f[2] = f[3] = 1;
    for (int i = 4; i <= N; i++)
        f[i] = (f[i - 3] + f[i - 2] + f[i - 1]) % MOD;

    printf("%d\n", f[N]);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

AC的C语言程序（节省存储）如下：

/* LQ0007 数列求值 */

#include 

#define MOD 10000
#define N 20190324

int main()
{
    int f1, f2, f3, t;
    f1 = f2 = f3 = 1;
    for (int i = 4; i <= N; i++) {
        t = (f1 + f2 + f3) % MOD;
        f1 = f2, f2 = f3, f3 = t;
    }

    printf("%d\n", t);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20