編程之美1.13——NIM(3)兩堆石頭的游戲

問題：
       假設有兩堆石頭，有兩個玩家會根據如下的規則輪流取石頭：
每人每次可以從兩堆石頭中各取出數量相等的石頭，或者僅從一堆石頭中取出
任意數量的石頭；最後把剩下的石頭一次拿光的人獲勝。請問在哪些局面（依
據兩堆石頭中的石頭個數）下，先取石頭的玩家有必勝的策略。

解法：
      類似構造質數的篩選方法，這裡我們利用找到的必輸局面（後取的玩家有必勝策略）
來篩去掉能通過一次操作達該必輸局面的其它必勝局面（先取的玩家有必勝策略）。
最後選出的局面都是必輸局面。
構造必勝策略：
      如果一開始的局面就是必輸局面，那麼可能先取的玩家沒有必勝策略（當然如果後取
的玩家不太聰明，先取的玩家依然有可能能贏）。如果一開始的局面不是必輸局面，
那麼先取的玩家一定有必勝策略，且必勝策略就是保證每次都將當前非必輸局面轉變
為必輸局面（後取的玩家必輸）。

[cpp]
#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); 
    } 
} 
作者：linyunzju