【C++题解】1238. 统计每个月兔子的总数

本文主要是介绍【C++题解】1238. 统计每个月兔子的总数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》

问题：1238. 统计每个月兔子的总数

类型：函数、递归

题目描述：

有一对兔子，从出生后第 3 个月起每个月都生一对兔子，一对小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死。

问第 n 个月（ n≤50 ）的兔子总数为多少对？

输入：

输入 1 个整数 n ，表示第几个月。

输出：

第 n 个月兔子的总数量有多少对？

样例：

输入：

输出：

在这里插入图片描述

完整代码如下：

#include<bits/stdc++.h>
using namespace std;int dg(int d){int r;if(d==1||d==2){r=1;}else{r=dg(d-1)+dg(d-2);}return r;}int main(){//一、分析问题//已知：1 个整数 n ，表示第几个月。//未知：第 n 个月兔子的总数量有多少对？//关系: 递归 //二、定义变量（已知、未知、关系）int n,res; //三、输入已知cin>>n;//四、根据关系计算res=dg(n);//五、输出未知 cout<<res;return 0;
}

虽然该解法可以正确求出题目的解，但是当n很大时，会出现超时的问题。

改进方法：

#include<bits/stdc++.h>
using namespace std;
int main(){//一、分析问题//已知：一对兔子 //未知：n月后兔子总数 //关系:每3个月生一对 小兔子，小兔子三个月生一对 //二、定义变量（已知、未知、关系）int n; vector<long long> v(2);//三、输入已知cin>>n;//四、根据关系计算v[0]=1;v[1]=1;for(int i=2;i<n;i++){v.push_back(v[i-1]+v[i-2]);}//五、输出未知 cout<<v.back();return 0;
}