即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

博弈,三种博弈 巴什博奕,尼姆博奕,威佐夫博弈

编程语言 sizaif 30℃ 0评论

三种博弈



Bash Game:同余理论       Hdu 1846  hdu 2189 hdu
2147

Nim  Game:异或理论    
Hdu 1907 hdu 2509  hdu 1850

Wythoff Game:  黄金分割      hdu1527

 

巴什博奕:     
只有一堆n个物品,两个人轮流从这堆物品中取物,
规定每次至少取一个,最多取
m个。最后取光者得胜

威佐夫博弈:有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,不封顶,最后取光者得胜。


尼姆博奕:
三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,不封顶,最后取光者得胜。


 

三种博弈 正好对应1
2
3
堆物品问题;

巴什博奕,
用 同余来理解
n=(m+1)*k+s;  
先手赢得条件为 每次都留给对方
(m+1)的倍数即可,
即 每次只拿s ;
最后先手必赢
所以先手赢得条件 n%(m+1)!=0;

尼姆博奕,
用异或 运算,
同时又引用二进制思想,三堆物品
存在一个定理:

Bouton定理先手能够在非平衡尼姆博弈中取胜,而后手能够在平衡的尼姆博弈中取胜

所以存在一个奇异局势(0,0,0)
或者(0,n,n) 
无论谁遇到奇异局势
,必输,
所以先手赢得条件为把奇异局势留给对方
而奇异局势 正是 (a^b^c=0)  所以
有 先手赢得条件为

(a^b^c)!=0

威佐夫博弈
通过找规律发现 黄金分割点0.618 
而威佐夫恰是1.618
所以

设两堆物品的初始值为(xy),且x,则另z=y-x

w=int[
z*
sqrt5+1))/2 
]

w=x,则先手必败,否则先手必胜。




巴什博奕题目 

hdu2149 

http://acm.hdu.edu.cn/showproblem.php?pid=2149


#include 
#include 

using namespace std;

int main()
{
    int n,m;
    while(~scanf("%d %d",&m,&n))
    {
        if(!(m%(n+1)))
            printf("none\n");
        else
        {
            if(m








hdu 1846 http://acm.hdu.edu.cn/showproblem.php?pid=1846




#include 
#include 

using namespace std;

int main()
{
    int T,n,m;
    scanf("%d",&T);
    {
        while(T--)
        {
            scanf("%d%d",&n,&m);
            if((n%(m+1))!=0)
                printf("first\n");
            else
                printf("second\n");
        }
    }
    return 0;
}





hdu 2147  http://acm.hdu.edu.cn/showproblem.php?pid=2147

#include 
#include 

using namespace std;

int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m),(n|m))
    {
        if(n%2&&m%2)
            printf("What a pity!\n");
        else
            printf("Wonderful!\n");
    }
    return 0;
}



尼姆博奕题目

hdu 1849   http://acm.hdu.edu.cn/showproblem.php?pid=1849

#include 
#include 

using namespace std;

int main()
{
    int x,y,n,i,sum;
    while(cin>>n&&n)
    {
        sum=0;
        for(i=0;i>x;
            sum^=x;
        }
        if(sum)
            printf("Rabbit Win!\n");
        else
            printf("Grass Win!\n");
    }
    return 0;
}



hdu 1907   http://acm.hdu.edu.cn/showproblem.php?pid=1907

#include 
#include 
#include 

using namespace std;

int main()
{
    int t,n,m,res;
    int a[5000];
    cin>>t;
    while(t--)
    {
        cin>>n;
        m=res=0;
        memset(a,0,sizeof(a));
        for(int i=0;i>a[i];
            m^=a[i];
            if(m>1)
                res++;
        }
        if((m&&res)||(m==0&&res==0))//john 先手, 当他m 不等于0  并且 res的个数大于0 胜利
            printf("John\n");//或者 0 并且res=0;
        else
            printf("Brother\n");
    }
    return 0;
}



hdu 2509   http://acm.hdu.edu.cn/showproblem.php?pid=2509




/*
  最后一个人拿 则输,
  分为两种 即 1.全是孤单堆时 即全为1 时 考虑奇数和偶数问题, 奇数则先手异或结果为1 偶数异或为0
  在此条件下 奇数则先手必输, 偶数先手必赢.
  2. 当有充满堆是(存在堆数 数目超过1) 此时就要考虑
*/

#include 
#include 
#include 
#include 


using namespace std;

int a[500];
int main()
{
    int n,res,m,sum;
    int  full;
    while(cin>>n)
    {
        res=sum=0;
        full=0;
        for(int i=0;i>a[i];
            sum^=a[i];
            printf("%d**\n",sum);
            if(a[i]>1)
                full=1;
        }
        if(full)// 非孤单堆
        {
            if(sum)
                printf("Yes\n");
            else
                printf("No\n");
        }
        else//孤单堆  考虑多种
        {
            if(!sum)//
            {
                printf("Yes\n");
            }
            else
            {
                printf("%d***\n",n&1);
                if((n&1))
                    printf("No\n");//  一定拿最后一个
                else
                    printf("Yes\n");//留下最后一个3
            }
        }

    }
    return 0;
}



威佐夫博弈题目


hdu 1527   http://acm.hdu.edu.cn/showproblem.php?pid=1527

#include 
#include 
#include 

using namespace std;

int main()
{
    int n,m,k,ans;
    while(cin>>n>>m)
    {

        k=fabs(n-m);
        ans=(int)((k*(sqrt(5)+1)/2));
        if(ans==min(n,m))
            printf("0\n");
        else
            printf("1\n");

    }
    return 0;
}








转载请注明:CodingBlog » 博弈,三种博弈 巴什博奕,尼姆博奕,威佐夫博弈

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情