算法04 模拟算法之一维数组相关内容详解【C++实现】

大家好,我是bigbigli,模拟算法我们将分为几个章节来讲,今天我们只看一维数组相关的题目

目录

模拟的概念

训练:开关灯

解析

参考代码

训练:数组变化

解析

参考代码

训练:折叠游戏

解析

参考代码


模拟的概念

模拟算法就是模拟题目给的操作,用代码一步一步的描述出来即可。在过程中使用的都是我们已知的各种方法,如数组元素调用、排序、枚举等等,只是这些过程一般比较复杂。本次课程主要针对一维数组的模拟。

在各类算法竞赛中,包括CSP-J/S,NOIP等竞赛,经常会出现各类“模拟题目”,遇到这种题大家不需要害怕,甚至可以将其作为“送分题”,因为你只需要按照题目叙述的方式来写程序就能得到最终答案。模拟不是一种算法,而是一种技巧,要想掌握模拟题目,就需要多读题、多整理细节问题。

训练:开关灯

有n盏灯,从1到n按顺序依次编号,初始时所有灯都处于开启状态;有m个人,从1到m依次编号。

第一个人将灯全部关闭,第二个人将编号为2的倍数的灯打开,第三个人将编号为3的倍数的灯做相反处理(即将打开的灯关闭,将关闭的灯打开)。依照编号递增顺序,以后的人都一样,将凡是自己编号倍数的灯做相反处理。

请问:当第m个人操作之后,哪几盏灯是关闭的,按从小到大输出其编号,用逗号间隔。

【输入描述】一行,n和m,空格隔开

【输出描述】顺次输出关闭的灯的编号,用逗号隔开

【输入样例】10 1010

【输出样例】1,4,9

 

解析

因为灯只会出现0和1两种情况,我们可以使用数组元素来表示(类似桶),随后只需要重复m次,每次寻找当前序号的倍数为下标的元素进行更改,如果是1就变成0,是0就变成1。

最后对数组元素进行判断,找出是0的元素,就行数组元素下标的输出。

输出时要注意的问题是用逗号隔开不同于用空格隔开。

 

参考代码

#include<iostream>
using namespace std;
int a[1010];//全部是0,表示关闭
int main()
{int n,m;cin>>n>>m;for(int i=2;i<=m;i++)//从第二个人开始操作for(int j=i;j<=n;j+=i)//编号对应倍数下标if(a[j]==1)    a[j]=0;else a[j]=1;//更改状态cout<<1;//1号肯定关闭for(int i=2;i<=n;i++)if(a[i]==0)    cout<<","<<i;//间隔逗号输出return 0;
}

训练:数组变化

现有一个长度为n的数组,对这个数组进行m次操作,可以对数组进行的操作分为以下三类:

输入1 i:   表示输出数组中第i个元素的值;

输入2 i v: 表示在数组中第i个元素前加入新的元素v;

输入3 i:   表示删除数组中的第i个元素。

注意:三类操作都要满足 i <= n。

【输入描述】第1行:n,表示数组的初始长度

第2行:n个用空格间隔的数,表示原始的数组

第3行:m,表示操作的次数

接下来的m行分别是每次对数组进行的操作(题目描述中的三类操作中的一种)

【输出描述】对于第一种操作输出对应的答案,一行输出一个数。

【样例输入】

5
6 7 8 9 10
5
1 2
2 2 12
1 2
3 3
1 3

【样例输出】

7
12
8

解析

对题目的要求一步一步的实行,先保证数组的输入以后,需要对三种情况进行分类处理。第一种处理里面有输出,后面两种都是在操作。操作的要点是数组的插入和删除。插入的话,就要求插入位置后面所有数字向后移动一步,实现a[i+1]=a[i]的操作;而删除则需要当前位置后面所有的数字向前移动一步,实现a[i]=a[i+1]。这里需要注意移动的方向,要从头移动。

参考代码

