编程之好1.13——NIM(3)两堆石头的游戏

问题：

       假设有两堆石头，有两个玩家会根据如下的规则轮流取石头：

每人每次可以从两堆石头中各取出数量相等的石头，或者仅从一堆石头中取出

任意数量的石头；最后把剩下的石头一次拿光的人获胜。请问在哪些局面（依

据两堆石头中的石头个数）下，先取石头的玩家有必胜的策略。

解法：

      类似构造质数的筛选方法，这里我们利用找到的必输局面（后取的玩家有必胜策略）

来筛去掉能通过一次操作达该必输局面的其它必胜局面（先取的玩家有必胜策略）。

最后选出的局面都是必输局面。

构造必胜策略：

      如果一开始的局面就是必输局面，那么可能先取的玩家没有必胜策略（当然如果后取

的玩家不太聪明，先取的玩家依然有可能能赢）。如果一开始的局面不是必输局面，

那么先取的玩家一定有必胜策略，且必胜策略就是保证每次都将当前非必输局面转变

为必输局面（后取的玩家必输）。

#include <iostream> #include <algorithm> #include <cstdlib> using namespace std; // filter method #define MAXN 10000 #define CLEAR(a) memset((a), 0, sizeof(a)) char ns[MAXN][MAXN]; // 用于筛选出必输局面 int v[MAXN];<span style="WHITE-SPACE: pre"> </span>// 保存(ind,v[ind])的必输局面对 int main() { int a, b, i, j, abmin, abmax, k; <span style="WHITE-SPACE: pre"> </span>// 输入的数据(a,b)表示两堆石头中石头的个数对 while (cin >> a >> b) { <span style="WHITE-SPACE: pre"> </span>// 筛选出可能用到的所有必输局面 abmax = max(a, b); for (i=1; i<=abmax; i++) { if (v[i]) continue; for (j=i+1; j<=MAXN; j++) { if (!ns[i][j]) { printf("(%d,%d) ", i, j); v[i] = j; v[j] = i; for (k=1; k+i<=abmax; k++) ns[i+k][j+k] = 1; break; } } } cout << endl; <span style="WHITE-SPACE: pre"> </span>// 使用必胜策略 do { printf("current (%d,%d)n", a, b); <span style="WHITE-SPACE: pre"> </span>// 我方（先取的玩家）的策略 if (b==0) { printf("I: extract (%d,0) from (%d,0)n", a, a); a = 0; break; } else if (a==0) { printf("I: extract (0,%d) from (0,%d)n", b, b); b = 0; break; } else if (a==b) { printf("I: extract (%d,%d) from (%d,%d)n", a, b, a, b); a = b = 0; break; } <span style="WHITE-SPACE: pre"> </span>// 将非必输局面(a,b)转变为必输局面(v[b],b)或(a,v[a]) else if (v[b] < a) { printf("I: extract (%d,0) from (%d,%d)n", a-v[b], a, b); a = v[b]; } else { printf("I: extract (0,%d) from (%d,%d)n", b-v[a], a, b); b = v[a]; } <span style="WHITE-SPACE: pre"> </span>// 对方随机选取 int select = rand()%3; if (select == 0) { int suba = rand()%a+1; printf("She: extract (%d,0) from (%d,%d)n", suba, a, b); a = a-suba; } else if (select == 1) { int subb = rand()%b+1; printf("She: extract (0,%d) from (%d,%d)n", subb, a, b); b = b-subb; } else { abmin = min(a,b); int sub = rand()%abmin+1; printf("She: extract (%d,%d) from (%d,%d)n", sub, sub, a, b); a = a-sub; b = b-sub; } }while (a>0 || b>0); } }