【华为练习题 】 长寿的兔子

2024-01-27 08:18
文章标签 华为 练习题 兔子 长寿

本文主要是介绍【华为练习题 】 长寿的兔子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【华为练习题 】 长寿的兔子

题目

从前有一对长寿的兔子,他们每个月生出一对小兔子,第一个月新生产的兔子两个月就长大了,在第三个月初开始生他们的下一代小兔子,这样一代一代的生下去,不考虑兔子的寿命,求第n个月出生多少对小兔子

简单示例:

比如输入1,第一个月出生的兔子只有一对,所以输出为1
比如输入2,第二个月出生的兔子只有一对,所以输出为1
比如输出为3,则该月份有两对兔子出生,则输出为2

要求:

实现以下接口:
输入一个正整数,表示第几个月,输出该月份生产出的小兔子的对数
调用者会保证:
输入的月份与生产的兔子数目都为unsigned int 能表达的数字

分析

非递归:将兔子分为大中小3类(大兔子:可以产小兔子,中兔子:成长1个月的小兔子,下个月会变成大兔子),每个月的大兔子数量为上个月的大兔子数量加上中兔子数量,中兔子数量为上个月小兔子数量,小兔子数量为上个月大兔子数量。
递归:某月出生的兔子数量等于大兔子数量,大兔子数量等于上个月的大兔子数量加上中兔子数量,而上个月的中兔子数量等于上上个月的小兔子数量,等于上上上个月的大兔子数量,于是得到递推式:
f(n) = f(n-1) + f(n-3) (n>=3)

解答

非递归方式

#include <iostream>
using namespace std;unsigned rabbit(unsigned n){unsigned  big = 1, mid = 0, little = 0;while (n--){unsigned tmp1 = big, tmp2 = mid, tmp3 = little;big = tmp1 + tmp2;mid = tmp3;little = tmp1;}return big;
}int main()
{unsigned n;cin >> n;cout << rabbit(n) << endl;return 0;
}

递归方式

#include <iostream>
using namespace std;unsigned rabbit(unsigned n){if (n <= 2) return 1;return rabbit(n-1) + rabbit(n-3);
}int main()
{unsigned n;cin >> n;cout << rabbit(n) << endl;return 0;
}

这篇关于【华为练习题 】 长寿的兔子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/649622

相关文章

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

828华为云征文|华为云Flexus X实例docker部署rancher并构建k8s集群

828华为云征文|华为云Flexus X实例docker部署rancher并构建k8s集群 华为云最近正在举办828 B2B企业节,Flexus X实例的促销力度非常大,特别适合那些对算力性能有高要求的小伙伴。如果你有自建MySQL、Redis、Nginx等服务的需求,一定不要错过这个机会。赶紧去看看吧! 什么是华为云Flexus X实例 华为云Flexus X实例云服务是新一代开箱即用、体

华为OD机试真题-学生方阵-2024年OD统一考试(E卷)

题目描述 学校组织活动,将学生排成一个矩形方阵。 请在矩形方阵中找到最大的位置相连的男生数量。这个相连位置在一个直线上,方向可以是水平的,垂直的,成对角线的或者呈反对角线的。 注:学生个数不会超过10000 输入描述 输入的第一行为矩阵的行数和列数, 接下来的 n行为矩阵元素,元素间用""分隔。 输出描述 输出一个整数,表示矩阵中最长的位

华为 HCIP-Datacom H12-821 题库 (13)

有需要题库的可以看主页置顶 1.可以携带外部路由的 tag 标签信息的是以下哪一类 LSA? A、4 类 LSA B、5 类 LSA  C、3 类 LSA  D、2 类 LSA 答案:B 解析: 暂无解析 2..两台路由器直连,并设定网络类型为 p2p 建立OSPF 邻居。那么两台路由器传输 OSPF 报文的目的 IP 地址是以下哪一项? A、使用组播地址 224.0.0.6 B

4G模块、WIFI模块、NBIOT模块通过AT指令连接华为云物联网服务器(MQTT协议)

MQTT协议概述 MQTT(Message Queuing Telemetry Transport)是一种轻量级的消息传输协议,它被设计用来提供一对多的消息分发和应用之间的通讯,尤其适用于远程位置的设备和高延迟或低带宽的网络。MQTT协议基于客户端-服务器架构,客户端可以订阅任意数量的主题,并可以发布消息到这些主题。服务器(通常称为MQTT Broker)则负责接受来自客户端的连接请求,并转发消

华为23年笔试题

消息传输 题目描述 在给定的 m x n (1 <= m, n <= 1000) 网格地图 grid 中,分布着一些信号塔,用于区域间通信。 每个单元格可以有以下三种状态:  值 0 代表空地,无法传递信号;  值 1 代表信号塔 A,在收到消息后,信号塔 A 可以在 1ms 后将信号发送给上下左右四个方向的信号塔; 值 2 代表信号塔 B,在收到消息后,信号塔 B 可以在 2ms

实现的动态规划问题华为笔试题C++实现

秋招刷力扣题,我觉得我对动态规划不是熟练,在此处做总结 动态规划(Dynamic Programming,DP)算法通常用于求解某种具有最优性质的问题。在这类问题中,可能会有许多可行解,每一个解都对应一个值,我们希望找到具有最优值的解。我觉得最大的问题就是对问题的分解,分解后的问题与分解前的问题具有相同的决策机制,将决策机制进行抽象,最终可以得到对应的解; 动态规划中开始介绍的爬楼梯等问题,答

C语言练习题之 数组中出现次数超过一半的数

题目描述 给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。 数据范围:n≤50000,数组中元素的值0≤val≤10000 要求:空间复杂度:O(1),时间复杂度O(n) 输入描述: 保证数组输入非空,且保证有

828华为云征文|基于华为云Flexus云服务器X实例部搭建Halo博客平台

华为云征文|基于华为云Flexus云服务器X实例部搭建Halo博客平台 前言一、Flexus云服务器X实例介绍1.1 Flexus云服务器X实例简介1.2 Flexus云服务器X实例特点1.3 Flexus云服务器X实例使用场景 二、Halo介绍2.1 Halo 简介2.2 Halo 特点 三、本次实践介绍3.1 本次实践简介3.2 本次环境规划 四、购买华为云Flexus云服务器X实例4.

三方登录 - 华为登录

1.1. 开发准备 当应用需要使用以下开放能力的一种或多种时,为正常调试运行应用,需要预先添加公钥指纹 Account Kit(华为帐号服务)Call Kit(通话服务)Game Service Kit(游戏服务)Health Service Kit(运动健康服务)IAP Kit(应用内支付服务)Live View Kit(实况窗服务,当需要使用Push Kit时必须执行此步骤)Map Kit