现在的位置: 首页 > 综合 > 正文

简单博弈总结

2018年04月24日 ⁄ 综合 ⁄ 共 6554字 ⁄ 字号 小 中 大 ⁄ 评论关闭
文章目录

看到大家都写了博弈的总结，我也来一发。

友情链接：

http://blog.csdn.net/sio__five/article/details/17053753（吴琦大婶的博弈总结）

http://blog.csdn.net/u010468553/article/details/17074501（中午好大婶的博弈总结）

我这里总结三种最基础的博弈：巴什博弈、威佐夫博弈、尼姆博弈。

巴什博弈：

有一堆石子，石子个数为n，两人轮流从石子中取石子出来，最少取一个，最多取m个。最后不能取的人输，问你最后的输赢情况。
这种就是可以直接判断必败态的问题。如果这堆石子少于或者等于m个，那么先手赢。如果石子数目为m+1个，那么先手必输，因为无论先手怎么拿石子，后手都可以直接把剩下的石子全部拿走。如果石子数目为m+1<n<2(m+1),那么先手就可以拿走n-(m+1)个石子，使得对手面对m+1的必败态，这样先手必赢。所以如此推算下去，我们就知道当n%(m+1)==0时，先手输，否则先手赢

HDU 1846 Brave Game

最基础的巴什博弈

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define PI acos(-1)
using namespace std;
void bash(int n,int m)
{
    if(n%(m+1)!=0)  printf("first\n");
    else    printf("second\n");
}
int main()
{
    int n,m,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        bash(n,m);
    }
    return 0;
}

HDU 1847 Good Luck in CET-4 Everybody!

巴什博弈的变形，每次取2的幂次个（1，2，4，8……），1、2、4、5都是必胜态，3、6是必败态，容易想到3相当于(m+1)，6就是2*(m+1)，3<n<6时也都是必胜态。由于任何一个非3的倍数的数减1(2^0)或减2(2^1)都会成为3的倍数成为必败态，所以当n不是3的倍数时为必胜态。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define PI acos(-1)
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n%3==0)  printf("Cici\n");
        else    printf("Kiki\n");
    }
    return 0;
}

HDU 2149 Public Sale

巴什博弈，如果先手能赢，问你该怎么取
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define PI acos(-1)
using namespace std;
void bash(int m,int n)
{
    if(m%(n+1)!=0)
    {
        if(m<=n)
        {
            printf("%d",m);
            for(int i=m+1;i<=n;i++) printf(" %d",i);
            printf("\n");
        }
        else    printf("%d\n",m%(n+1));
    }
    else    printf("none\n");
}
int main()
{
    int n,m;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        bash(m,n);
    }
    return 0;
}

威佐夫博弈

有两堆石子，石子数目分别为n和m,现在两个人轮流从两堆石子中拿石子，每次拿时可以从一堆石子中拿走若干个，也可以从两中拿走相同数量的石子，拿走最后一颗石子的人赢。
我们用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有如下三条性质：
1。任何自然数都包含在一个且仅有一个奇异局势中。
2。任意操作都可将奇异局势变为非奇异局势。若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3。采用适当的方法，可以将非奇异局势变为奇异局势。
假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b  – bk个物体，即变为奇异局势；如果 a = ak ，  b < bk ,则同时从两堆中拿走 ak – ab – ak个物体,变为奇异局势（ ab – ak , ab – ak+ b – ak）；如果a > ak ，b= ak + k,则从第一堆中拿走多余的数量a – ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，a=aj
（j < k）,从第二堆里面拿走 b – bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b – aj 即可。
从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
  那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：ak =[k（1+√5）/2]，bk= ak + k  （k=0，1，2，…,n 方括号表示取整函数)
(这里不加证明）
这样的话我们对于两堆石子的数目就可以直接判断是不是属于奇异局势，若是，则先手赢，否则后手赢

HDU 1527 取石子游戏

基础威佐夫博弈
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define PI acos(-1)
using namespace std;
void wzf(int n, int m)
{
    if(n > m)
    {
        int t=n;
        n=m;
        m=t;
    }
    int k = m-n;
    int a = (k * (1.0 + sqrt(5.0))/2.0);
    if(a == n)						//奇异局势
        printf("0\n");
    else
        printf("1\n");
}
int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        wzf(a,b);
    }
    return 0;
}

HDU 2177 取(2堆)石子游戏

