1004: [递归]母牛的故事

解题思路:

一开始思路出了问题，一直考虑的是每年牛的数量=母牛+小牛，然后对母牛和小牛分别递归计算数量，再求和，结果是时间超限了。

#include using namespace std;

int prt(int day);
int cld(int day);
int main() {
	int n = 0;
	//连续输入非0数，到0停止
	while(cin >> n && n && n < 55) {
		cout << prt(n) << endl; //牛牛总数为当年的母牛+小牛，重点在于顺序：先计算小牛变母牛，再计算母牛生小牛，最后算总数
	}
	return 0;
}
int prt(int day) {
	if(day == 1 || day == 2 || day == 3) {
		return 1;
	} else {
		return prt(day - 1) + cld(day - 3); //小牛第四年年初变母牛，所以是cld(day - 3)而不是cld(day - 4)
	}
}
int cld(int day) {
	if(day == 1 || day == 2 || day == 3) {
		return day - 1;
	} else {
		return cld(day - 1) + prt(day) - cld(day - 3); //“小牛年初变母牛”先于“母牛年初下小牛”，所以是prt(day)而不是prt(day - 1)
	}
}
/*
年 1 2 3 4 5 6 7  8  9
母 1 1 1 1 2 3 4  5  7
小 0 1 2 3 4 6 7  11 16
总 1 2 3 4 6 9 11 16 23
*/

后来不得不转换思路，不去区分母牛和小牛，说到底母牛和小牛的区别不就是“有没有生育能力”吗？而“有生育能力”的条件就是“这头牛三年前就已经出生了”。所以说每年的牛是由“前一年的牛”和“三年前的牛”组成的。三年前的牛有母牛也有小牛，但到了现在，这些牛就都是母牛了。

那么可能有人要说了，除掉“新成熟的母牛生的牛”和“前一年剩的牛”，“前一年的老母牛”不也要生小牛吗？为什么不算这部分呢？

实际上，这部分已经被包含在“三年前的牛”内了。试想第m年的时候，有p头母牛，q头小牛，其中有k头小牛会在下一年成熟，于是到第m+1年会发生什么呢？按顺序来就是：小牛变成q-k头，因为k头变母牛了 → 母牛变成p+k头 → 生小牛之前牛的总数仍然是p+k+q-k=p+q，即前一年的牛总数 → 母牛开始生小牛，一共生了p+k头，而k为在这一年成熟的小牛数，而“在这一年成熟的小牛”不就是“三年前出生的牛”吗？

从总数来看：第一种考虑方法中，老母牛生了p头，新成熟的母牛生了k头，前一年剩的牛是p+q；第二种考虑方法中，前一年的牛是p+q，三年前出生的牛新生了k，而从三年前到现在除掉这k头牛、其他的都不是母牛，所以三年前的牛数量为p+k；两种方法的结果都是p+q+p+k。只不过前一种更容易理解，也就是我一开始的代码，后一种更抽象。

可惜为了优化时间复杂度，不得不用后一种思路啊！

后一种代码：

#include using namespace std;
int numCow(int day) {
	if(day < 4) {
		return day;
	} else {
		return numCow(day - 1) + numCow(day - 3);
	}
}
int main() {
	int n = 0;
	while(cin >> n && n && n < 55) {
		cout << numCow(n) << endl;
	}
	return 0;
}

新的问题又来了：这个方法仍然时间超限！

好家伙，原来是递归在对于n很大时，会进行大量的重复计算，比如算numCow(n) = numCow(n - 1) + numCow(n - 3)的时候要把numCow(n - 3)算一遍，结果到了numCow(n - 2) = numCow(n - 3) + numCow(n - 5)的时候又要把numCow(n - 3)算一遍！如果说第一段代码要花2t的时间（因为分成了两个递归），第二段就是t的时间，但t仍然不符合题目的时间限制。

解决办法：建一个大小为55的数组，把算过的结果放进去，这样遇到算过的就不用重复计算了，在主函数里直接根据输入的n来输出对应的numCow[n]就完事了。

最终代码：

#include using namespace std;

int main() {
	long numCow[55] = {0, 1, 2, 3};
	int n = 0;
	for(int i = 4; i < 55; i++) {
		numCow[i] = numCow[i - 1] + numCow[i - 3];
	}
	while(cin >> n && n && n < 55) {
		cout << numCow[n] << endl;
	}
	return 0;
}

这次终于过了。不容易啊。

注意事项:

（1）在计算时，要分清“年初”这个文字游戏，不要把-3搞成-4了。

（2）两种思路写的很清楚了，但后一种较为抽象，需要动脑子想想。

（3）优化时间复杂度方面，用动态规划应该也能达到同样的效果。

参考代码:

#include using namespace std;

int main() {
	long numCow[55] = {0, 1, 2, 3};
	int n = 0;
	for(int i = 4; i < 55; i++) {
		numCow[i] = numCow[i - 1] + numCow[i - 3];
	}
	while(cin >> n && n && n < 55) {
		cout << numCow[n] << endl;
	}
	return 0;
}