14.基本递推

发表于 更新于 分类于 ，

基本递推

递推是编程中最常用的技能，规模较大的问题可以由规模较小的问题计算得到，从规模较小的问题开始，按一定的顺序推导更大问题的解的过程。

例：斐波那契数列

\(f_{1}=1, f_{2}=1, f_{n}=f_{n-1}+f_{n-2}\).

求数列的第 \(n\) 项.

当这类问题存在多次提问时，可以用一个数组把序列的表提前算好，俗称“打表”.

知识点：有的问题（或函数，或数列）随着自变量的增大，增长非常快，这样稍大一些的时候，long long 都存不下。出题人为了考察这类问题，会要求输出答案对一个较大的质数取模的结果，这个结果正确，就认为答案正确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 斐波那契数列前 1000 项，每项都是对 10^9+7 取模的结果
const int mod = 1e9 + 7;
long long f[1111];
int main() {
    f[1] = f[2] = 1;
    for(int i = 3; i <= 1000; i ++) {
        f[i] = (f[i - 1] + f[i - 2]) % mod;
    }
    int n;  // 不断询问的第“n”项
    while(scanf("%d", &n) != EOF) { // EOF是scanf读到输入文件末尾时的返回值
        printf("%d\n", f[n]);
    }
    return 0;
}

例：传染

数量不限个健康动物，一个生病动物每轮会传染 \(x\) 个健康动物， 求 \(n\) 轮后染病动物总数。

输入 \(x\) 和 \(n\)

1
10 2

输出

1
121

每轮结束时，染病动物总数应当是传染的数量加上已染病的数量，形成递推关系。

如果涉及多次查询，就开数组大表，否则用一个变量递推就行。

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
#include<cstring>
int main() {
    int x, n;
    long long ans = 1;          // 最开始的一个，指数级增长要注意查看题目数据范围
    scanf("%d%d", &x, &n);            
    for(int i = 1; i <= n; i ++) {
        ans = ans * x + ans;    // 传染的加上已有的
    }
    printf("%lld\n", ans);
    return 0;
}

常见注意点小结

  • 注意递推问题的增长规模与数据范围，选择性使用 long long
  • 题目答案要求对特定数取模，要注意不仅仅是结果取模，要避免计算过程中超类型范围
    • 递推式多项累加，要分析中间结果是否会超long long，如果会，则要随时取模： f[n] = ((f[n - 1] + f[n - 2]) % mod + f[n - 3]) % mod
    • 递推式带有乘法，虽然取模数不超 int ，但乘法计算超： 用“1LL”去乘中间结果临时转 long long： f[n] = 1LL * f[n-1] * f[n - 2] % mod;