运行时间:4

解题思路:

把前几年的牛的数量写出来,找下规律(这排版..我尽力了)

出生后x年      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

应该容易看出来第n年,牛的总数 F[n]=F[n-1]+F[n-3]

注意事项:

没有使用递归;

用数组依次储存每一年的牛总数可以减少运算量


参考代码:

#include<stdio.h>

int main()

{

    int q[55]={1,2,3}; //粗略一算可知第1,2,3年的牛总数分别为1,2,3只

    int i,m=0; //m:记录所求的最大年数

    int n[20]; //n:保存输入的所求年数

    for(i=0;i<20;i++) //输入

    {

        scanf("%d",&n[i]);

        if(n[i]==0) break;

        if(m<n[i]) m=n[i]; //记录所求最大年数

    }

    for(i=3;i<=m;i++) //循环算出从第4年(3+1)至m年的牛总数,并保存在数组中

        q[i]=q[i-1]+q[i-3]; //找规律找出来的

    for(i=0;n[i]!=0&&i<21;i++) //输出

        printf("%d\n",q[n[i]-1]);

    return 0;

}