首页 > 试题广场 >

关灯开灯问题

[问答题]
有编号1~100个灯泡，起初所有的灯都是灭的。有100个同学来按灯泡开关，如果灯是亮的，那么按过开关之后，灯会灭掉。如果灯是灭的，按过开关之后灯会亮。
现在开始按开关。
第1个同学，把所有的灯泡开关都按一次(按开关灯的编号： 1,2,3,......100)。
第2个同学，隔一个灯按一次(按开关灯的编号： 2,4,6,......,100)。
第3个同学，隔两个灯按一次(按开关灯的编号： 3,6,9,......,99)。
......
问题是，在第100个同学按过之后，有多少盏灯是亮着的？这些灯的编号是多少？要求给出解题思路或给出伪码。
添加回答
推荐
surfacedust头像 surfacedust
10盏，1，4，9，16，25，36，49，64，81，100
按照同学来看，每个同学只会按是自己的倍数的灯。
那么我们转换成灯来看的话，每个灯只会被是自己的因子的同学按。
那么一个初始化为灭的灯，如何最后变成一盏亮的灯呢？
很明显，只有它有奇数个因子的时候，才有可能。
那么什么时候一个数可以有奇数个因子呢？
对于任意一个数N ，都可以分解成 N = a * b的乘积，即任意一个数都可以分解成 M个(a * b) 的乘积。
所以若想满足存在奇数个因子，a 必须等于 b.
即 N = a2,所以只有平方数最后才满足要求，故可以在0(n)的时间复杂度解决该问题。 
编辑于 2015-01-19 20:44:02 回复(4)
NOWCODER我最帅头像 NOWCODER我最帅
用0 代表 灯灭 1 代表灯亮
用一个array[100][100]储存每个人按的状态 index 由1---100 初始值为0
array[i][j]代表第i个人按了第j盏灯。

for（i=1；i＜＝100;i++)
for（j＝1；j<=100；j++）
if(j%i==0）{
arrray[i][j]=1;
}
赋值
j相同的列相加
和是偶数
则亮 否则不亮




发表于 2014-12-19 15:33:16 回复(3)
lenovo头像 lenovo
分析：
灯1 只会被第1个同学按，属亮。
灯2 只会被第1个同学和第2个同学按，属灭。
灯3 只会被第1个同学和第3个同学按，属灭。
灯4 只会被第1个同学、第2个同学以及第4个同学按，属灭。
。。。。
由此分析：
灯N，只会被第1个同学、。。。。以及第N个同学按，亮灭情况由其间被按几次确定。

由上分析可知：这实际上是一道求解一个数字的因式分解题目，只要确定随意给定一个数，确定因式分解可得到几个不同的因子即可解题。

1只有1本身这个因子
2只有1和2这两个因子
3只有1和3这两个因子
4有1、2、4三个因子
5有1和5两个因子
6有1，2，3，6四个因子
。。。

因灯首先是灭的，所以当某个数的因子个数为奇数时则该灯亮。

public Set<Integer> yinshifenjie(int num){
    Set<Integer> result = new HashSet<Integer>();
    for(int i=2;i*i<=num;i++){ 
       if(num%i==0){     
          result.add(i); 
          num = num/i;   
       }else{    
          i++;    
       }   
    }
}

则只需要从1到100依次调用这个函数，则由得到Set<Integer>结果算中结果集长度，为奇数的为亮灯情况。

public Set<Integer> lighting(){
   Set<Integer> result = new HashSet<Integer>();
    
   for(int i=1;i<=100;++i){ 
       if(yinshifenjie(i).size() % 2 != 0){
          result.add(i);
       }
   }

   System.out.println("一共有"+result.size()+"盏灯是亮着的，它们是："+result);

}

发表于 2014-12-24 22:38:58 回复(2)
俊雪恋头像 俊雪恋 
这个题目简直就是为数组量身定制的，假设a[i] = 1代表开着，a[i] = 0;代表关着，对数组进行非的操作，a[i] = !a[i]这样就把关着的开了，开着的关了，妙。
#include <stdio.h>
#include <string.h>
#define N 1005

int main()
{
int a[N], n, k;
scanf("%d %d", &n, &k);
memset(a,0,sizeof(a));
for(int i = 1; i <= k; i++)
{
for(int j = 1; j <= n; j++)
{
if(j % i == 0)
a[j] = !a[j];
}
}
for(int i = 1; i <= n; i++)
if(a[i])
printf("%d ", i);
return 0;
}
编辑于 2017-03-28 10:56:10 回复(0)
StrongYoung头像 StrongYoung
在纸上画一画，你会发现，这是一个对称问题，左下角和右上角元素值是一样的，可以表示，一个代表开，一个代表关，刚好抵销，只有对角线上的元素消不掉，对角线上的元素即为1，4，9，。。。，100
发表于 2015-08-26 11:12:08 回复(0)
hitzlm头像 hitzlm 
int flag[101] = {0};
for(int i=1;i<=100;i++){
     int startIndex = i;
     int step = i;
     while(startIndex<=100){
         flag[startIndex] += 1;
         startIndex += step;
     }
 }
 int count = 0;
 for(i=1;i<=100;i++){
     if(flag[i]%2==1){
         count++;
         cout<<i<<"  "<<endl;
     }
 }
 cout<<count<<endl;

编辑于 2015-03-27 22:37:03 回复(0)
可是我头像 可是我
#include<stdio.h>



#include<string.h>
#define maxn 1010
int a[maxn]= {0};
int main(void)
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=k; i++)    //判断
        for(int j=1; j*i<=n; j++)
                a[j*i]=!a[j*i];
    for(int i=1; i<=n; i++)  //输出
        if(a[i])
            printf("%d ",i);
    return 0;
}
//输入 100 100
//输出  1 4 9 16 25 36 49 64 81 100
发表于 2021-02-22 20:26:27 回复(0)
落寒渐殇头像 落寒渐殇 
    
	
	
  1. 
		import numpy as np
