尼姆博弈(Nim Game)

简述

有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人的时候所有石子堆都已经被拿空了,则判负(因为他此时没有任何合法的移动)

分析

这游戏看上去有些复杂,我们先从简单情况开始研究,如果轮到你时,只剩下一堆石子,那么此时必胜策略肯定是把这堆石子全部拿完,然后对手没有石子拿就输了;如果剩下两堆不相等的石子,必胜策略是通过取多的一堆石子将两堆石子变得相等,之后对手如果在某一堆拿若干颗,你就在另一堆拿同样多的数量,直至胜利;但是如果还剩三堆,应该怎么分析呢?假设有三堆石子(a,b,c),我们前面说到,如果只有两堆石子,并且石子数量满足(n,n),谁先手谁就输。其实我们可以把三堆石子问题转换成两堆,只要满足状态(0,n,n)并且此时是对方先手,那我方按照两堆石子的取法,就能获胜。对于这种(0,n,n)的局势,我们称为奇异局势。对任何奇异局势(a,b,c)都有a^b^c=0(^表示异或),如果我们面对非奇异局势,要如何变为奇异局势呢?假设a<b<c,我们只要将c变为a^b即可。道理很简单,因为a^b^(a^b)=0。要将c变为a^b也很简单,只要从c中减去c-a^b即可

例(14,21,39),14^21=27,39-27=12,所以从39中拿走12个,即可变成奇异局势(14,21.27)

例题

    1.HDU1849 Rabbit and Grass

思路:将输入的值存在数组中,然后连续求异或(0对任意数异或都得任意数本身)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m;
    int a[1001];
    while(cin>>m&&m)
    {
        int res = 0;
        memset(a,0,sizeof(a));
        for(int i = 0;i < m;i++)
        {
            cin>>a[i];
            res ^= a[i];
        }
        if(res == 0)
            cout<<"Grass Win!"<<endl;
        else
            cout<<"Rabbit Win!"<<endl;
    }
    return 0;
}

参考文章:https://hrbust-acm-team.gitbooks.io/acm-book/content/game_theory/nimbo_yi.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2506
来自专栏落花落雨不落叶

canvas画简单电路图

58411
来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

6588
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2667
来自专栏C#

DotNet加密方式解析--非对称加密

    新年新气象,也希望新年可以挣大钱。不管今年年底会不会跟去年一样,满怀抱负却又壮志未酬。(不过没事,我已为各位卜上一卦,卦象显示各位都能挣钱...)...

4798
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5286
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2517
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

3955
来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2102
来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4054

扫码关注云+社区