复试算法练习Day07

题目描述

有一种兔子，从出生后第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)

小结

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