我今天在一次求职面试中遇到了这个问题，我完全感到沮丧。这是问题的描述：
您在一个房间内有1到100盏照明灯，并且有100人。第i个人走进房间，打开所有编号为i倍数的灯。如果该灯已经打开，则他们将其关闭（即，它们将切换该灯）。100只是随机数-解决方案应达到某个任意值N（N ==灯光数量==人数）。
例如，人1将打开所有灯（因为每个数字都是1的倍数）。人2将切换所有2的倍数的光（2、4、6、8，依此类推）。这一直持续到第100位。
当时，我感到这可能与尝试确定最多N的素数有关，但是我不确定100％的正确性，所以我采用了一种蛮力方法（这大致就是我提供的方法）在PHP中）：
function lights_toggled($number_of_lights) {
$toggly = function($idx, $lights) {
foreach($lights as $i => $light) {
if($i % $idx == 0) {
if($lights[$i]) {
$lights[$i] = 0;
} else if(!$lights[$i]) {
$lights[$i] = 1;
}
}
}
return $lights;
};
$lights = array_fill(1,$number_of_lights,0);
for($i = 1; $i <= count($lights); $i++) {
$lights = $toggly($i, $lights);
}
return array_sum($lights);
}
我以为一切都很好，直到我回到家并开始查看该功能的输入和输出。我这样做是为了得到一些样本结果：
$results = array();
for($j = 1; $j <= 100; $j++) {
$number_of_lights_on = lights_toggled($j);
$results[$number_of_lights_on][] = $j;
}
print_r($results);
它很长，所以这是当＃个灯亮== 3或4时的输出片段：
...
[3] => Array
(
[0] => 9
[1] => 10
[2] => 11
[3] => 12
[4] => 13
[5] => 14
[6] => 15
)
[4] => Array
(
[0] => 16
[1] => 17
[2] => 18
[3] => 19
[4] => 20
[5] => 21
[6] => 22
[7] => 23
[8] => 24
)
...
当灯的数量在9到15之间时，答案是3灯亮。当灯的数量在16到24之间时，答案是4灯亮。基本上，似乎当x灯返回作为答案时，总灯数的下限是x ^ 2，而上限是x（x + 2）。
我开始在这里看到结构，但是我无法确定这个结果是否遵循了我不记得或不知道的算法。
这个问题在传统上被称为“更衣室问题”-在网络上对此有很多解释，例如：
http://mathforum.org/library/drmath/view/55812.html
其要点是，除数为偶数的那些将以其初始状态结束，而除数为奇数的那些将以相反的状态结束。尽管除数的确很好地影响了质数，但这实际上与质数无关。
特别是，其中有奇数个约数的数字都是....击鼓声......完美的正方形。由于除平方根以外的任何其他除数都将具有匹配且不相等的除数，但是理想平方具有一个额外的除数（平方根），该除数不与另一个除数配对。它与自身配对。
请注意，对于您所说的特定问题（有多少个未解决的问题），这意味着答案仅是floor(sqrt(N))针对N灯光，因为这是有多少个理想平方小于或等于N。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句