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

相关文章

来自专栏ATYUN订阅号

【深度学习】图片风格转换应用程序:使用CoreML创建Prisma

WWDC 2017让我们了解了苹果公司对机器学习的看法以及它在移动设备上的应用。CoreML框架使得将ML模型引入iOS应用程序变得非常容易。 ? 大约一年前,...

4108
来自专栏人人都是极客

5.训练模型之利用训练的模型识别物体

接下来我们开始训练,这里要做三件事: 将训练数据上传到训练服务器,开始训练。 将训练过程可视化。 导出训练结果导出为可用作推导的模型文件。 配置 Pipelin...

3544
来自专栏生信宝典

2018 升级版Jaspar数据库

R包ggseqlogo 绘制seq logo图和Seq logo 在线绘制工具—Weblogo介绍了如何用R脚本和在线工具绘制seq logo图,用于展现转录因...

1132
来自专栏小石不识月

如何将机器学习模型转移到产品中

针对于特定问题(例如自然语言处理,即 NLP,或图像识别)的深度学习模型开发、训练和调参,需要耗费时间与资源。这通常还包括使用功能强大的处理器来训练大型数据集上...

1682
来自专栏小白课代表

更新 | SPSS 25 64位 安装教程。

1612
来自专栏AI科技大本营的专栏

Hinton胶囊理论代码开源,上线即受热捧

当前的深度学习理论是由Geoffrey Hinton大神在2007年确立起来的,但是如今他却认为,“CNN的特征提取层与次抽样层交叉存取,将相同类型的相邻特征检...

2719
来自专栏10km的专栏

SSD(Single Shot MultiBox Detector):绘制训练过程loss,accuracy曲线

关于标准Caffe绘制loss,accuracy曲线参见这篇博客,写得很详细《Caffe 绘制训练过程loss,accuracy曲线》,而训练SSD时绘制los...

3388
来自专栏IT派

用40行Python代码 实践高大上的人脸识别

很多人都认为人脸识别是一项非常难以实现的工作,看到名字就害怕,然后心怀忐忑到网上一搜,看到网上N页的教程立马就放弃了。这些人里包括曾经的我自己。其实如果如果你不...

1250
来自专栏owent

POJ PKU 1474 Video Surveillance 解题报告

写这题的目的是看完了zzy的论文,写了半平面交,验证一下正确性,结果发现我写的问题还是很多的。

441
来自专栏机器学习实践二三事

使用Faster-Rcnn进行目标检测(实践篇)

原理 上一篇文章,已经说过了,大家可以参考一下,Faster-Rcnn进行目标检测(原理篇) 实验 我使用的代码是python版本的Faster Rcnn,官方...

6726

扫码关注云+社区