题目 1004: [递归]母牛的故事

/*
题目 1004: [递归]母牛的故事

时间限制: 1Sec 内存限制: 128MB 提交: 57063 解决: 17498

题目描述
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

输入
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。

输出
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

样例输入
2
4
5
0
样例输出
2
4
6
*/

1.第一次超时了，用的递归方式效率很低

#include<iostream>
using namespace std;

//这种递归超时了，效率太低
void recursion(int ny,int by,int n);
int cnt=1;//记录数量
int main()
{
	int n;
	while(cin>>n&&n!=0)
	{
		cnt=1;
		recursion(1,4,n);
		cout<<cnt<<endl;
	}
}

void recursion(int ny,int age,int n)//ny表示第ny年，要加到第n年就停止
{
	if(ny==n)    return;
	else
	{
		age++;
		recursion(ny+1,age,n);//自己还要继续生孩子
		if(age>=4)
		{
			recursion(ny+1,1,n);//孩子长大，达到岁数后生孩子
			cnt++;
		}
	}
}

2.这种利用数字之间的关系得出，效率高很多

#include<iostream>
using namespace std;
int a[100]={0,1,2,3};//数组未初始化部分默认值为0
int recrusion(int n)
{
	if(a[n]!=0) return a[n];
	return a[n]=recrusion(n-1)+recrusion(n-3);
}
int main()
{
	int n;
	while(cin>>n && n!=0)   cout<<recrusion(n)<<endl;
}