百人开灯问题解法及优化
一：题意
房间里有100盏电灯，编号为1，2，3……100，每盏灯上有一个按钮，初始时灯全都是关的。编好号的100位同学由房间外依次走进去，将自己编号的倍数的灯的按钮全部按一次
- 第一位同学把编号是1的倍数的灯的按钮按一下（此时100盏灯全亮）
- 第二位同学把编号是2的倍数的灯的按钮按一下（此时只有50盏灯亮着，50盏被这个人按灭了
- ……
- 第100位同学把编号是100的倍数的灯（即编号为100的灯）的按钮按一下
请问依次走完后，还有多少盏灯亮着？
二：实现
1：暴力法
- 双循环暴力破解
- 时间复杂度：O(n*n)
- 空间复杂度：O(1)
- 代码实现：
/**
* 暴力法
* 时间复杂度：O(n*n)
*/
public class Test {
public static void main(String[] args) {
int[] light = new int[101];
//初始化为灯关闭
for (int i = 1; i < light.length; i++) {
light[i] = 0;
}
//关灯操作
for (int i = 1; i < light.length; i++) {
for (int j = 1; j < light.length; j++) {
if(j%i == 0) {
light[j] = light[j] == 0 ? 1 : 0;
}
}
}
//输出打开的灯
for (int i = 1; i < light.length; i++) {
if(light[i] == 1)
System.out.println(i);
}
/**
* 输出
* 1
* 4
* 9
* 16
* 25
* 36
* 49
* 64
* 81
* 100
*/
}
}2：优化一：
- 观察发现每一盏灯都只会被比自身小并且是自身约数的值和自身 进行开启或者关闭操作
- 我们将自身数对灯的开启关闭排除，则比这盏灯小并且是这盏灯约数的值为偶数，则最后为开灯，否则最后为熄灯
- 时间复杂度会比单纯的暴力法降低一些
- 代码如下：
/**
* 优化暴力法
* 时间复杂度：O(n*n)，但会比单纯的暴力法时间复杂度低
*/
public class Test {
public static void main(String[] args) {
int[] light = new int[101];
//初始化为灯关闭
for (int i = 1; i < light.length; i++) {
light[i] = 0;
}
//关灯操作
for (int i = 1; i < light.length; i++) {
for (int j = 1; j < i; j++) {
if(i%j == 0) {
light[i]++;
}
}
}
//输出打开的灯
for (int i = 1; i < light.length; i++) {
if(light[i]%2 == 0)
System.out.println(i);
}
/**
* 输出
* 1
* 4
* 9
* 16
* 25
* 36
* 49
* 64
* 81
* 100
*/
}
}3：优化二：
- 观察发现，每盏灯都会被“1”操作一次，也会被自身的值操作一次，这两次相互抵消
- 对于灯i，如果存在一个i的约数j，那么一定存在另外一个约数k，如果j != k ，那么这两次相互抵消，如果j == k，那么只有一个这样的值，不会被抵消，这样只有存在完全约数（比如:4 = 2*2 , 9 = 3*3类的）的灯才不会被抵消，所以我们要求的就是具有完全约数的值。
- 所以我们只要判断值的开方是不是整数就可以了
- 时间复杂度：O(n)
- 没有通用性，代码如下:
/**
* 具体问题具体分析，没有通用性
* 时间复杂度：O(n)
*/
public class Test {
public static void main(String[] args) {
int[] light = new int[101];
//初始化为灯关闭
for (int i = 1; i < light.length; i++) {
light[i] = 0;
}
//关灯操作并输出
for (int i = 1; i < light.length; i++) {
double k = Math.sqrt(i);
int m = (int)k;
if((double)m == k) {
System.out.println(i);
}
}
/**
* 输出
* 1
* 4
* 9
* 16
* 25
* 36
* 49
* 64
* 81
* 100
*/
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018年10月07日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
