【例3.4】昆虫繁殖

题目描述

每对成虫过 $x$ 个月后每月产 $y$ 对卵，每对卵过两个月长成成虫，成虫不死；第 1 个月只有 1 对成虫。求第 $z+1$ 个月（即再过 $z$ 个月）的成虫对数。输入 $x$ 、 $y$ 、 $z$ （ $0 \le x \le 20$ ， $1 \le y \le 20$ ， $x \le z \le 50$ ），输出一个整数。样例输入 1 2 8，输出 37。

思路

设 $a_i$ 为第 $i$ 个月的成虫对数、 $b_i$ 为第 $i$ 个月新产的卵对数。成虫不死且成熟满 $x$ 个月后每月一产，故 $b_i = y \cdot a_{i-x}$ ；卵要两个月才孵化，故 $a_i = a_{i-1} + b_{i-2}$ ，初值 $a_1 = \cdots = a_{x+2} = 1$ ，答案即 $a_{z+1}$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 04:35
# update_at: 2026-09-30 04:35

import sys


def solve() -> None:
    x, y, z = map(int, sys.stdin.buffer.read().split())

    # a[i]：第 i 个月的成虫对数；b[i]：第 i 个月产下的卵对数。下标即月份，0 号位当哨兵 0。
    a = [0] * (z + 3)
    b = [0] * (z + 3)

    for i in range(1, x + 1):
        a[i] = 1  # 成虫不死：前 x 个月始终只有最初那对，尚未到产卵时间

    for i in range(x + 1, z + 2):
        b[i] = a[i - x] * y  # 第 i-x 月已有的每对成虫，过 x 个月在本月产 y 对卵
        a[i] = a[i - 1] + b[i - 2]  # 成虫不死 + 卵过两个月孵化：上月成虫 + 两月前的卵

    print(a[z + 1])  # 从第 1 个月再过 Z 个月，即第 Z+1 个月


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:58
 * update_at: 2026-10-05 08:58
 */
// main.cpp：昆虫繁殖。按月的双序列线性递推求第 z+1 个月的成虫对数。

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXZ = 60; // z <= 50，数组开到 53 够用

ll a[MAXZ]; // a[i] 表示第 i 个月的成虫对数
ll b[MAXZ]; // b[i] 表示第 i 个月新产下的卵对数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int x, y, z;
    cin >> x >> y >> z;

    // 成虫不死：前 x 个月尚未到产卵时间，始终只有最初那 1 对
    for (int i = 1; i <= x; ++i) {
        a[i] = 1;
    }

    for (int i = x + 1; i <= z + 1; ++i) {
        b[i] = a[i - x] * y; // 第 i-x 月已有的每对成虫，过 x 个月在本月产 y 对卵
        ll hatch = 0;        // 两月前产的卵在本月长成的新成虫
        if (i >= 2) {
            hatch = b[i - 2];
        }
        a[i] = a[i - 1] + hatch; // 上月成虫 + 新孵化的成虫
    }

    cout << a[z + 1] << '\n'; // 从第 1 个月再过 z 个月即第 z+1 个月

    return 0;
}

【例3.4】昆虫繁殖

目录

题目描述

思路

参考代码