#include<iostream>
using namespace std;
int a[1001];
int main()
{int n,m,p,q,v;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cin>>m;for(int i=0;i<m;i++){cin>>p;if(p==1){cin>>q;cout<<a[q]<<endl;}else if(p==2){cin>>q>>v;for(int j=n;j>=q;j--)//挨个向后移动a[j+1]=a[j];a[q]=v;//单独把插入的数字放入位置n++; //数组长度加1}else  if(p==3){cin>>q;for(int j=q;j<n;j++)//挨个向前移动a[j]=a[j+1];n--;//数组长度减1}}return 0;
}

训练:折叠游戏

小明和小华在玩数组折叠游戏,游戏规则是,给出n个整数,按照从左到右的顺序排列,现在需要将这列整数从中间折叠m次,右边的叠加到左边,每次折叠后,重合的两个数字会相加变成一个新的数字。请你输出折叠m次后的s数组。

【输入描述】第1行:输入一个整数n表示序列的长度,输入一个整数m表示折叠的次数。

第2行:输入n个空格隔开的整数,整数不超过100。

【输出描述】输出折叠m次后的数组。

【输入样例】

5 2
1 2 3 4 5

【输出样例】

9 6

解析

数组对折,需要把后半部分移动到前半部分对应位置进行数组相加,所以移动次数为n/2(即循环次数)。

然后需要进行的就是数组加法。

最后要对数组长度也做n/2的操作。

但是这里需要注意的是,如果长度是奇数不能只是简单的n/2哦。

 

参考代码

#include<iostream>
using namespace std;
int a[10010];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)    cin>>a[i];for(int i=1;i<=m;i++){for(int j=1;j<=n/2;j++)a[j]+=a[n-j+1];if(n%2!=0)n++;n/=2;}for(int i=1;i<=n;i++)cout<<a[i]<<' ';return 0;
}

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/356790.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

动态ARP

定义 动态ARP表项由ARP协议通过ARP报文自动生成和维护&#xff0c;可以被老化&#xff0c;可以被新的ARP报文更新&#xff0c;可以被静态ARP表项覆盖。 动态ARP适用于拓扑结构复杂、通信实时性要求高的网络。 ARP地址解析过程 动态ARP通过广播ARP请求和单播ARP应答这两个过…

33 - 连续出现的数字(高频 SQL 50 题基础版)

33 - 连续出现的数字 -- 开窗函数lead(col,n) 统计窗口内往下第n行值 -- over(partition by xxx) 按照xxx所有行进行分组 -- over(partition by xxx order by aaa) 按照xxx分组&#xff0c;按照aaa排序select distinct num as ConsecutiveNums from(select num,# 从当前记录获…

运行vue3项目相关报错

1. VSCode打开TSVue3项目很多地方报错 报错内容 几乎所有文件都会出现未知飘红 error Delete CR prettier/prettier报错原因 插件冲突&#xff0c;Windows系统回车换行符与MAC不一致&#xff08;所以这个问题Windows系统才会出现&#xff09; 解决 需要安装Vue - Official…

永磁同步电机FOC调试记录(一)

永磁同步电机FOC调试记录&#xff08;一&#xff09; 前言架构硬件架构软件架构 调试过程元器件选型开环控制编码器调试速度采样电流检测中断优先级的确定电流环部分烧坏IPM速度-电流环位置-电流环 结语 前言 这是我个人从零开始尝试永磁同步电机&#xff08;PMSM&#xff09;…

【LeetCode刷题】232.用栈实现队列

目录 题目链接 图解思路 整体结构 实现过程 入队列 出队列 实现代码 MyQueue.h MyQueue.c stack.h stack.c test.c 题目链接 232. 用栈实现队列 - 力扣&#xff08;LeetCode&#xff09; 图解思路 整体结构 实现过程 入队列 插入数据时&#xff0c;插入到ist。…

尚品汇-(四)

&#xff08;1&#xff09;商品的基本知识 1.1基本信息—分类 一般情况可以分为两级或者三级。咱们的项目一共分为三级&#xff0c;即一级分类、二级分类、三级分类。 比如&#xff1a;家用电器是一级分类&#xff0c;电视是二级分类&#xff0c;那么超薄电视就是三级分类。…

《计算机英语》 Unit 5 Networking 网络

Section A Networking 网络 The need to share information and resources among different computers has led to linked computer systems, called networks, in which computers are connected so that data can be transferred from machine to machine. 不同计算机之间共享…

路由器基础配置以及静态路由配置

1、搭建网络 搭建网络拓扑、分配IP地址、划分网段、连接端口 2、配置路由器 路由器基础配置 //进入全局配置模式 Router#enable Router#conf t Enter configuration commands, one per line. End with CNTL/Z.//配置高速同步串口serial2/0 Router(config)#int ser2/0 Route…

Linux-Https协议

