房间里有100盏电灯编号为1，23……100，每屋里7盏灯灭掉一盏还有多少上有一个按钮初始时灯全都是关的。编好号的100位同学由房间外依次走进去将自己编号的倍数的灯的按钮全部按一次，例如第一位同学把编号是1的倍数的灯的按钮按一下（此时100屋里7盏灯灭掉一盏还有多少全亮）第二位同学把编号是2的倍數的灯的按钮按一下（此时只有50屋里7盏灯灭掉一盏还有多少亮着，50盏被这个人按灭了）……第100位同学把编号是100的倍数的灯（即编号为100的灯）的按钮按一下请问依次走完后，还有多少屋里7盏灯灭掉一盏还有多少亮着
方法一.通过模拟同学进出场开关灯实现
*100屋里7盏灯灭掉一盏還有多少开关的问题通过模拟同学进出实现 /*模拟100屋里7盏灯灭掉一盏还有多少，1表示开0表示关*/ /*最后灯开着的数量*/ /*将灯初始化为全关*/ /*模拟同學进场进行开关灯*/ /*输出开灯的数目*/ }方法二.通过以上进出场开关流程分析，我们可以通过对灯编号进行约数计数来降低复杂度约数个数为渏数的灯最后是开着的，约数为偶数的灯是关着的 *100屋里7盏灯灭掉一盏还有多少开关的问题通过计算约数个数实现 /*将数组初始化为0*/ /*输出开燈的数目*/
方法三.进一步分析，约数是成对出现的因此只有完全平方数约数个数为奇数，其他数的约数个数都为偶数因此本题实际上可鉯转换为求100内完全平方数的个数。当然答案为10我们在上面两个代码中将开灯编号打出来，结果如下：
结果验证了求100内完全平方数的个数
该题，我是永循序渐进的的思想去解决的可能一开始不能想到将问题转换为求100以内完全平方数的个数，但是通过模拟实现再一步步抽象分析优化得到了最简单的模型，当然中间过程并不一定要去代码实现我这里只是为了做比较。因此给我的启发是遇到问题要分步分析去优化
问题延伸：如果是n屋里7盏灯灭掉一盏还有多少，k个人呢
这里给出复杂度为O(k*n)的约数个数算法这里的约数个数是指ni在1-k之间的约数個数，方法一复杂度也为O(k*n)还没想到怎么优化，读者如果有想法希望给点指点。
/*将数组初始化为0*/ /*统计开灯数,打印开的灯的编号*/发布了52 篇原创文章 · 获赞 1 · 访问量 5万+
