TZOJ 1376 母牛的故事(递推和递归）

答案1（递推）：

#include<stdio.h>
int main() 
{int n=0,i=0;int a[55] = { 0,1,2,3,4 };   //数组下标就相当于过了几年，以第四年母牛生出的第一只小母牛成年为周期，初始化前四年的值while (scanf("%d", &n) == 1 && (n >= 0 && n < 55))   //使输入符合if (n == 0)   //如果输入0break;     //跳出循环else    //如果输入不是0{if (n <= 4)   //如果在四年内，就没必要递推printf("%d\n", a[n]);   //直接打印母牛个数else     //如果超过四年，就要用递推了{for (i = 5; i <= n; i++)   //从最小递推年数第5年开始，循环至n年（要用<=，不然第5年就直接没算了）{a[i] = a[i - 1] + a[i - 3];    //母牛递推规律（推导解释在文末）if (i == n)    //如果到了输入的n年{a[n] = a[i];   //将此时的个数赋值给输出printf("%d\n", a[n]);   //打印第n年母牛的个数}}}} return 0;
}

答案2（递归）：

# include<stdio.h>
int fun(int n)   //定义母牛个数的函数
{if (n == 1)    //第一年的个数return 1;else if (n == 2)   //第二年的个数return 2;else if (n == 3)    //第三年的个数return 3;else if (n == 4)    //第四年的个数return 4;else     //超出四年{return fun(n - 1) + fun(n - 3);   //用递归母牛的规律公式（推导解释在文末）}
}
int main()
{int n=0;while (scanf("%d", &n) == 1 && (n >= 0 && n < 55))   //使输入符合题目要求if (n == 0)   //如果n=0{break;   //跳出循环}else   //如果n不为0printf("%d\n", fun(n));   //调用上面函数，然后打印return 0;
}

关于本题的知识点以及需要理解的点：

1.第一年母牛是不生的！！！也就是说从第二年母牛才开始生，这是要理解题目的点（大概是题目里每年年初是暗示吧）

2.

母牛个数规律推导：

首先：今年母牛的个数等于去年母牛的个数+今年新生的小母牛个数，然后去年母牛的个数等于去年的去年母牛的个数+去年新生的小母牛个数……直到第四年只有初始母牛在生小母牛

所以

f[i]=今年母牛的个数
f[i-1]=去年母牛的个数
f[i-3]=3年前母牛的个数=今年成年的母牛的个数（因为3年前加上本年等于4年）=今年能够生小母牛的母牛个数（即满4年的成年母牛的个数）=今年新生的小母牛个数
f[i]今年母牛的个数=f[i-1]去年母牛的个数+f[i-3]今年新生的小母牛个数 
故f[i] = f[i - 1] + f[i - 3] 

3.递推和递归的区别

递推：本题求第n年的牛总数，已知第一年为“1”头，进而推出第二年“2”头，第三年“3”头，“4”头，“6”头，“9”头……

递归：要想求第“n”年的牛的总数，只要知道“n-1”和“n-3”年的牛的总数，再依次向前推
所以递推和递归是一个正向思维一个逆向思维

4.在TZOJ上本题只能用递推，递归会超时