专栏首页小浩算法一行代码击败 100% 用户,leetcode 尼姆问题求解

一行代码击败 100% 用户,leetcode 尼姆问题求解

大家好,我是小浩哥。

记得还是初中时期,就和同学玩过这样一个游戏。和对手轮流从一堆棋子中取走一个或者多个,最后不能再取的就是输家。

多年以后才知道,这一类游戏被称为尼姆游戏,是一种两个人玩的回合制数学战略游戏。

那这一类问题,我们该如何用代码进行求解?

01、题目示例

第292题:Nim 游戏

你和你的朋友,两个人一起玩 Nim 游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人,每一步都是最优解。编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false 
解释: 如果堆中有 4 块石头,那么你永远不会赢得比赛;
     因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。

02、题目分析

这种问题,如果没有思路,可以先自己找个纸写写画画,找找规律。

首先如果石头数小于 4 个,那么因为你是先手,一把拿走,肯定会赢。

如果石头恰好是 4 个。那不管你是拿了1,2,3个,最后一个都可以被你的对手拿走,所以怎么样都赢不了。这应该是很好理解。

继续分析至 8 个石头:

  • 对于 5、6、7 而言,你只需要对应的拿走 1、2、3,然后留下4个,则对方必输。
  • 但是如果你要面对的是 8,不管先拿(1、2、3)个,另一个人都可以通过 8 - (1、2、3) ,使得你面对 4 个石头,则你必输无疑。

通过观察,我们发现,好像是只要 N 是 4的倍数,我们就必输无疑。

尝试性的写下代码:

//go
func canWinNim(n int) bool {
    return n % 4 != 0
}

难以想象这么简单:

03、证明过程

首先需要说下的是,这个问题属于博弈论。一个非常典型的尼姆游戏。

回到本题,假若对于先手有N个石头,那么后手的可能性有 N-1,N-2,N-3 三种。只有当后手的这三种可能性都必胜时,N 才会必败。因为题目说了,我是聪明人(博弈论前提条件),那如果后手的三种可能性中,有哪一种必败,作为先手,我们一定会走出这种可能性。那这种可能性是什么,其实就是让对方去面对 4 的倍数。如果先手我们遇到一个不是 4 的倍数的值 x,有:

4k > N > 4(k-1)

N 一定处于两个 4 的倍数之间,因为 N 本身不是 4 的倍数,那 N 距离最近的 4 的倍数的值最大为 3。所以,只要我们不是面对 4 的倍数,作为先手,我们一定可以取走(1、2、3),使剩余的值变成 4 的倍数,则后手必输无疑。

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-11-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 挑战程序竞赛系列(49):4.2 推理与动态规划算法(2)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 漫画:脑筋急转弯题目(尼姆问题求解)

    你和你的朋友,两个人一起玩 Nim 游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。

    程序员小浩
  • 硅谷快意恩仇录:战斗力爆表的10对科技公司CEO之争

    硅谷是科技公司的天堂,吸引最有创造力的人来此实现自己的想法。这里孕育着看似千奇百怪,但最终成为科技前沿的互联网技术。

    新智元
  • 资源 | 站在巨人的肩膀,这才是刷算法的正确姿势

    随着中国程序员越来越多,如今,想要通过大厂的面试或者拿到一份高薪 offer,不仅要有过硬的岗位相关的专业知识和实践经历,更重要的是要有扎实的算法基本功。每一轮...

    程序员鱼皮
  • 07. 重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    Zoctopus
  • "Google X"大起底

    “Google X”来源 Google X,是谷歌公司最神秘的一个部门,位于美国旧金山的一处秘密地点,该实验室的机密程度堪比CIA,仅少数几位谷歌高层掌握情况...

    大数据和云计算技术
  • 基于D3.js实现分类多标签的Tree型结构可视化

    今天新来的实习生需要对部分分类文本进行多标签的检测,即根据已构建好的一、二级标签Excel文档,对众包平台人工标注的数据以及机器标注的数据进行评测。 此情此景...

    流川枫
  • 基于D3.js实现分类多标签的Tree型结构可视化

    今天新来的实习生需要对部分分类文本进行多标签的检测,即根据已构建好的一、二级标签Excel文档,对众包平台人工标注的数据以及机器标注的数据进行评测。

    用户1332428
  • Google“炸弹”袭击2004美国总统大选

    Google“炸弹”袭击2004美国总统大选     现在,当打开国际头号网络搜索引擎Google(www.google.com),键入“胡说八道”...

    数据和云01

扫码关注云+社区

领取腾讯云代金券