兔子问题 时间限制：C/C++ 1000MS 内存限制：C/C++ 256MB

Question

兔子问题
描述

意大利数学家斐波那契(L.Fibonacci)在他的1228年版的《算经》一书中记述了有趣的兔子问题:假定每对成年兔子每月能生一对小兔子，而每对小兔子过了一个月就长成了成年兔子。如果不发生死亡，那么由一对成年兔子开始，输入度过的月数，输出该月月末共有多少对兔子。

输入描述
一行一个整数n(n<=20)，代表度过的月数。

输出描述
一行一个整数，兔子的对数。

样例输入 1
12
样例输出 1
144

样例输入 2
5
样例输出 2
5

提示
【数据规模与约定】
对于100%的数据，满足0<n≤20。

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

这是一个经典的斐波那契数列问题。在这个问题中，每个月的兔子数量是由前两个月的兔子数量决定的，第一个月和第二个月是一对成年兔子，之后每个月的兔子数量是前两个月的总和。因此，我们可以使用动态规划来解决这个问题。下面是一个使用C++实现的解决方案：

#include <iostream>
using namespace std;

int main() {
    int n; // 输入的月数
    cin >> n; // 输入月数
    int a = 1, b = 1, c; // 分别代表第一个月、第二个月和当前月的兔子数量
    if (n == 1 || n == 2) { // 如果是第一个月或第二个月，直接返回对应的兔子数量
        cout << a << endl;
        return 0;
    }
    for (int i = 3; i <= n; ++i) { // 从第三个月开始计算每个月的兔子数量
        c = a + b; // 当前月的兔子数量等于前两月的兔子数量的和
        a = b; // 更新下一个月的a值为当前的b值
        b = c; // 更新下个月的b值为当前的c值
    }
    cout << c << endl; // 输出最后一个月的兔子数量
    return 0;
}

在这个程序中，我们首先输入月数n。如果n为1或2，我们直接返回对应的兔子数量。对于其他情况，我们使用一个循环从第三个月开始计算每个月的兔子数量，最后输出最后一个月的兔子数量。注意我们使用了三个变量a、b和c来分别存储前两个月的兔子数量和当前月的兔子数量。