第一个博弈程序
甲乙两人在玩一个游戏：一堆小石子，共n个，每次每人可以从中取1个，或2个，或4个，甲先开始，最后取的那个人输（不管他去1个，还是2个，还是4个）。
但是呢，甲乙两个人都是智力超群的天才，他们总会使用对自己有利的策略。
问题：我们能否从一开始就知道谁必然赢？
可以这样考虑：如果只剩下1,2,3,4个石子时，轮到 x 取，我们可以推断出那个必然的赢家。
| 1 | x 输 |
| 2 | x 赢（x 取 1 个） |
| 3 | x 赢（x 取 2 个） |
| 4 | x 输（不管取 1,2,4 个都输） |
我们给甲乙编号，甲为 0，乙为 1，可以得到如下递归程序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int winner(int n, int x) { assert(n >= 1); switch (n) { case 1: return 1-x; // 对方赢 case 2: return x; // 己方赢 case 3: return x; // 己方赢 case 4: return 1-x; // 对方赢 } int a = { 1, 2, 4 }; for (int i = 0; i < 3; ++i) { int y = winner(n-a[i], 1-x); // 取 a[i] 个石子，博弈方变为对方 if (y == x) return x; // 己方赢 } return 1-x; // 对方赢 } |
|
1 |
int theWinner = winner(n, 0); // 甲方先开始 |
这个函数的确可以 Work，但是，直观上看，最坏情况下，时间复杂度是 O(3^n)，当然，实际分析是小于这个数的，但仍然太大。有好的办法吗？
动态规划：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
int (*gm)[2]; // gm[0] 未用 int winner(int n, int x) { assert(n >= 1); switch (n) { case 1: return 1-x; // 对方赢 case 2: return x; // 己方赢 case 3: return x; // 己方赢 case 4: return 1-x; // 对方赢 } int a[] = { 1, 2, 4 }; for (int i = 0; i < 3; ++i) { int n2 = n-a[i]; if (gm[n2][1-x] == -1) gm[n2][1-x] = winner(n2, 1-x); // 取 a[i] 个石子，博弈方变为对方 if (gm[n2][1-x] == x) return x; // 己方赢 } return gm[n][x] = 1-x; // 对方赢，同时簿记 } int main(int argc, char* argv[]) { if (argc < 2) { fprintf(stderr, "usage %s number(must >= 1)n", argv[0]); return 3; } int n = atoi(argv[1]); if (n < 1) { fprintf(stderr, "usage %s number(must >= 1)n", argv[0]); return 3; } gm = new int[n+1][2]; // gm[0] 未用 for (int i = 0; i <= n; ++i) gm[i][0] = gm[i][1] = -1; printf("%dn", winner(n, 0)); delete [] gm; return 0; } |
观察结果，我们会发现这样的模式：
1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 …
也就是说，如果 n % 3 == 1，则 乙(1) 赢，否则，甲(0) 赢，想想为什么？