文章目录 前言一、Https协议二、常见的加密方式对称加密非对称加密数据摘要&&数据指纹中间人攻击 三、Https的加密历程方案1-只使用对称加密方案2-只使用非对称加密方案3-双方都使用非对称加密方案4-非对称加密对称加密 四、CA证书什么是CA证书CA证书的合法性如何生成.…

学习笔记——路由网络基础——动态路由

五、动态路由 1、动态路由概述 动态路由&#xff1a;通过在设备上运行某种协议&#xff0c;通过该协议自动交互路由信息的过程。 动态路由协议有自己的路由算法&#xff0c;能够自动适应网络拓扑的变化&#xff0c;适用于具有一定数量三“层设备的网络。 动态路由协议适用场…

深入理解redis持久化—AOF日志

redis为什么需要持久化 redis是内存数据库&#xff0c;redis所有的数据都保存在内存中 如果此时pc关机或重启&#xff0c;那么内存中的用户数据岂不是丢失了&#xff1f;redis这么不安全吗&#xff1f; 作为数据库&#xff0c;保证数据的安全&#xff0c;持久是基本需求&…

【Linux】进程间通信3——system V共享内存

1.system V进程间通信 管道通信本质是基于文件的&#xff0c;也就是说操作系统并没有为此做过多的设计工作&#xff0c;而system V IPC是操作系统特地设计的一种通信方式。但是不管怎么样&#xff0c;它们的本质都是一样的&#xff0c;都是在想尽办法让不同的进程看到同一份由操…

idea导入文件里面的子模块maven未识别处理解决办法

1、File → Project Structure → 点击“Modules” → 点击“” → “Import Model” 2、可以看到很多子模块&#xff0c;选择子模块下的 pom.xml 文件导入一个一个点累死了&#xff0c;父目录下也没有pom文件 解决办法&#xff1a;找到子模块中有一个pom.xml文件&#xff0c;…

Redis 主从同步

主从同步 很多企业没有使用Redis的集群&#xff0c;但是至少都做了主从。有了主从&#xff0c;当master挂掉的时候&#xff0c;运维让从库过来接管&#xff0c;服务就可以继续&#xff0c;否则master需要经过数据恢复和重启的过程&#xff0c;可能会拖很长时间&#xff0c;影响…

web-原生Ajax

概念: Asynchronous JavaScript And XML&#xff0c;异步的JavaScript和XML。 作用: 数据交换:通过Ajax可以给服务器发送请求&#xff0c;并获取服务器响应的数据。 异步交互:可以在不重新加载整个页面的情况下&#xff0c;与服务器交换数据并更新部分网页的技术&#xff0c;如…

MySQL—索引—基础语法

目录 一、创建、查看以及删除索引的语法 &#xff08;1&#xff09;创建索引 1、1会用到一个关键字&#xff1a;CREATE。 1、2增加索引还可以用到另外一个关键字——ALTER TABLE 表名 ADD INDEX ... 。 2、解释。 &#xff08;2&#xff09;查看索引 1、查看索引需要用到…

FreeCAD中类型机制研究

了解FreeCAD类型机制实现原理&#xff0c;为后续FreeCAD相关工作提供参考。 1.实现原理 FreeCAD系统提供一个最上层的基类BaseClass&#xff0c;该类主要处理类型相关工作&#xff0c;几乎所有的FreeCAD的类直接或间接继承于该类。该类只有唯一个属性Type&#xff0c;Type里面…

kotlin类

一、定义 1、kotlin中使用关键字class 声明类,如果一个类没有类体&#xff0c;也可以省略花括号&#xff0c; 默认为public 类型的&#xff1a; // 这段代码定义了一个公开的、不可被继承的Test类 class Test{} // 没有类体&#xff0c;可以省略花括号 class Test 底层代码&…

【菜狗学前端】uniapp(vue3|微信小程序)实现外卖点餐的左右联动功能

记录&#xff0c;避免之后忘记...... 一、目的&#xff1a;实现左右联动 右->左 滚动&#xff08;上拉/下拉&#xff09;右侧&#xff0c;左侧对应品类选中左->右 点击左侧品类&#xff0c;右侧显示对应品类 二、实现右->左 滚动&#xff08;上拉/下拉&#xff09;右…

利口 202. 快乐数

力扣 202. 快乐数 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为&#xff1a; 对于一个正整数&#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1&#xff0c;也可能是 无限循环 但始终变不到 1。如果这个过程 结…