【递推】兔子繁殖问题

题目描述

如果有一对小兔，每一个月都生下一对小兔，而所生下的每一对小兔在出生后的第三个月也都生下一对小兔。那么，由一对兔子开始，n 个月后有多少对小兔子呢？

输入

输入一个数字 n（1≤n≤100），代表题目中询问的月份。

输出

对于每个询问，输出一行整数，代表 n 月的时候，小兔子的数量。

样例输入1

4

样例输出1

5

样例输入2

65

样例输出2

27777890035288

数据规模与约定

时间限制：1 s

内存限制：64 M

40% 的数据保证 n≤20

100% 的数据保证 n≤100

解题

我们不妨设定兔子的第一年为幼体兔子，第二年为成年兔子，然后第三年成年兔子能够进行繁殖。

可以大概列出该情况：

我们不难认为，每年成年的兔子数为【上一年成年兔子】+【上一年幼年兔子】之和，即【上一年兔子总数】。我们用f(n)表示第n年兔子数量，则第n年成年兔子数可表示为f(n-1)。

而每年的幼年兔子数显然等于上一年成年兔子数，也等于上上一年兔子总数，可表示为f(n-2)。

以上不难理解。

我们可以用函数表达：

于是我们可以完成代码：

#include <iostream>
using namespace std；
int f(int n) {
	if (n <= 2)return n;
	return f(n - 1) + f(n - 2);
}
int main()
{
	int n;
	cin >> n;
	cout << f(n);
	return 0;
}

代码优化

在执行代码过程中，我们发现当n稍大时，程序便会发生超时。实际上，这是因为递归调用时产生大量非必要重复运算。

如图，红色部分是重复运算。实际上，我们只需要使用蓝色部分的结果即可。我们可以用记忆化的技巧来优化代码。即定义一个数组来存储运算结果。

本题运算结果较大，我们可用long long 类型来表示。

#include <iostream>
#define MAX_N 100

using namespace std;
long long arr[MAX_N+5] = { 0 };
long long f(long long n) {
	if (n <= 2)return n;
	if (arr[n])return arr[n];
	arr[n]= f(n - 1) + f(n - 2);
	return arr[n];
}
int main()
{
	long long n;
	cin >> n;
	cout << f(n);
	return 0;
}