当前位置: 首页 > news >正文

算法01 递推算法及相关问题详解【C++实现】

目录

递推的概念

训练:斐波那契数列

解析

参考代码

训练:上台阶

参考代码

训练:信封

解析

参考代码

递推的概念

递推是一种处理问题的重要方法。

递推通过对问题的分析,找到问题相邻项之间的关系(递推式),从起点出发(首项或者末项)然后使用循环不断地迭代,得到最后需要的结果。

训练:斐波那契数列

对于Fibonacci数列,已知:fib(1) = 1; fib(2) = 1; 从第三项开始满足公式fib(i) = fib(i-1) + fib(i-2)。输入一个整数n(1<=n<=100),求fib(n)的值。

【输入描述】一行:一个整数n。

【输出描述】一行:feibonacci数列第n项的值

【样例输入】5

【样例输出】5

解析

1.问题求的是斐波那契数列第i项的数值。

2.前两项的数值,题目中已经给出,分别为:

fib(1) = 1; fib(2) = 1;

3.从第3项开始,满足如下规律:

fib(i) = fib(i-1) + fib(i-2);

即当前项由前两项之和构成。

4.我们可以根据题目给出的fib(1)、fib(2)推出fib(3),

再按照顺序由fib(2)、fib(3)推出fib(4),以此类推。

参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{long long n,f1,f2,f3;cin>>n;f1=f2=f3=1;//初始化,f3表示第n项for(long long i=3;i<=n;i++){f3=f1+f2;f1=f2;f2=f3;}cout<<f3;return 0;
}

训练:上台阶

楼梯有n(1<=n<=100)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶,编程计算共有多少种不同的走法。

【输入描述】输入的每一行包括一组测试数据,即为台阶数n。最后一行为0,表示测试结束。

【输出描述】每一行输出对应一行输入的结果,即为走法的数目。

【样例输入】

1
2
3
4
0

【样例输出】

1
2
4
7

参考代码

#include<bits/stdc++.h>
using namespace std;
long long a[105];
//a[i]表示i层楼梯方案数
int main()
{int n,t;a[1]=1,a[2]=2,a[3]=4;//边界条件while(1){cin>>t;if(!t) break;if(a[t]){           //如果已经计算过,直接输出cout<<a[t]<<endl;continue;}for(int i=4;i<=t;i++)a[i]=a[i-1]+a[i-2]+a[i-3];//从第4层楼梯开始//每一步有3种方案:1阶、2阶、3阶//分别对应 a[i-1]、a[i-2]、a[i-3]cout<<a[t]<<endl;}return 0;
}

训练:信封

现在有n封信和n个信封,如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。

【输入描述】1行:输入一个整数n。

【输出描述】1行:输出一个整数,表示所有的情况数。

【样例输入】4

【样例输出】9

解析

先任取一封信,此时可供选择的信封有:n-1种情况。

每种情况下,我们在放置这封信的时候有2种方案:

  1. 这封信的位置,不与剩余的任意一封信互换,此时,剩余的问题就是:将n-1封信,错放在n-1个信封里,即f(n-1)
  2. 这封信的位置,与剩余的任意一封信互换,此时会有2个信封被使用掉。剩余的问题就是:将n-2封信,错放在n-2个信封里,即f(n-2),得出递推式:f(n)=(n-1)*(f(n-1)+f(n-2))。边界是:f(1)=0,f(2)=1

参考代码

#include<bits/stdc++.h>
using namespace std;
long long f[25];
int main()
{int n;cin>>n;f[1]=0,f[2]=1;for(int i=3;i<=n;i++){f[i]=(i-1)*(f[i-1]+f[i-2]);}cout<<f[n];return 0;
}

 从入门到算法,再到数据结构,查看全部文章请点击此处​icon-default.png?t=N7T8http://www.bigbigli.com/

相关文章:

算法01 递推算法及相关问题详解【C++实现】

