题目描述

有一种兔子从出生后第3个月起每个月都生一只兔子小兔子长到第三个月后每个月又生一只兔子。

例子假设一只兔子第3个月出生那么它第5个月开始会每个月生一只兔子。

一月的时候有一只兔子假如兔子都不死问第n个月的兔子总数为多少

数据范围输入满足 1≤n≤31

题目来源

(https://www.nowcoder.com/practice/1221ec77125d4370833fd3ad5ba72395tpId=37&tqId=21260&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D37%26type%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=)

输入描述

输入一个int型整数表示第n个月

输出描述

输出对应的兔子总数

输入
3
输出
2

思路

根据兔子出生的规律我们可以看到

第一个月1对兔子

第二个月1对兔子

第三个月2对兔子

第四个月2+1对兔子

第五个月3+2对兔子

第六个月5+3对兔子

由此可以归纳出来除了前两个月后面的月份的兔子的个数都是前两个月的兔子的总和符合斐波那契数列即f(n) = f(n-1)+f(n-2)。

由此可以采用动态规划把除一二月份的兔子总数之外将前两个月份的兔子数量相加就是后面的月份兔子总数rm[i]=rm[i−1]+rm[i−2]

具体实现

//利用斐波那契数列实现统计每个月兔子总数
#include<iostream>
#include<vector>
//初始化
using namespace std;
 
int main(){
    //兔子数量初始化
    int n;
    //动态遍历rm数组一次设置动态规划数组rm长度为n
    //执行n次即可得到那个月后兔子总数结果
    while (cin >>n){
        vector<int> rm(n+1);
        rm[1]= 1;
        rm[2]= 1;
        //递归方程为rm[i]=rm[i−1]+rm[i−2]
        for(int i = 3; i<=n; ++i){
            rm[i] = rm[i-1] + rm[i-2];
        }
        cout << rm[n] << endl;
    }
    return 0;
}

//这道题是斐波那契数列的生活应用
//可以将第n个月的兔子数可分为两部分
// 1.上个月已经有的兔子数为f(n-1)
// 2.新生的兔子数即在第n月时已经满三个月的兔子数为f(n-2)

#include <iostream>
using namespace std;

//通过建立getNum()函数
//利用斐波那契数列的递推则可以给出兔子总数
int getNum(int n)
{
	int ret,f1 = 1, f2 = 1; //前两个月都是一只
	for (int i = 3; i <= n;++i) //从第三个月开始到第n月
	{
		ret = f1 + f2;
		f1 = f2;
		f2 = ret;
	}
	return ret;
}

int main()
{
	int n;
	while (cin >> n)
		cout << getNum(n) << endl;
	return 0;
}

时间、空间复杂度

由于直接遍历了rm数组一次时间复杂度为O(n),在设计动态规划得到时候采用的辅助数组rm的长度为n因此其空间复杂度为O(n)

小结

通过采用动态规划对于需要输出的兔子总数进行总结归纳采用斐波那契数列的递推公式的设计通过建立动态规划辅助数组可以很好的利用斐波那契数列从而给出算法的结果很大方面提高了计算的效率对于设计与处理生活问题有很好的借鉴。