java - 有人可以解释一下下面的代码实际上是如何工作的吗

Question

有人可以向我解释一下以下代码的实际工作原理吗？

Problem: You have 64 doors in a row that are all initially closed. You make 64 passes by the doors. The first time through, you visit every door and toggle the door (if the door is closed, you open it; if it is open, you close it). The second time you only visit every 2nd door (door #2, #4, #6, ...). The third time, every 3rd door (door #3, #6, #9, ...), etc, until you only visit the 64th door.

我发现以下代码有效，但我想知道到底发生了什么。我不明白这个循环。

public class doors {
public static void main(String args[]) {
    // assume true=open, false=closed. Doors will all default to closed.
    boolean[] doors = new boolean[64];
    for (int i=0; i<64; i++) {
        for (int j=i; j<64; j=j+i+1) {
            doors[j] = !doors[j];
        }
    }
    // at the end, print out all the doors that are closed
    System.out.println("These doors are opened:");
    for (int i=0;i<64;i++){
        if (doors[i]) {
            // printing out i+1 to negate the zero-indexing
            System.out.println(i+1);
        }
    }
}
}

Answer 1

假设您知道 for 循环 的工作原理，让我们看一下以下示例:

首先假设所有门都关闭，关闭意味着false f，打开意味着true t 。为了更简单地理解，我们还假设门总数 = 4。

index       :     0       1       2       3
              +-----+ +-----+ +-----+ +-----+
begin       : |  f  | |  f  | |  f  | |  f  | // say all doors closed
              +-----+ +-----+ +-----+ +-----+
door number :    1       2       3       4

现在

 for (int i=0; i<4; i++) { // our example has 4 doors instead of 64
        // first iteration of outer loop, i = 0
        for (int j=i; j<4; j=j+i+1) {
            // as i = 0, j = 0 too
            // and j = j+i+1 = j + 0 + 1 = j +1 
            // so j will increment by 1
            // hence, j < 4 means the loop will rotate 4 (j = 0 to 3) times 
            doors[j] = !doors[j]; // this line do the trick, See bellow for details.
        }
    }

doors[j] = !doors[j]; 切换当前状态。如何？假设 doors[j] 包含 false 表示门已关闭，则 !doors[j] 更改值 false > 改为 true 表示关闭为打开!哒哒，这就是我们想要的!

   index(value of j) :    0       1       2       3
                       +-----+ +-----+ +-----+ +-----+
after 1st iteration  : |  t  | |  t  | |  t  | |  t  |
                       +-----+ +-----+ +-----+ +-----+
         door number :    1       2       3       4

所有四扇门都打开!

现在，对于外循环的第二次迭代，

 for (int i=0; i<4; i++) { // our example has 4 doors instead of 64
        // 2nd iteration of outer loop, i = 1
        for (int j=i; j<4; j=j+i+1) {
            // as i = 1, j = 1 too
            // and j = j+i+1 = j + 1 + 1 = j + 2 
            // so j will increment by 2
            // hence, j < 4 means the loop will rotate 2 (j = 1 and j = 3) times 
            doors[j] = !doors[j]; 
        }
    }

所以，

   index(value of j) :    0       1       2       3
                       +-----+ +-----+ +-----+ +-----+
after 2nd iteration  : |  t  | |  f  | |  t  | |  f  |
                       +-----+ +-----+ +-----+ +-----+
         door number :    1       2       3       4

只有2号和4号门是关着的!是的，我们走在正确的道路上!

现在你清楚地明白了，在外循环的第三次迭代中，j将从值2开始，并增加3，意味着仅门3将被切换!

   index(value of j) :    0       1       2       3
                       +-----+ +-----+ +-----+ +-----+
after 3rd iteration  : |  t  | |  f  | |  f  | |  f  |
                       +-----+ +-----+ +-----+ +-----+
         door number :    1       2       3       4

希望这将帮助您了解此代码如何解决 64 门的问题!

最后(第四次)迭代将制作所有门，如下所示:

   index(value of j)   :    0       1       2       3
                         +-----+ +-----+ +-----+ +-----+
after final iteration  : |  t  | |  f  | |  f  | |  t  |
                         +-----+ +-----+ +-----+ +-----+
         door number   :    1       2       3       4