威佐夫博弈，不过如果先手胜需要输出先手取完的剩余石子数，也就是先手取石子的策略。
分两种情况，取两堆的和只取一堆的。
取两堆的较简单，根据威佐夫博弈的性质可知k对应唯一的奇异局势，取两堆k值不变直接输出对应的奇异局势即可。
取一堆的情况可保持m,n不变，再定义m1=m,n1=n，保持m1和n1变化每次取一个，让m1和n一组，m和n1一组，不停的枚举直到性质中的ak值满足奇异局势输出
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define PI acos(-1)
using namespace std;
void wzf(int n, int m)
{
    if(n > m)
    {
        int t=n;
        n=m;
        m=t;
    }
    int k = m-n;
    int a = (k * (1.0 + sqrt(5.0))/2.0);
    if(a == n)
        printf("0\n");
    else
    {
        printf("1\n");
        if(n>a) printf("%d %d\n",a,m-(n-a));            //两堆都取的情况
        int n1=n,m1=m,k1=k,k2=k,x;
        while(1)                        //只取一堆的情况
        {                            //枚举只减n和只减m
            n1--;
            k1=m-n1;
            m1--;
            k2=max(m1,n)-min(m1,n);
            x=(k1 * (1.0 + sqrt(5.0))/2.0);
            if(n1==x)   {printf("%d %d\n",min(n1,m),max(n1,m));break;}
            x=(k2 * (1.0 + sqrt(5.0))/2.0);
            if(m1==x)   {printf("%d %d\n",min(m1,n),max(m1,n));break;}
        }
    }
}
int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b),a||b)
    {
        wzf(a,b);
    }
    return 0;
}

尼姆博弈

每次都喜欢说成尼玛博弈，刚开始写的也是尼玛博弈，但是我觉得对学习得抱持一个严谨的态度，于是我又老老实实改成了尼姆。。。
尼姆博奕（Nimm Game）：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。那么如何判断三个数是不是奇异局势呢，总结发现奇异局势的每个数字相异或的值为0，也就是必败态。
在吴琦的博客里有较好的证明：http://blog.csdn.net/sio__five/article/details/17053753#t8
这里引用过来：
1、最后的状态，全为零，显然成立；
2、对于某个局面(a1,a2,...,an)，若a1^a2^...^an<>0，一定存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai'=ai^k，此时a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。
3、对于某个局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。因为异或运算满足消去率，由a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai'。所以将ai改变成ai'不是一个合法的移动。证毕。
为了表示方便之后都以sum代表a1^a2^...^an

POJ 2234 Matches Game

基础尼姆博弈
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define PI acos(-1)
using namespace std;
int a[25];
int main()
{
    int m,i;
    while(scanf("%d",&m)!=EOF)
    {
        int sum=0;
        for(i=0;i<m;i++)
        {
            scanf("%d",&a[i]);
            sum^=a[i];
        }
        if(sum==0)  printf("No\n");
        else    printf("Yes\n");
    }
    return 0;
}

HDU 1850 Being a Good Boy in Spring Festival

尼姆博弈，输出先手胜的情况下第一步的走法个数
通过二进制来看，不难得出a^b^b=a，也就是说对同一个数异或两次另一个数之后这个数的值不变，利用这点，sum ^ a[i]（a[i] ^ sum）可以得出除了a[i]这堆石子之外其他所有石子的异或值。
而由a^b^b=a还可得出b^b=0，因为a^0=a 任何一个数和0异或都等于它本身
根据尼姆博弈的证明，a1^a2^...^an=k时必定存在一个ai使得ai ^ k<ai，所以当a[i] ^ sum<a[i]时就能通过对a[i]这堆石子的一定操作使之变为必败态。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define PI acos(-1)
using namespace std;
int a[105];
int main()
{
    int m,i,k,sum,t;
    while(scanf("%d",&m),m)
    {
        k=sum=0;
        for(i=0;i<m;i++)
        {
            scanf("%d",&a[i]);
            sum^=a[i];
        }
        for(i=0;i<m;i++)
        {
            t=sum^a[i];
            if(a[i]>t)   k++;
        }
        printf("%d\n",k);
    }
    return 0;
}

HDU 2176 取(m堆)石子游戏

尼姆博弈，这回如果先手胜，要输出可获胜的走法。在先手取胜的情况下，还是用a[i] ^ sum<a[i]来判断是否可通过取a[i]这堆石子来变成必败态，直接取走a[i] - a[i] ^ sum个石子使之变成a[i] ^ sum 个，此时所有堆石子的异或值为 (sum ^ a[i] ) ^ (a[i] ^ sum) 相当于a ^ a  ，结果为0
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define PI acos(-1)
using namespace std;
int a[200005];
int main()
{
    int m,i,k,sum,t;
    while(scanf("%d",&m),m)
    {
        sum=0;
        for(i=0;i<m;i++)
        {
            scanf("%d",&a[i]);
            sum^=a[i];
        }
        if(sum==0)  printf("No\n");
        else
        {
            printf("Yes\n");
            for(i=0;i<m;i++)
            {
                t=sum^a[i];
                if(a[i]>t)   printf("%d %d\n",a[i],t);
            }
        }
    }
    return 0;
}
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