（转）巴氏（bash）威佐夫（Wythoff）尼姆（Nim）博弈之模板

转自：http://colorfulshark.cn/wordpress/巴氏（bash）威佐夫（wythoff）尼姆（nim）博弈之模板-823.html

最近研究了一下博弈论（听起来很高大上），当然，这只是博弈论中的冰山一角，但不可否认，巴氏（bash）博弈，威佐夫（Wythoff）博弈和尼姆（Nim）博弈这三种在ACM比赛中也是相当重要的，而最大的问题就是，博弈理解起来有较大的难度，即使理解了，也很难快速转换成代码，这对于做题来说是很不利的，于是，我就决定写一套模板，包括多一点接口，从而方便以后的使用，当然，虽然说是自己写的，但也是参考了别人的代码，所以别告我侵权哈。

首先是Bash（巴氏）博弈，这是比较简单的一种，原理就不解释了，相信大家都懂，代码很简短，只需要输入这一堆石子的数目，输赢立刻见分晓

#include<iostream>

using namespace std;

int main(void)

{

    int cas,total,price;

    scanf("%d",&cas);

    while(cas--)

    {

        scanf("%d%d",&total,&price);

        if(total%(price+))

            cout<<"先手赢"<<endl;

        else

            cout<<"先手输"<<endl;

    }

    return ;

}

接下来上威佐夫（Wythoff）博弈，石子变成两堆，难度也大幅提升，但是

#include<iostream>

#include<cmath>

#include<stdio.h>

using namespace std;

int main ()

{

    int a,b,dif;

    double p=(sqrt((double))+)/double();

    while(cin>>a>>b)

    {

        dif=abs(a-b);//取差值

        a=a<b?a:b;//取较小的值

        if(a==(int)(p*dif))//判断是不是奇异局势

            printf("0\n");

        else printf("1\n");

    }

    return ;

}

我擦，为毛代码还是这么短，大神膜拜中。。。（过奖过奖，如有雷同，请相信这真的只是借鉴）

最后奉上尼姆（Nim）博弈，这种博弈其实就是分解成简单的博弈再一一求解

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

using namespace std;

int a[],ans[][];

int main()

{

    int n,i,j,cnt,s;

    while(~scanf("%d",&n),n)

    {

        cnt = ;

        s = ;

        for(i = ; i<n; i++)

        {

            scanf("%d",&a[i]);

            s^=a[i];

        }

        for(i = ; i<n; i++)

        {

            if(a[i] > (s^a[i]))

            {

                ans[cnt][] = a[i];

                ans[cnt][] = s^a[i];

                cnt++;

            }

        }

       if(cnt)//判断先手是胜是负

        {

            printf("Yes\n");

            for(i = ; i<cnt; i++)

                printf("%d %d\n",ans[i][],ans[i][]);//输出若先手为胜的走法

        }

        else

            printf("No\n");

            cout<<cnt<<endl;//输出使先手为胜的方案的数目

    }

    return ;

}

这个稍微长一点，因为里面增加了很多步骤，大大方便了题目的求解。

从今天开始，你就可以骄（zhuang）傲（bi）的说：“今朝获此三模板，从此博弈是水题！”

巴特西

（转）巴氏（bash）威佐夫（Wythoff）尼姆（Nim）博弈之模板

最新文章

热门文章