您现在的位置: 主页 > 华夏黑客联盟 > QQ黑客软件 > 文章内容

黑客基地--编程之美1.13——NIM(3)两堆石头的游戏

作者: QQ黑客 来源:未知 时间: 2013-12-13 阅读:

QQ黑客问题:
       假设有两堆石头,有两个玩家会根据如下的规则轮流取石头:
每人每次可以从两堆石头中各取出数量相等的石头,或者仅从一堆石头中取出
任意数量的石头;最后把剩下的石头一次拿光的人获胜。请问在哪些局面(依
据两堆石头中的石头个数)下,先取石头的玩家有必胜的策略。


黑客基地解法:
      类似构造质数的筛选方法,这里我们利用找到的必输局面(后取的玩家有必胜策略)
来筛去掉能通过一次操作达该必输局面的其它必胜局面(先取的玩家有必胜策略)。
最后选出的局面都是必输局面。
构造必胜策略:
      如果一开始的局面就是必输局面,那么可能先取的玩家没有必胜策略(当然如果后取
的玩家不太聪明,先取的玩家依然有可能能赢)。如果一开始的局面不是必输局面,
那么先取的玩家一定有必胜策略,且必胜策略就是保证每次都将当前非必输局面转变
为必输局面(后取的玩家必输)。


[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


本篇文章来源于 黑客基地-专业的QQ黑客技术最优秀密码破解网站!