目录 递推的概念 训练&#xff1a;斐波那契数列 解析 参考代码 训练&#xff1a;上台阶 参考代码 训练&#xff1a;信封 解析 参考代码 递推的概念 递推是一种处理问题的重要方法。 递推通过对问题的分析&#xff0c;找到问题相邻项之间的关系&#xff08;递推式&a…...

自动化测试火狐下载文件

本篇文章介绍selenium中火狐浏览器如何下载文件。比如我想把这个MP4的视频文件下载下来。 点击之后查看下载的类型是video/mp4 指定使用火狐浏览器 profile webdriver.FirefoxOptions() # 设置firefox默认的下载路径&#xff0c;0表示桌面&#xff0c;1表示我的下载&#xf…...

基于JSP技术的定西扶贫惠农推介系统

开头语&#xff1a;你好呀&#xff0c;我是计算机学长猫哥&#xff01;如果有相关需求&#xff0c;文末可以找到我的联系方式。 开发语言&#xff1a;JSP 数据库&#xff1a;MySQL 技术&#xff1a;B/S架构、JSP技术 工具&#xff1a;Eclipse、MySQL、Tomcat 系统展示 首…...

Linux 终端窗口设置为透明

Linux 终端窗口设置为透明 打开终端 右键鼠标 选择Profile Preferences 点击Background 选择 Transparent background 拖动滑条调整透明度 完成。...

MySQL 中 Varchar(50) 和 varchar(500) 区别是什么?

一. 问题描述 我们在设计表结构的时候&#xff0c;设计规范里面有一条如下规则: 对于可变长度的字段&#xff0c;在满足条件的前提下&#xff0c;尽可能使用较短的变长字段长度。 为什么这么规定&#xff1f;我在网上查了一下&#xff0c;主要基于两个方面 基于存储空间的考…...

强化RAG:微调Embedding还是LLM?

为什么我们需要微调&#xff1f; 微调有利于提高模型的效率和有效性。它可以减少训练时间和成本&#xff0c;因为它不需要从头开始。此外&#xff0c;微调可以通过利用预训练模型的功能和知识来提高性能和准确性。它还提供对原本无法访问的任务和领域的访问&#xff0c;因为它…...

提取 Excel单元格文本下的超链接

在Excel中&#xff0c;可以使用内置的函数来提取单元格中的超链接地址。如果你有一个包含超链接的单元格&#xff0c;例如B1&#xff0c;你可以使用以下步骤来提取这个超链接&#xff1a; 在一个新的单元格&#xff08;例如C1&#xff09;中&#xff0c;输入以下公式&#xff…...

一键安全体检!亚信安全携手鼎捷软件推出企业安全体检活动 正式上线

亚信安全联合鼎捷软件股份有限公司&#xff08;以下简称“鼎捷软件”&#xff09;正式推出“一键安全体检”服务。亚信安全网络安全专家将携手鼎捷软件数据安全专家&#xff0c;围绕企业的数智安全状况&#xff0c;进行问题探索与治愈、新问题预测与预警&#xff0c;在全面筛查…...

numpy - array(1)

一维数据&#xff1a;向量 二位数据&#xff1a;矩阵 维度超过三维的数据&#xff1a;张量 这些数据在numpy中统称array (1)使用穷举法创建多为数据,接受列表或者元组类型的数据 a numpy.array([1, 2, 3]) b numpy.array([[1, 2, 3], (4, 5, 6), [7, 8, 9]]) (2)创建所有元…...

师彼长技以助己(6)递归思维

师彼长技以助己&#xff08;6&#xff09;递归思维 递归思维-小游戏 思维小游戏 思维 小游戏&#xff1a;1 玩一个从1或2开始往上加的游戏&#xff0c;谁加到20就赢 如何保证一定赢呢&#xff1f;我们倒推&#xff0c;要先到20的话&#xff0c;谁先到17就赢&#xff0c;如此…...

