建成区违法建设治理网站,外汇直播网站建设开发,html5网站引导页,网站建设模板系统1109#xff1a;开关灯 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 假设有N盏灯(N为不大于5000的正整数)#xff0c;从1到N按顺序依次编号#xff0c;初始时全部处于开启状态#xff1b;有M个人(M为不大于N的正整数)也从1到M依次编号。 第一个人(1号)将灯全部关… 1109开关灯 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 假设有N盏灯(N为不大于5000的正整数)从1到N按顺序依次编号初始时全部处于开启状态有M个人(M为不大于N的正整数)也从1到M依次编号。 第一个人(1号)将灯全部关闭第二个人(2号)将编号为2的倍数的灯打开第三个人(3号)将编号为3的倍数的灯做相反处理(即将打开的灯关闭将关闭的灯打开)。依照编号递增顺序以后的人都和3号一样将凡是自己编号倍数的灯做相反处理。 请问当第M个人操作之后哪几盏灯是关闭的按从小到大输出其编号其间用逗号间隔。 【输入】 输入正整数N和M以单个空格隔开。 【输出】 顺次输出关闭的灯的编号其间用逗号间隔。 【输入样例】 10 10 【输出样例】 1,4,9 说明 主要考查一维数组和循环嵌套。 此处将使用两种算法解决。第一种是模拟法较为简单第二种是筛选法较为优秀。 关于筛选法的基本思想可参考文章 【信奥·数论】求区间质数(素数)的算法(进阶篇) 题目概述 编号1~M(MN)个人操作编号为1~N(N5000)盏灯1号把N盏灯全关从2号开始如果灯的编号是人编号的倍数作相反的处理即原来是关的就打开原来是开的就关闭。 到第M个人操作完成后最后输出N盏灯中关闭的编号。 思路分析(方法1适合入门) 以题目输入输出样例为例下图橙色背景数字是打开的灯灰色背景是关闭的灯该数字表示灯的编号。其中红色数字表示要作相反处理的灯号。 图中的这一过程不难理解。M个人可以循环M次而每个人对N盏灯中相关的灯进行相反操作可以循环N次。很明显使用循环嵌套的框架即可。 M个人中每个人都对N盏灯进行遍历和相反操作所以M个人的循环作为外层而N盏灯的循环作为内层。循环嵌套代码框架如下 灯有两个状态(开/关)即有两个值且每个人都对灯进行操作所以N盏灯肯定需要使用一维数组存储。 N盏灯的编号从1开始对应数组下标为1的元素所以数组下标为0的元素不使用从下标1开始使用方便写代码。如果N5000那么最后一盏灯的下标是5000。如果数组下标为5000的元素那么声明数组时数组的长度不能小于5001。所以声明如下变量和数组 第1个人关闭所有灯从第2个人开始才是以倍数的形式操作。所以将数组的所有元素初始化为一个数表示关灯状态。而数组在声明时只能初始化所有元素为0。所以将数组a所有元素初始化为0表示所有灯初始状态是关闭的而灯打开的状态可以用数字1表示。将声明数组a的代码修改如下 如此一来数组a就初始化所有元素的值为0其中{0}中的数字0可以省略。 上面讲到第1个人关闭所有灯而数组a已经把所有元素初始化为0(关闭状态)。所以外层循环直接从第2个人开始修改循环嵌套代码如下变量i代表人的编号变量j代表灯的编号 接着在循环嵌套中开始为2~M个人对N盏灯进行处理。如果灯号j是i的倍数将对应灯号作相反处理即对数组a[j]的值进行相反的操作。如果a[j]等于1那么将a[j]赋值为0否则将a[j]赋值为1。代码如下 循环结束后使用一个循环遍历数组a的N个元素即看看N盏灯中有哪些是关闭的。如果a[i]等于0说明是关闭的输出该灯的编号即该元素的下标值代码如下 不过这是不对的因为相邻两个灯号之间要输出一个逗号。修改代码如下 还是不正确输出结果是【1,4,9,】最后多了一个逗号。输出时不管逗号写在变量i的前面还是后面输出结果都多了一个逗号。 其实可以这么思考最终输出结果的逗号比数字少一个而输出时数字和逗号是同时输出的所以逗号和数字的数目相等如果能确定第一或最后一盏关闭的灯的编号就很简单了。但最后一盏关闭的灯的编号是不能确定的而第一盏灯肯定是关闭的所以先输出第一盏灯的编号然后再循环输出剩余的逗号和灯号。代码如下 问为什么第一盏灯肯定是关闭呢 答所有灯初始时关闭的(第1个人全部关闭)从第2个人开始不可能存在是1的整数倍的正整数那么就无法对第一盏灯进行操作。 数据类型存储5000盏灯的一维数组可以在main函数中声明也可以声明为全局。N最大是5000而M不大于N说明M最大也是5000。所有数据选择int类型即可。 完整代码 思路分析(方法2适合基础和思维较好的同学) 在方法1的基础上进行优化。 方法1的循环嵌套代码框架 其实没有必要每个人都从第1盏灯开始遍历从第i盏灯开始即可。因为第i个人是从第i盏灯开始操作(i以内的数字都不是i的倍数)所以内层循环int j 1可以改为int j i。 同样第i个人只对i的倍数的灯进行操作所以内层循环的更新操作(j)可以改为j i。 修改后的代码 对第j盏灯是否为第i个人的倍数以及对灯进行相反的操作也可以进行优化。 方法1代码 因为现在的循环已修改每次循环都是i的倍数(即遍历的灯号都是人编号的倍数)所以语句【if (j % i 0)】可以删掉。 进行相反操作时因为a[j]的值要么为1要么为0只要把a[j]的值进行逻辑非运算即可。例如a[j]的值为1那么!a[j]的值为0。也可以写成【a[j]1-a[j]】如果a[j]等于1那么1-a[j]等于0如果a[j]等于0那么1-a[j]等于1。 代码如下二选一 完整代码 思路分析(方法3筛选法适合思维更好的同学) 完整代码 此方法与方法2的思路相似都是按倍数来遍历。 代码中变量j是倍数从1倍开始每次循环递增1。j是原来的灯号经过i倍筛选即可完成开关灯操作。 关于筛选法的基本思想可以参考下面文章在此不再赘述。 【信奥·数论】求区间质数(素数)的算法(进阶篇) 三种方法的运行时间 方法1 方法2 方法3 重难点 三种方法中方法2和方法3的运行时间看似相当实际上方法2是最快的而方法3的思路值得学习。 本题的难点是循环的嵌套框架即思路。以及最后输出的技巧。 如果能独自完成说明自己对循环嵌套和一维数组掌握得相当不错。 对于数组类型的选择可以选择bool类型空间开销较int类型的小。 参考代码下载链接 https://pan.baidu.com/s/123L9UFBoUaNnWAZwFiVv6A 提取码dsbc END 注题目来源于网络转载于《信息学奥赛一本通(C版)在线评测系统》点击下方的【阅读原文】即可打开该题的链接。 题解属于本微信公众号【大神编程】原创。
