一道有趣的题

发表于   |  

一道有趣的算法题。

看《算法设计与分析基础》第三版的时候，1.1节习题中又这么一道题：

带锁的门：在走廊上有n个带锁的门，从1到n一次编号。最初所有的门都是关着的。我们从门前经过n次，每次都从1号门开始。在第i次经过时(i=1，2，3，…，n)我们改变i的整数倍号锁的状态：如果门是关着的，就打开它；如果门是打开的，就关上它。在最后一次经过，哪些门是打开的，哪些门是关上的？有多少打开的门？

一开始没什么头绪，不过我们可以写个例子看看，比如取n等于10。

n/门号 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1
2 1 0 1 0 1 0 1 0 1 0
3 1 0 0 0 1 1 1 0 0 0
4 1 0 0 1 1 1 1 1 0 0
5 1 0 0 1 0 1 1 1 0 1
6 1 0 0 1 0 0 1 1 0 1
7 1 0 0 1 0 0 0 1 0 1
8 1 0 0 1 0 0 0 0 0 1
9 1 0 0 1 0 0 0 0 1 1
10 1 0 0 1 0 0 0 0 1 0

n为0表示初始状态，0表示关闭，1表示打开。

在写这个例子的时候，我们会发现门号如果能被k(第k次经过)整除，该门的状态就会发生变化，当k>$\sqrt{k}$时，只会改变第k个门的状态。

我接着就能发现状态改变偶数次后，状态不变，也就是说，对于第k个门，如果k有偶数个约数，那么这扇门的状态最后还是和初始状态一样，这样我们的问题就是找出哪些数有偶数个约数。

我们观察上面的例子，发现1,4和9的最后状态是与初始状态不一样外，其他门的状态都一样。到这里，我们可能很容易就猜想到1，4，9等这些是某个数的平方的数有奇数个约数，当然，我们可以取n的值16，25再看看。能想到这里，其实为什么这些数有奇数个约数也很容易想到。

如果k是n的一个约数，那么n除以k等于$\frac nk$余0，那么$\frac nk$也是n的一个约数，这样，n的约数一般都是成对出现，只有一种情况就是k等于$\frac nk$的时候，即这两个约数相等，那么这时只算一个约数。而只有像1，4，9这些数会出现这种情况，1比较特别。

这样也就回答了上面的那个问题。

下面是代码演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main(String[] args) {
	printState(10);
}

private static void printState(int n) {
	for (int i = 1; i <=n; i++) {
		if (isSquared(i)) {
			System.out.println("Door " + i  + " is opened");
		} else {
			System.out.println("Door " + i  + " is closed");
		}
	}
}
private static boolean isSquared(int n) {
	int i = 1;
	while (i * i < n) i++;
	return i * i == n;
}