x=np.zeros(100)
for i in range(1,101):
    q=[]
    for j in range(1,101):
        if i%j==0:
            q.append(j)
    x[i-1]=len(q)%2   
for i in range(0,100):
    if x[i]==1.0:
        print(i+1)

发表于 2018-09-16 11:14:55 回复(0)
Carrod头像 Carrod
1:1
2:2
...
可看出规律：需要知道1~100的各个位置的公约数个数+1，例如8按过的有1,2,4，求完公约数后异或，不为0的就是亮的。
不过求公约数略麻烦，何不初始化100个数组进行异或运算，并得到一个数组，非0就是亮着的，用bit的减少内存利用应该也是可以的。例如：
第一个：1111111111111111
第二个：0111111111111111
第三个：0011111111111111
三组异或后
             1011111111111111
发表于 2017-02-26 00:58:37 回复(0)
DELIN头像 DELIN 
map = {1:0,2:0...100:0}
for(int i=1:i<=100:i++){
    for(int j=i:j<=100:j=j+i){
        map.put(j , map.get(j) == 1 ? 0 : 1);
    }
}
map里相同键会被覆盖，所以不用考虑太多...
发表于 2016-05-23 20:06:29 回复(0)
winterliu头像 winterliu
//输出1 4 9 16 25 36 49 64 81 100
#include <iostream>
int main(){
for(int i = 1;i <= 100;i++){
int count = 0;
for(int j = i;j >= 1; j--){
if(i % j == 0){
count++;
}
}
if(count % 2 != 0){
std::cout<<i<<"\t";
}
}
return 0;
}
发表于 2015-09-23 13:44:15 回复(0)
pmby头像 pmby
<div> 1.可以看到，每名同学按的灯，都是自己编号的整数倍， 为所有同学迭代这么多次，求出每个灯的结果 </div> <div> 2.每个灯的位置，它在1~100以内的倍数，是奇数个还是偶数个（100/n）？这就确定了灯亮还是灭。可以从这点考虑，统计出结果。一次遍历即可，复杂度O(n) </div>
发表于 2015-09-15 10:27:26 回复(0)
指上弹兵赵小括头像 指上弹兵赵小括
<div> 1^2 = 1 </div> <div> 2^2 = 4 </div> <div> 3^2 = 9 </div> <div> …… </div> <div> …… </div> <div> 10^2 = 100 </div> <div> <br /> </div>
发表于 2015-09-08 21:58:36 回复(0)
咸蛋头像 咸蛋 
/****以下代码是按我的解题思路写的，因为条件限制没有实际去调试过，也不知
道算法对不对，希望有兴趣的大神帮我检查一下这个算法对不对！在此谢过！！！****/




/*
创建一个int数组，大小为101（为了数组角标与每个灯编号对应，所以
不用0角标），用于记录每个灯被点击的次数。
*/

int []count=new int[101];

/*
第一个循环控制第i个人去按开关，第二个循环控制每个人所按开关的编号
*/

for(i=1;i<=100;i++)
    {
    for(j=i;j<=100;j+=i)
        {
        count[j]=count[j]+1; //在对应的计数器上加1
    }
}

/*
最后遍历数组，对每个值%2，若结果为1，则说明该编号的开关被点击了奇
数次，最后灯的状态是亮着的
*/

