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

Question

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

理想情况下，解决方案应该用带有大O分类的伪代码表示。这种分类的证据是肉汁。关于这个问题：

有N个封闭式储物柜和N个学生在场。第一个学生打开每个储物柜。第二个学生每隔一次打开或关闭一个储物柜。这在第n个学生打开和关闭每个第n个储物柜的情况下继续。在N个学生之后，哪个储物柜是打开的？有几个储物柜是开着的？

Answer 1

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

这个解决方案将是O(sqrt(N))来确切地知道哪些锁是打开的，但是如果您只需要知道有多少个锁是打开的，则O(1)。

Answer 2

这是我的答案，不使用数组(或对象等)，也不使用平方根方法。

====

包括

使用命名空间std；

int main() {

int studentTotal，lockerTotal，，totalOpened = 0，totalClosed = 0；

cout << "Enter number of students“<< endl；cin >> studentTotal；

lockerTotal = studentTotal；

for (int locker = 1; locker <= lockerTotal;  locker++ ){ // locker loop
    cout << "\n\n\nLocker no." << locker << endl;
    cout << " is visited by student(s) ";
    visit = 0;
    for (int student = 1 ; student <= studentTotal; student++) { // student loop

    if( locker % student == 0) {
            cout << student << ", ";
            visit++;}

    }//end of locker loop

    cout << "\nTotal number of visits: " << visit;
    if (visit % 2 == 0){
        cout << " the locker will stay closed.";
        totalClosed++;}
    else { cout << " the locker will be opened.";
        totalOpened++;}

} //end of student loop

if (lockerTotal == totalOpened + totalClosed) {
    cout << "\n\n\nOf total lockers (" << lockerTotal << "), " << totalOpened << " will be left open." << "(" << totalClosed << ") " << "will be closed." << endl;
    }else cout << "Error!!";



return 0;

}

Answer 3

在O(log )中，基于系列1+2k之后的打开储物柜的间隔：

delta=1

for(index=1;index < N;index+=delta) {
   print open locker = index;
   delta+=2;
   opencount++;
};