代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
题目：
有一对夫妇买了一头母牛，它从第2年起每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。
请编程实现在第n年的时候，共有多少头母牛？
输入格式:
输入为一个整数n(0< n< 55)
输出格式:
输出在第n年的时候母牛的数量。
###输入样例1:
2
###输出样例1:
2
###输入样例2:
5
###输出样例2:
6对于这类题目，我们可以想象为最典型的题目，斐波那契函数的递推调用
//fib
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
long a[111]={0,1,2,3};
for(int i=4;i<=n;i++){
a[i]=a[i-1]+a[i-3];
}
cout<<a[n];
return 0;
}在这里我们首先要去使用long防止递推时所产生的数据量过大，使得超过原有的数据基本范围
第二年生小牛，第四年小牛生下小牛
所以我们对前三年进行枚举，第四年开始调用递推
递推：
本题求第n年的牛总数，已知第一年为“1”头，进而推出第二年“2”头，第三年“3”头，“4”头，“6”头，“9”头……
所以发现第四年以后，牛的总数就是前一年的牛的总数，加上可以生育的牛的总数，而可生育的牛的总数为三年前牛的总数，因而得到递推方程：a[n] = a[n-1] + a[n-3],(n>2)