乐者为王

Do one thing, and do it well.

逻辑题-100盏电灯

房间里有100盏电灯,编号为1,2,3...100,每盏灯上有一个按钮,初始时灯全都是关的。

编好号的100位同学由房间外依次走进去,将自己编号的倍数的灯的按钮全部按一次,例如第一位同学把编号是1的倍数的灯的按钮按一下(此时100盏灯全亮),第二位同学把编号是2的倍数的灯的按钮按一下(此时只有50盏灯亮着,50盏被这个人按灭了)...第100位同学把编号是100的倍数的灯(即编号为100的灯)的按钮按一下,请问依次走完后,还有多少盏灯亮着?

解题思路:

被按过奇数次的灯亮着,偶数次的灯关了。因为每个同学会把自己编号的倍数的灯全部按一次,所以:

1
2
3
4
5
6
7
8
9
1号灯会被1号同学按下;
2号灯会被1,2号同学按下;
3号灯会被1,3号同学按下;
4号灯会被1,2,4号同学按下;
5号灯会被1,5号同学按下;
6号灯会被1,2,3,6号同学按下;
7号灯会被1,7号同学按下;
...
依此类推

从上面可以总结出n号灯会被以它所有约数为编号的同学按下。

这样,问题就变成了求每盏灯的编号有多少个约数的数学问题。如果约数个数为奇数,灯亮着;反之,灯关着。

Ruby代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
# Light state: ON/OFF = true/false
lamps = Array.new(100, false)

1.upto(lamps.length) do |lno|
  1.upto(lno) do |fno|
    lamps[lno - 1] = !lamps[lno - 1] if lno % fno == 0
  end
end

lamps.each_index do |i|
  print "Light #{i + 1} is "
  puts lamps[i] ? "ON" : "OFF"
end

最后,我们会发现编号1,4,9,16,25...100的灯是亮着的,其它都是灭的。即编号值可以开出整数平方根的灯是亮的。

Comments