[递归]母牛的故事题解

解题思路:

这是一个典型的斐波那契数列问题，只不过初始条件略有不同。根据题目描述，母牛的数量可以用递推公式来表示：

        f(n) = f(n-1) + f(n-3)

注意事项:1.可以使用scanf函数的返回值来判断输入是否结束。当scanf函数返回1时，表示成功读取了一个整数；当scanf函数返回0时，表示输入结束。

              2.使用了递归的方式，会导致重复计算 从而导致时间超限，为了改良这个问题，可以使用动态规划（Dynamic Programming）来避免重复计算。具体做法是使用一个数组来保存已经计算过的结果，从而避免重复计算

参考代码:

        #include<stdio.h>

            long long cow_num(int n) //long long防溢出 

            {

                     long long dp[100]={0}; //用数组保存 

                     for(int i=1;i<=n;i++)

                     {

                          if(i<=3)

                              dp[i]=i;

                          else if(i>=4)

                             dp[i]=dp[i-1]+dp[i-3];

                     }

             }

                     return dp[n];

            }

        int main()

        {

                     int s=0;//输入数据的个数 

                     int year[100];

                     while(scanf("%d",&year[s])==1&&year[s]!=0)//读取到一个整数(当scanf成功读取时会返回1)，且该整数不等于0

                     {

                              s++;

                     }

                     for(int i=0;i<s;i++)

                     {

                             printf("%lld\n",cow_num(year[i]));

                     }

                 return 0;

        }