当前位置：首页 > article >正文

c语言[递归]母牛的故事，有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

article 2025/2/24 9:27:00

题目：有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

问题分析

设第 n 年的母牛总数为 f(n)。我们可以将母牛分为两类：一类是上一年就已经存在的母牛，数量为 f(n - 1)；另一类是新出生的母牛。新出生的母牛数量等于能生育的母牛数量，而能生育的母牛是三年前就已经存在的母牛，数量为 f(n - 3)。因此，我们可以得到递推公式：

当 n = 1 时，f(1) = 1；
当 n = 2 时，f(2) = 2；
当 n = 3 时，f(3) = 3；

当 n > 3 时，f(n) = f(n - 1) + f(n - 3)。

#include <stdio.h>

// 计算第 n 年母牛的数量
int count_cows(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else if (n == 3) {
        return 3;
    }

    int a = 1, b = 2, c = 3;
    int current;
    for (int i = 4; i <= n; i++) {
        // 根据递推公式计算当前年的母牛数量
        current = c + a;
        // 更新前三年的数量
        a = b;
        b = c;
        c = current;
    }
    return c;
}

int main() {
    int n;
    printf("请输入年份 n: ");
    scanf("%d", &n);

    // 计算并输出第 n 年的母牛数量
    int result = count_cows(n);
    printf("第 %d 年共有 %d 头母牛。\n", n, result);

    return 0;
}