什么是"学生和储物柜"问题的最佳解决方案？

我认为提出一些经典的CS问题并让人们展示他们的算法优化技巧会很有趣.希望我们能够看到一些巧妙的技术来解决我们可能在实践中实现的抽象问题.

理想情况下,解决方案将以具有大O分类的伪代码呈现.该分类的证明是肉汁.关于问题:

有N个封闭的储物柜和N个学生在场.第一个学生打开每个储物柜.第二个学生打开或关闭每个第二个储物柜.这继续在第n名学生打开和关闭每个第n个储物柜的地方.N学生之后什么储物柜开着？打开多少个储物柜？

学生只会翻转这些储物柜的状态,这些储物柜的数量是其除数(学生2翻转偶数储物柜,学生3翻转可被3整除的储物柜,依此类推......).因此,在N轮之后将保持打开的唯一储物柜是那些具有奇数除数的储物柜(因为它们开始关闭,奇数翻转将使其打开).唯一具有奇数除数的数字是完美的正方形,因此所有完美正方形编号的储物柜都将保持打开状态.因此,在N轮之后,打开的储物柜的数量将是N的平方根(平铺).

该解决方案将是O(sqrt(N))以确切地知道哪些储物柜是打开的,但是如果您只需要知道有多少储物柜是打开的,则为O(1).