首页 > 试题广场 > 关灯开灯问题
[问答题]
有编号1~100个灯泡,起初所有的灯都是灭的。有100个同学来按灯泡开关,如果灯是亮的,那么按过开关之后,灯会灭掉。如果灯是灭的,按过开关之后灯会亮。
现在开始按开关。
第1个同学,把所有的灯泡开关都按一次(按开关灯的编号: 1,2,3,......100)。
第2个同学,隔一个灯按一次(按开关灯的编号: 2,4,6,......,100)。
第3个同学,隔两个灯按一次(按开关灯的编号: 3,6,9,......,99)。
......
问题是,在第100个同学按过之后,有多少盏灯是亮着的?这些灯的编号是多少?要求给出解题思路或给出伪码。
推荐
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)
用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)
分析:
灯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)
在纸上画一画,你会发现,这是一个对称问题,左下角和右上角元素值是一样的,可以表示,一个代表开,一个代表关,刚好抵销,只有对角线上的元素消不掉,对角线上的元素即为1,4,9,。。。,100
发表于 2015-08-26 11:12:08 回复(0)
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)
  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)
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)
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)
//输出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)
<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)
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)
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)
解题思路:首先定义一个数组,全部初值设为关灯状态的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)
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)
char a[100]={1};
for(char i=1; i<100;i++)
{
    for(char j=i;j<100; j+=i+1)
    {
        a[j]=((~a[j])&0x01)
    }         
}


发表于 2014-12-20 23:24:13 回复(0)