原题如下:

有 n 盏灯,编号 1~n(0<n<100)。第 1 个人把所有灯打开,第 2 个人按下所有编号为 2 的倍数的开关(这些灯将被关掉),第 3 个人按下所有编号为 3 的倍数的开关(其中关掉的灯将被打开,开着的灯将被关闭),依次类推。输入灯数和人数,输出开着的灯的编号。
比如输入:10 2 输出最后亮灯的编号:1,3,5,7,9
注意:使用循环语句实现。

java和c都可以实现,下面代码将使用java来实现

首先这题有两种解题思路:

  1. 可以通过定义一个boolean数组判断灯是否打开,然后模拟整个开关的流程
  2. 可以先算出一个灯被开关的次数,根据开关的次数推断出这个灯现在的开关状态

第一种:

首先我们要先输入两个需要变量,这个两种方法是一样的:

Scanner sc = new Scanner(System.in);
System.out.println("输入灯数:(0<n<100):");
int lampNum = sc.nextInt();
System.out.println("输入人的数量:");
int manNum = sc.nextInt();

然后定义一个boolean数组然后初始化:

boolean[] lamp_flag = new boolean[lampNum];	//使用boolean数组来判断灯的开关
for(int i=0;i<lamp_flag.length;++i) {
	lamp_flag[i] = true;
}

接下来就是模拟整个关灯开灯的流程:

for(int i=1;i<=manNum;++i) {
	if(i==1) {
		continue; //因为之前初始化就把所有灯打开了,所以第一个跳过就可以了
	}
	for(int j=1;j<=lampNum;++j) {
		if(j%i==0) {
			if(lamp_flag[j-1]==true) {			
				lamp_flag[j-1]=false;			
			}else {  //如果灯是关的就打开,如果是开的就关闭
				lamp_flag[j-1]=true;
			}
		}
	}			
}

最后输出:

for(int i=0;i<lamp_flag.length;++i) {
	if(lamp_flag[i] == true) {
		System.out.print((i+1)+" ");
	}			
}

第二种:

相比第一种方法模拟整个流程第二种方法就要简单很多:

for(int i=1;i<=lampNum;i++) {
	int count=0;//count用来统计一个灯开关的次数
	for(int j=1;j<=manNum;j++){
		if(i%j==0){//灯是人数的倍数即灯被按下一次
		   count++;
                }
	}
	if(count%2==1){//灯原始状态为熄灭,因此灯泡被按下单数次即灯泡是打开的
		System.out.printf("%d ",i);
        }
}

最后本人才疏学浅,如果发现有错误或者有不同的,更优的算法,请在评论指出万分感谢


本文作者为 MoWang ,转载请注明


爱编程更爱生活