for(i=1;i<=100;i++){
    if(count[i]%2==1){
        System.out.println(“第”+i+“个灯亮”);
    }
}

编辑于 2015-06-11 08:56:58 回复(0)
牛客924667号头像 牛客924667号
for (int i = 1; i <101; i++) {
            int cs = 0;
            for (int j = 1; j <= i; j++) {
                int ys = i%j;
                if(ys==0){
                    cs+=1;
                }
            }
            if(cs%2==0)
                System.out.println("当前灯为"+i+"号灯,此灯关闭");
            if(cs%2==1)
                System.out.println("当前灯为"+i+"号灯,此灯打开");
        }
发表于 2015-05-03 20:47:15 回复(0)
keepcoding头像 keepcoding 
public class Light {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 int[] lights = new int[100];
 int count = 0;

 // 方法二：直接判断灯的编号是平方数,时间复杂度O(N)
 for (int i = 1; i <= 100; i++) {
 if (Math.sqrt(i) == (int) (Math.sqrt(i))) {
 lights[i - 1] = 1;
 }
 }
 for (int i = 0; i < 100; i++) {
 if (lights[i] == 1) {
 count++;
 System.out.print((i + 1) + ",");
 }
 }
 System.out.println("有多少盏灯是亮着的：" + count);
 }
}

发表于 2015-04-18 21:03:57 回复(0)
只是说说而已头像 只是说说而已
for (int i = 1; i <= 100; i++) {
for (int j = 1; j * i <= 100; j++) {
list[i * j - 1] = list[i * j - 1]+=1;
}
}
StringBuffer str = new StringBuffer();
for (int i = 0; i < list.length; i++) {
str.append(i+1 + " = " + list[i] + ";\n");//list[i]为每个数出现的个数，奇数灯亮，偶数灯灭
}
Log.d("tag", str.toString());
编辑于 2015-01-15 14:58:07 回复(0)
linko解万头像 linko解万
解题思路：首先定义一个数组，全部初值设为关灯状态的0,。然后开始循环部分。
    从1到100循环，循环部分主要是找出到底是第几个同学关的灯，然后设置对应的开关灯顺序。我们可以在循环的同时加入判定语句，假如是第1、4、7（如此类推）名同学，则执行第一种开关灯方式：循环数组中1到100的元素，然后判定：是否已开灯了，已开灯的-1，关灯的+1。
    然后回到最初的循环，加入第二个判定语句：假如是第2、5、8（如此类推）名同学，则执行第二种开关灯方式：循环数组中所有元素，从1开始，每次自加2，就可以对所有编号为双数的灯进行操作，因为数组从0开始，编号2的灯就是数组中的1。然后再加一个判定：开灯了的-1，关灯了的+1。
    现在再次回到最初的循环，加入最后一个判定，判定是否是第3、6、9（如此类推）名同学，也可以用else，因为除去前面的那些同学，最后就剩下这些3的倍数的同学了。这里先说一下，三种大判定顺序不一定要从1到3按顺序，只要在程序运行时触发其中一个大判定，判定出到底是哪个同学应该用那种方式开关灯就可以了。那么，当我们现在找到这个同学，就开始循环数组中的元素，在for循环的时候从2开始，小于100，自加3，这样就可以对所有编号是3的倍数的灯进行操作（编号从1开始，而数组从0开始，所以是2开始），然后判定是否已开灯，开了的-1，关了的+1。
    这100个同学统统操作完以后，我们可以直接用一个循环来输出，这时候可以另外定义一个变量sum（初值为0）来存储计算亮着的灯的数量。循环找出所有数组中的元素（灯），再判定这些灯是0还是1。如果是1，则sum自加1，然后直接输出灯的编号：当前循环数字+1的和（因为灯的编号总比数组对应的数字多1）。为0则跳过。最后可输出sum，sum是最终亮着的灯的总数
发表于 2015-01-05 15:23:31 回复(0)
lazywg头像 lazywg
int [] light=new int[100];//0关 1开
for(int i = 1,i<=100,i++)
{
for(int j=1,j<=100,j++)
{
if(j%i==0)
{
if(light[j-1]==0)
{
light[j-1] = 1;
}
else
{
light[j-1] =0;
}
}
}
}
发表于 2014-12-25 19:46:23 回复(0)
大脸头像 大脸
发表于 2014-12-21 14:48:00 回复(0)
远方方头像 远方方
计算每个数字出现的次数
发表于 2014-12-21 07:30:19 回复(0)
提交观点

问题信息

智力题 2015 百度 大数据开发工程师
来自：百度2015大数据云计...
上传者：小小
难度：
23条回答 25131浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号