首页 > 试题广场 >

Nim游戏

[编程题]Nim游戏
  • 热度指数：2609 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
这是一个经典的博弈。
你和你的朋友，两个人玩一个游戏。
1.桌子上有 n 个石头
2.你和你的朋友轮流取石头，你先手。
3.每一回合可以取 1~3 个石头。
4.轮到你的朋友时桌上没有石头则你获胜，否则你的朋友获胜。

你和你的朋友都尽力让自己获胜，如果你有方法必胜，则返回 true ，如果你的朋友有方法必胜，则返回 false

数据范围：
示例1

输入

4

输出

false

说明

第一轮不管你取几个石头，第二轮你的朋友都一定能全部取走，则必输。
示例2

输入

2

输出

true

说明

第一轮你可以直接取走全部石头。
算法知识视频讲解
添加回答
Java
倔强小头头像 倔强小头 
public boolean NimGame (int n) {
       if (n <= 4) {
        return n == 1 || n == 2 || n == 3;
        }
        return n%4 != 0; 
    }

发表于 2021-11-26 19:58:30 回复(0)
每天一通offercall头像 每天一通offercall
可以反过来考虑朋友必赢的情况，即n%4 == 0
发表于 2021-11-28 10:01:09 回复(0)
zkingcode头像 zkingcode
经典游戏：抢“20” 
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return bool布尔型
     */
    bool NimGame(int n) {
        return n % 4 != 0;
    }
};


编辑于 2024-04-11 09:33:10 回复(0)
Hanson_Zhong头像 Hanson_Zhong

这是一个经典的博弈，也称为“取石子游戏”。它是一个博弈论中的基础问题。为了判断是否能必胜，我们可以采用“博弈树”的思想，从最终的情况开始分析，逐渐回到初始状态，判断每个状态的必胜必败性。具体的分析过程如下：

  1. 当桌子上只有 1-3 个石头时，无论先手后手怎么取，都可以获胜。因此，当石头的数量为 1-3 时，返回 true。

  2. 当桌子上有 4 个石头时，无论先手怎么取，后手都可以把剩下的石头取完，因此先手必输。因此，当石头的数量为 4 时，返回 false。

  3. 当桌子上有 5、6、7 个石头时，先手可以先取 1、2、3 个石头中的任意一个，然后把剩下的石头留给后手。此时，后手必输。因为无论后手怎么取，先手都可以保证自己取完最后一个石头，因此先手必胜。因此，当石头的数量为 5、6、7 时，返回 true。

  4. 当桌子上有 8 个石头时，无论先手怎么取，后手都可以通过取走一定数量的石头，让桌子上剩下的石头为 5、6、7 三种情况之一，使得后手必胜。因此，当石头的数量为 8 时，返回 false。

  5. 当桌子上有 9、10、11 个石头时，先手可以通过取走一定数量的石头，让桌子上剩下的石头为 8，让后手必输。因此，当石头的数量为 9、10、11 时，返回 true。

  6. 当桌子上有 12 个石头时，无论先手怎么取，后手都可以通过取走一定数量的石头，让桌子上剩下的石头为 9、10、11 三种情况之一，使得后手必胜。因此，当石头的数量为 12 时，返回 false。

通过以上分析，我们可以总结出规律：当桌子上的石头数量为 4 的倍数时，先手必输；否则，先手必胜。

因此，我们只需要判断桌子上的石头数量是否为 4 的倍数即可。如果是，返回 false，否则返回 true。

发表于 2023-06-10 17:11:54 回复(0)
勿忘5头像 勿忘5

这是一个经典的博弈，也称为“取石子游戏”。它是一个博弈论中的基础问题。为了判断是否能必胜，我们可以采用“博弈树”的思想，从最终的情况开始分析，逐渐回到初始状态，判断每个状态的必胜必败性。具体的分析过程如下：

  1. 当桌子上只有 1-3 个石头时，无论先手后手怎么取，都可以获胜。因此，当石头的数量为 1-3 时，返回 true。

  2. 当桌子上有 4 个石头时，无论先手怎么取，后手都可以把剩下的石头取完，因此先手必输。因此，当石头的数量为 4 时，返回 false。

  3. 当桌子上有 5、6、7 个石头时，先手可以先取 1、2、3 个石头中的任意一个，然后把剩下的石头留给后手。此时，后手必输。因为无论后手怎么取，先手都可以保证自己取完最后一个石头，因此先手必胜。因此，当石头的数量为 5、6、7 时，返回 true。

  4. 当桌子上有 8 个石头时，无论先手怎么取，后手都可以通过取走一定数量的石头，让桌子上剩下的石头为 5、6、7 三种情况之一，使得后手必胜。因此，当石头的数量为 8 时，返回 false。

  5. 当桌子上有 9、10、11 个石头时，先手可以通过取走一定数量的石头，让桌子上剩下的石头为 8，让后手必输。因此，当石头的数量为 9、10、11 时，返回 true。

  6. 当桌子上有 12 个石头时，无论先手怎么取，后手都可以通过取走一定数量的石头，让桌子上剩下的石头为 9、10、11 三种情况之一，使得后手必胜。因此，当石头的数量为 12 时，返回 false。

通过以上分析，我们可以总结出规律：当桌子上的石头数量为 4 的倍数时，先手必输；否则，先手必胜。

因此，我们只需要判断桌子上的石头数量是否为 4 的倍数即可。如果是，返回 false，否则返回 true。

发表于 2023-03-12 20:38:58 回复(0)
小谷围做题家头像 小谷围做题家 
package main
// import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return bool布尔型
*/
func NimGame( n int ) bool {
    return n%4!=0
}

发表于 2023-01-31 21:19:35 回复(0)
Python 3
danspace头像 danspace 
class Solution:
    def NimGame(self , n: int) -> bool:
        # write code here
        if n%4 == 0:
            return False
        return True

发表于 2022-04-22 11:11:21 回复(0)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def NimGame(self , n: int) -> bool:
        # write code here
        #朋友先的情况下一起凑4 第一把n-4*k 当/小于4 都可以赢/4的倍数输了
        return False if n%4==0 else True

发表于 2022-01-07 01:41:26 回复(0)
C++
牛客438919385号头像 牛客438919385号
每一回合可以取 1~3 个石头，就是说可以保证每次可以双方一共取4个石头。
你先手，意味着只要先手后，剩下的石头是4的倍数，就可以保证最后的胜利。
所以原本石头数除以4的余数大于0，把余数取走，就能保证胜利。

发表于 2021-12-17 08:55:19 回复(0)
C++
HarlanHW201809051315156头像 HarlanHW201809051315156 
bool NimGame(int n) {
    return n%4;
}

发表于 2021-12-06 20:34:21 回复(0)
提交观点

问题信息

博弈
难度：
10条回答 1294浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号