母牛生小牛_模拟推演

问题描述：

设有一头小母牛，从出生第四年起每年生一头小母牛，按此规律，第N年时有几头母牛？

输入描述

本题有多组数据。每组数据只有一个整数N，独占一行。( 1 ≤ N ≤ 50 )。当N为0时，输入结束。

输出描述

对每组数据，输出一个整数（独占一行）表示第N年时母牛的数量。

分析

 此问题很容易让人想到递归的方法，但是母牛每年的增量(出生的母牛)不确定，造成这个增量的可生育的牛妈妈的增量亦是未知，造成牛妈妈的增量的上年三岁的的母牛的数量未知，增量未知……
并不能明确得出f(n)=f(n-x)+f(n-y)+m…的递推式，所以不能使用，反正我是不会

求解方法

 计算机最擅长反复地迭代计算了，所以直接点，模拟过程
 注意这里牛群全部针对母牛讨论

方式一（占空间太大了）

#include<iostream>
#include<vector>

using namespace std;
//用对象太奢侈了，只有一个属性（年龄），所以下面一个加入向量空间的一个数（年龄）
//就看做一个牛儿吧
int main()
{
	vector<int> a;
	vector<int> lair;
	vector<int> result;
	lair.push_back(0);
	for (int i = 0; i < 50; i++) //时间线（年），控制模拟进程
	{
		int num1 = lair.size();
		for (int j = 0; j < num1; j++) //所有牛儿的年龄加1
		{
			lair[j]++;
		}
		int num2 = lair.size();
		for (int j = 0; j < num2; j++)
		{
			if (lair[j] >= 4)
				lair.push_back(1); //生了一个牛儿
		}
		result.push_back(lair.size());
	}
	int temp;
	cin >> temp;
	while (temp != 0)
	{
		a.push_back(temp);
		cin >> temp;
	}
	for (int i = 0; i < a.size() ; i++)
	{
		if(i==a.size()-1) 
			cout << result[a[i]-1];
		else
			cout << result[a[i] - 1] << endl;
		}
	return 0;
}

50年lair向量空间的维数就会太大了，因为50年时母牛已经8000多万只了，vector的遍历成本太大，向量占用空间也较大，所以Don’t be accepted喽

于是放弃了用容器去放牛儿，直接用五个数分别记录某年的母牛总数和各个年龄段的母牛总数来推演整个牛群发展进程

方式二（accepted）:

#include<iostream>
#include<vector> 

using namespace std;

int main()
{
	vector<int> a;
	vector<int> result;
	int lair[5] = {1,1,0,0,0}; //1年结束时的每个类群的个数 
	//index:0:当年牛数 1：当年一岁的牛数 2：2岁的牛数
	//index: 3:当年三岁的牛的总数 4：当年具有生育能力的牛数
	result.push_back(lair[0]);
	//第一年只有一只母牛 
	for (int i = 2; i <= 50; i++) //时间线（年）
	{
		lair[4] += lair[3]; 
		//上年3岁的牛今年当了妈妈 
		lair[0] += lair[4]; 
		//今年结束时候牛群的增量由今年的牛妈妈提供
		lair[3] = lair[2];	
		//上年2岁的牛今年底3岁 
		lair[2] = lair[1]; 
		//上年1岁的牛这年底2岁
		lair[1] = lair[4];  
		//（今年的牛群增量）今年新生，年底为一岁  
		result.push_back(lair[0]); //某年结束的时候的母牛数 
	}
	int temp;
	cin >> temp;
	while (temp != 0)
	{
		a.push_back(temp);
		cin >> temp;
	}
	for (int i = 0; i < a.size() ; i++)
	{
		if(i==a.size()-1) 
			cout << result[a[i]-1];
		else
			cout << result[a[i] - 1] << endl;
		}
	return 0;
}

结果截图