N盏灯问题

N盏灯问题是个很有意思的问题,是一个数学题,也是一个编程题。

这个问题,有很多不同的叫法
0、N个人开关N盏灯问题
1、开关灯问题

一、问题描述:
有N盏灯放在一排,从1到N依次顺序编号。有N个人,也从1到N顺序编号。1号将灯全部关闭,2号将凡是2的倍数的灯全部打开;3号将3的倍数的灯全部作相反操作(该灯如为打开,则将它关闭;如关闭,则将灯打开)。以后的人,都和3号操作一样,将凡是自己序号倍数的灯作相反操作。第N个人操作完之后,一共有几盏灯亮着?

二、问题分析
灯编号: 1->N
人编号: 1->N
开始灯都关着
灯 % 人 == 0 按一次开关
第N个人操作后,亮个的灯的个数

三、解题思路
0、解法一、暴力求解
2次遍历,时间复杂度:n平方

1、解法二、数学知识
算法:
0、第M盏灯是否亮着,取决于有多少个人按过开关,如果是奇数个人按过就是亮个,否则就不亮。
1、是M的约数的人都是按一次灯,问题转换为判断M是否有奇数个约数。
2、平方数的性质正好满足有奇数个约数,问题转换判断M是否是平方数。
3、最终亮灯数,就是小于等于N有多少个平方数。【小于等于N的平方数个数正好等于不大于N的平方数的平方根,推理得出,需要证明】
小于5的平方数个数2: 1,2
小于10的平方数个数3:1 4 9
4、求解

$num = (int)sqrt($n);

总结:
0、平方数,也就完全平方数
1、约数也叫因数

参考:
维基百科:约数
维基百科:平方数
N个人开关N盏灯的问题思考
牛客网N盏灯问题

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注