l***i
发帖数: 165 | 1 就是说有100个灯泡，排一排。第一个人打开第一个，然后第二个人打开2,4,6....
所有2n个，第3个人打开3，关闭6。。。。就是改变3n的状态。第4个人类推，问
第100个人以后那些是亮的。
有什么算法没有？还好像除了归纳也没什么办法了？ | w*******e
发帖数: 14 | 2
hehe, sounds like 数学竞赛题目~~
亮着的灯必然有奇数个约数，所以是完全平方数和1
【在 l***i 的大作中提到】
: 就是说有100个灯泡，排一排。第一个人打开第一个，然后第二个人打开2,4,6....
: 所有2n个，第3个人打开3，关闭6。。。。就是改变3n的状态。第4个人类推，问
: 第100个人以后那些是亮的。
: 有什么算法没有？还好像除了归纳也没什么办法了？
| x******g
发帖数: 318 | 3 所有的平方数
考察每个数的因子个数即可,奇数个因子将是亮着的
这显然与为平方数等价
这是一道很老的微软面试题
【在 l***i 的大作中提到】
: 就是说有100个灯泡，排一排。第一个人打开第一个，然后第二个人打开2,4,6....
: 所有2n个，第3个人打开3，关闭6。。。。就是改变3n的状态。第4个人类推，问
: 第100个人以后那些是亮的。
: 有什么算法没有？还好像除了归纳也没什么办法了？
|
|
