尼姆博弈(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 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

负载均衡的基本算法

负载均衡的基本算法,主要有以下几种(参考F5产品): 随机:负载均衡方法随机的把负载分配到各个可用的服务器上,通过随机数生成算法选取一个服务器,然后把连接发送给...

2627
来自专栏Python爬虫与算法进阶

敲敲级简单的鉴别H图片的小程序

首先,来看一下程序运行结果的截图 ? 功能实现 一、下载SDK pip install qcloud_image 先贴出官方给的实例代码: #!/usr/bi...

2974
来自专栏小詹同学

知乎大神爬取高颜值美女(Python爬虫+人脸检测+颜值检测)

这是一篇来自知乎大神的技术文章 ---- 写在前面: 本文作者:邓卓 原文链接:本文转发修改已取得原作者授权 https://zhuanlan.zhihu.c...

7397
来自专栏FreeBuf

使用Python和Tesseract来识别图形验证码

各位在企业中做Web漏洞扫描或者渗透测试的朋友,可能会经常遇到需要对图形验证码进行程序识别的需求。很多时候验证码明明很简单(对于非互联网企业,或者企业内网中的应...

5585
来自专栏计算机视觉战队

Caffe源码---------主要框架介绍

初学者的我感觉看代码就是一个煎熬啊!但是某人说过一句话:“Don’t be afraid to read the code!”现在我写一下简单的介绍,准备给入门...

3465
来自专栏友弟技术工作室

(爬虫)书籍和电影,程序员不可或缺爬虫步骤1. 分析目标网页的特征2. 找到需要爬取的数据3.多页面数据的跳转4.数据存储

周五, 由于同事给了一个下载书籍的网站。所以心血来潮,想写一个爬虫demo,把数据都爬下来。然后发现一个电影网站也是类似,于是乎。代码重用。 爬虫步骤 分析目标...

3176
来自专栏不止思考

网络中的「动态路由算法」,你了解吗?

在计算机网络中,路由器的一个很重要责任就是要在端对端的节点中找出一条最佳路径出来,通过自己与相邻节点之间的信息,来计算出从自己位置到目的节点之间的最佳线路,这种...

1675
来自专栏七夜安全博客

“跳一跳”游戏外挂原理详析(自动版)

1163
来自专栏小小詹同学

知乎大神爬取高颜值美女(Python爬虫+人脸检测+颜值检测)

这是一篇来自知乎大神的技术文章

77310
来自专栏新智元

【加入星际2征程】DeepMind星际争霸2开源机器学习平台入门

【新智元导读】DeepMind此前开源了《星际争霸2》机器学习训练平台,这个平台对于state-of-the-art的深度强化学习算法来说是极好的测试平台。希望...

2845

扫码关注云+社区