Kali Linux 2024.2

Kali Linux 2024.2 版本&#xff08;t64、GNOME 46 和社区包&#xff09; 比平常晚了一点&#xff0c;但 Kali 2024.2 来了&#xff01;延迟是由于实现这一目标的幕后变化所致&#xff0c;这也是人们关注的焦点。社区提供了大量帮助&#xff0c;这次他们不仅添加了新的软件包&…...

【Spine学习08】之短飘,人物头发动效制作思路

上一节说完了跑步的&#xff0c; 这节说头发发型。 基础过程总结&#xff1a; 1.创建骨骼&#xff08;头发需要在上方加一个总骨骼&#xff09; 2.创建网格&#xff08;并绑定黄线&#xff09; 3.绑定权重&#xff08;发根位置的顶点赋予更多总骨骼的权重&#xff09; 4.切换到…...

chatgpt的命令词

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌…...

用python把docx批量转为pdf

为保证转换质量&#xff0c;本文的方法是通过脚本和com技术调用office自带的程序进行转换的&#xff0c;因此需要电脑已经装有office。如果希望不装office也能用&#xff0c;则需要研究OpenXML技术&#xff0c;后面实在闲的慌&#xff08;退休&#xff09;再搞。 安装所需库 …...

项目采购管理

目录 1.概述 2.三个子过程 2.1.规划采购管理 2.2.实施采购 2.3.控制采购 2.4.归属过程组 3.应用场景 3.1.十个应用场景 3.2.软件开发项目 3.2.1. 需求识别和分析 3.2.2. 制定采购计划 3.2.3. 发布采购请求 3.2.4. 供应商评估与选择 3.2.5. 合同签订 3.2.6. 采购…...

Elasticsearch 认证模拟题 - 18

一、题目 为一个索引&#xff0c;按要求设置以下 dynamic Mapping 一切 text 类型的字段&#xff0c;类型全部映射成 keyword一切以 int_ 开头命名的字段&#xff0c;类型都设置成 integer 1.1 考点 字段的动态映射 1.2 答案 # 创建索引和索引模板 PUT my_index {"m…...

Python基础-速记笔记

Python的基础数据类型都有哪些&#xff1f; 1、字符串(string)2、布尔类型(bool)3、整数(int) 4、浮点数(float)5、列表(list)6、集合(set)7、元组(tuple)8、字典(dict) 其中不可变类型有&#xff1a; 字符串(string)、布尔类型(bool)、整数(int) 、浮点数(float)、元组(tup…...

青少年编程与数学 01-001开始使用计算机 02课题、计算机操作系统3_3

青少年编程与数学 01-001开始使用计算机 02课题、计算机操作系统3_3 四、Linux操作系统安装&#xff08;一&#xff09; 准备工作&#xff08;二&#xff09;设置BIOS/UEFI&#xff08;三&#xff09; 安装Linux&#xff08;四&#xff09;磁盘分区&#xff08;五&#xff09;安…...

填表统计预约打卡表单系统(FastAdmin+ThinkPHP+UniApp)

填表统计预约打卡表单系统&#xff1a;一键搞定你的预约与打卡需求​ 填表统计预约打卡表单系统是一款基于FastAdminThinkPHPUniApp开发的一款集信息填表、预约报名&#xff0c;签到打卡、活动通知、报名投票、班级统计等功能的自定义表单统计小程序。 &#x1f4dd; 一、引言…...

IO模型和多路转接

叠甲&#xff1a;以下文章主要是依靠我的实际编码学习中总结出来的经验之谈&#xff0c;求逻辑自洽&#xff0c;不能百分百保证正确&#xff0c;有错误、未定义、不合适的内容请尽情指出&#xff01; 文章目录 1.IO 概要1.1.IO 低效原因1.2.IO 常见模型1.2.1.阻塞 IO1.2.2.非阻…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...