1000 locker在不使用数组的情况下出现java问题

Question

我在不使用数组的情况下为一个关于1000 locker问题的课堂作业编写了一个程序，但我没有得到所需的输出。

这是储物柜的问题：

一所高中有1000名学生和1000个储物柜，每个学生一个储物柜。开学第一天，校长玩以下游戏：

她让第一个学生打开所有的储物柜。然后，她要求第二个学生关闭所有偶数的储物柜。第三个学生被要求每隔三个储物柜检查一次。如果它是打开的，则学生关闭它；如果它是关闭的，学生就会打开它。第四个学生被要求每隔四个储物柜检查一次。如果它是打开的，则学生关闭它；如果它是关闭的，学生打开它。剩下的学生继续这个游戏。

一般来说，第n个学生每隔第n个储物柜检查一次。如果它是打开的，则学生关闭它；如果它是关闭的，学生就会打开它。在所有学生轮流之后，一些储物柜是打开的，一些是关闭的。

它要求我提示用户输入储物柜的数量，并输出储物柜的数量和打开的储物柜编号。在研究它的过程中，我相信如果我是正确的，输出应该是一个完美平方数的列表。

这是我迄今为止编写的代码。

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int studentVisitCount = 0;
System.out.print("Enter the number of lockers: ");
int numberOfLockers = keyboard.nextInt();
for (int x = 1; x <= numberOfLockers; x++) {
for (int y = 1; y <= x; y++) {
if (x % y == 0) {
studentVisitCount++;
}
}
}
System.out.println("The number of lockers and students are: " + numberOfLockers);
if (studentVisitCount % 2 == 0) {
System.out.print(studentVisitCount + " ");
System.out.println("The locker numbers of lockers that are left open at the end of the game are: ");
}
}
}

Answer 1

你是对的，打开的门将是完美的方形门编号，因为完美的方形编号i将被访问3次(通过1，sqrt(i(，i，除了1将被访问一次(，将门状态更改为Closed->打开->关闭->打开完美正方形的数量<=numberOfLockers是1…平方根(numberOfLocker(中每个i的i*i，所以你可以使用/不使用数组来做这样的事情：

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
System.out.print("Enter the number of lockers: ");
int numberOfLockers = keyboard.nextInt();
// With array
boolean[] isDoorOpen = new boolean[numberOfLockers + 1];
for (int i = 1; i <= numberOfLockers; i++) {
for (int j = i; j <= numberOfLockers; j += i) {
isDoorOpen[j] = !isDoorOpen[j];
}
}
for (int i = 1; i <= numberOfLockers; i++) {
if (isDoorOpen[i])
System.out.println(i);
}
// Without array
System.out.printf("The number of lockers and students are: %s%n", numberOfLockers);
System.out.println("The locker numbers of lockers that are left open at the end of the game are: ");
for(int i=1; i<=Math.sqrt(numberOfLockers); i++) {
System.out.println(i*i);
}
}

Answer 2

如果我们看到这种模式，我们就会意识到，在特定锁定器中发生的打开/关闭操作的总数等于其除数的总数。因此，如果一个数有奇数个除数，那么它的最终状态将是开的，否则它将是闭的。

现在，为了找到特定数的除数，我们可以将数表示为n = p^q，那么总除数将为(q + 1)，除数为1, p, p^2, ...., p^q[类似地，如果n = p^q * r^s，我们可以找到除数为(q + 1) * (s + 1)]。因此，为了使(q + 1)是奇数，q必须是偶数。因此，如果一个数可以表示为完全平方(如p^2(，那么它将具有奇数个除数。

现在，如果我们只想在n储物柜中找到最终打开的储物柜的数量，我们可以通过简单地计算n的平方根的整数表示来在O(logn)时间复杂度中找到它。

int numberOfLockersThatWillBeOpen = (int) Math.sqrt(n);

但是，为了打印所有打开的储物柜编号，并找到将要打开的储物柜的编号，我们可以迭代从1到n的所有数字，检查它们的平方是否小于或等于n，并在我们注意到平方大于n时立即中断循环。

int numberOfLockersThatWillBeOpen = 0;
List<Integer> ans = new ArrayList<Integer>();
for (int x = 1; x <= numberOfLockers; x++) {
if ((x * x) <= numberOfLockers) {
numberOfLockersThatWillBeOpen++;
ans.add(x);// put x into list to print it later 
} else {
break;
}
}

由于我们正在迭代到n的平方根，所以上述解的时间复杂度将是O(sqrt(n))。