【递归】母牛的故事

第一次提交超时——

解题思路:对第一头奶牛每年生一头小母牛进行递归，递归部分为每生出一头小奶牛，其第四年之后就可每年生出一头小母牛这一过程是重复的。

注意事项:此解法效率不高，递归部分不够高度浓缩，以致超时。

参考代码:

#include<stdio.h>

int get(int n)
{
    int sum=1;//初始值为一头母牛
    int i;
    for(i=1;i<=n;i++)//每一年
    {
        sum++;
        get(n-4);//每年生下一头小母牛
    }

    return sum;
    
}

int main()
{
int n;
int sum;

while(1)
{

    scanf("%d\n",&n);
    if(n==0)
        break;
    sum = get(n);
    printf("%d\n",sum);
}


return 0;
}

第二次提交正确——参考优质题解

解题思路:第n年的母牛数=第n-1年的母牛数+第n-3年的母牛数（已具有生育能力）

注意事项:每一头母牛生出的那一年视为第一年

参考代码:

#include<stdio.h>

int get(int n)

{

    if(n<=4)

        return n;

    else

        return get(n-1)+get(n-3);

}

int main()

{

int n;

while(1)

{

    scanf("%d\n",&n);

    if(n==0)

        break;

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

}

return 0;

}