使用递归方法求解母牛问题

解题思路:

根据题目列出表格如下：

         年龄        1        2         3          4            牛总数

年份

1                      0        0         0          1                1

2                      1        0         0          1                2

3                      1        1         0          1                3

4                      1        1         1          1                4

5                      2        1         1          2                6

6                      3        2         1          3                9

7                      4        3         2          4               13

...

表中的数据是每个年龄段的母牛数量，由于当母牛4岁时才开始生小母牛，故前4年都只有原来的一只大母牛在生崽；要算出表中的数据，可把年龄为1，2，3的母牛个数整体挪移到后一年去加上，再把年龄为4的母牛放到年龄为1的母牛上面形成闭环。随着时间的推移，可知前四年的母牛数量与年份相等，从第五年开始需要靠前四年的母牛数计算得知。仔细观察表格可以发现：第四年的母牛数=第三年的母牛数+第一年的母牛数；第五年的母牛数=第四年的母牛数+第二年的母牛数。...以此类推可得出公式：a(n)=a(n-1)+a(n-3)。则可利用递归的方法求解此题。

注意事项:
需知晓公式：a(n)=a(n-1)+a(n-3)的由来。

参考代码:

#include<iostream>

using namespace std;

int dfs(int year)

{

    if (year <5)//年份为1，2，3，4时母牛数等于年份数，直接返回年份数即可

        return year;

    else

        return dfs(year - 1) + dfs(year - 3);//当年份大于4年时，套用公式a(n)=a(n-1)+a(n-3)即可

}

int main()

{

    int a;

    while (cin >> a && a > 0 && a < 55)//输入数据a，且0<a<55

        cout << dfs(a) << endl;//输出第a年的母牛总数

    return 0;

}