复试算法练习Day07

news/2024/10/30 9:27:52/

复试算法练习Day07

文章目录

  • 复试算法练习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)

小结

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


http://www.ppmy.cn/news/12241.html

相关文章

C# Dictionary(字典)各种属性的用法

C# Dictionary(字典&#xff09;各种属性的用法 要使用Dictionary集合&#xff0c;需要导入C#泛型命名空间&#xff01; ​System.Collections.Generic​&#xff08;程序集&#xff1a;mscorlib&#xff09; Dictionary的描述 1、从一组键&#xff08;Key&#xff09;到一组值…

【饥荒】本地服务器+内网穿透

本地服务器搭建方法 准备工具 网易UU加速器&#xff08;用于加速科雷官网登陆和steam创意工坊&#xff09;Don’t Starve Together Dedicated Server(steam饥荒联机版开服工具) 获取方法&#xff1a;在库中勾选工具&#xff0c;然后搜索Don’t Starve Together Dedicated Ser…

华为VRRP、BFD实验配置

目录 VRRP实验配置 BFD实验配置 配置单跳检测 配置多跳检测 配置单臂回声 BFD与路由协议联动配置 BFD与OSPF联动 BFD与ISIS联动 BFD与BGP联动 VRRP实验配置 VRRP配置 AR1配置&#xff08;VRRP缺省优先级100&#xff09; int g0/0/0 ip add 192.168.10.1 24 vrrp vrid …

Spring Boot Apollo监听namespace并更新配置Bean(附源码)

这里是weihubeats,觉得文章不错可以关注公众号小奏技术&#xff0c;文章首发。拒绝营销号&#xff0c;拒绝标题党 背景 如果我们使用的配置中心是apollo的话我们经常会遇到这样的问题&#xff0c;就是动态更新配置Bean 动态更新配置bean 动态更新配置bean其实是很简单的&…

Himall商城ExpressDaDaHelper订单预发布 查询运费后发单接口

/// <summary> /// 订单预发布 查询运费后发单接口 /// </summary> /// <param name="source_id">商户编号</param> /// <param name="deliveryNo">平台订单编号</param> //…

[LCTF]bestphp2022安洵杯 babyphp

目录 <1> [LCTF]bestphp‘s revenge SoapClient触发反序列化导致ssrf serialize_hander处理session方式不同导致session注入 crlf漏洞 <2> 安洵杯 babyphp SoapClient 触发ssrf session反序列化 利用文件操作原生类读取flag <3> XCTF Final Web1 解…

12.30

反解 vim /var/named/chroot/etc/named.rfc1912.zones zone "a.com" { type master; file "a.com.zone"; }; zone "1.168.192.in-addr.arpa" { type master; file "192.168.1…

NET餐厅管理系统前端js-dwz.dialog打开一个层

//打开一个层 open:function(url, dlgid, title, options) { var op $.extend({},$.pdialog._op, options); var dialog $("body").data(dlgid); //重复打开一个层 if(dialog) { if(dial…