首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >2025-06-10:移除石头游戏。用go语言,Alice 和 Bob 玩一个拿石头的游戏,规则如下: - 他们轮流从一堆石头中

2025-06-10:移除石头游戏。用go语言,Alice 和 Bob 玩一个拿石头的游戏,规则如下: - 他们轮流从一堆石头中

作者头像
福大大架构师每日一题
发布于 2025-06-11 04:29:19
发布于 2025-06-11 04:29:19
5600
代码可运行
举报
运行总次数:0
代码可运行

2025-06-10:移除石头游戏。用go语言,Alice 和 Bob 玩一个拿石头的游戏,规则如下:

  • • 他们轮流从一堆石头中拿走石头,Alice 先手。
  • • Alice 第一次拿走的石头数量固定为 10 个。
  • • 之后每次轮到某个玩家时,他必须拿走的石头数量等于对方上一次拿走石头数减 1。
  • • 如果某个玩家无法按规则拿足够的石头,则这个玩家输掉游戏。

给定初始石头总数 n,如果 Alice 最终获胜,返回 true,否则返回 false。

1 <= n <= 50。

输入:n = 12。

输出:true。

解释:

Alice 第一次操作中移除 10 个石头,剩下 2 个石头给 Bob 。

Bob 无法移除 9 个石头,所以 Alice 赢下游戏。

题目来自力扣3360。

一般情况分析

我们需要找到一个通用的方法来判断 Alice 是否能获胜。以下是游戏的步骤:

  1. 1. Alice 第一次拿走 10 个石头,剩余 n - 10 个石头。
  2. 2. Bob 需要拿走 10 - 1 = 9 个石头:
    • • 如果 n - 10 < 9,Bob 无法拿走 9 个,直接输掉游戏,Alice 获胜。
    • • 否则,Bob 拿走 9 个,剩余 n - 10 - 9 = n - 19 个石头。
  3. 3. Alice 需要拿走 9 - 1 = 8 个石头:
    • • 如果 n - 19 < 8,Alice 无法拿走 8 个,输掉游戏,Bob 获胜。
    • • 否则,Alice 拿走 8 个,剩余 n - 19 - 8 = n - 27 个石头。
  4. 4. Bob 需要拿走 8 - 1 = 7 个石头:
    • • 如果 n - 27 < 7,Bob 无法拿走 7 个,输掉游戏,Alice 获胜。
    • • 否则,Bob 拿走 7 个,剩余 n - 27 - 7 = n - 34 个石头。
  5. 5. 游戏继续,每次拿走的石头数量依次减少 1(从 10 开始,然后是 9、8、7、6、...),直到某个玩家无法按规则拿走足够的石头。

关键观察

游戏的关键在于:

  • • Alice 第一次拿走 10 个石头。
  • • 之后每次拿走的石头数量是对方上一次拿走的数量减 1。
  • • 游戏会在某个玩家无法按规则拿走足够的石头时结束。

我们需要找到 n 的临界值,使得 Alice 能够获胜。具体来说:

  • • 如果 n - 10 < 9(即 n < 19),Alice 直接获胜。
  • • 如果 n - 10 - 9 < 8(即 n < 27),Bob 会在第二轮获胜。
  • • 如果 n - 10 - 9 - 8 < 7(即 n < 34),Alice 会在第三轮获胜。
  • • 以此类推。

数学推导

游戏结束的条件是:在某一轮中,剩余的石头不足以让当前玩家拿走所需的石头数量。

  • • 第一轮:Alice 拿走 10,剩余 n - 10
    • • Bob 需要拿走 9,条件是 n - 10 >= 9,即 n >= 19
  • • 第二轮:Bob 拿走 9,剩余 n - 19
    • • Alice 需要拿走 8,条件是 n - 19 >= 8,即 n >= 27
  • • 第三轮:Alice 拿走 8,剩余 n - 27
    • • Bob 需要拿走 7,条件是 n - 27 >= 7,即 n >= 34
  • • 第四轮:Bob 拿走 7,剩余 n - 34
    • • Alice 需要拿走 6,条件是 n - 34 >= 6,即 n >= 40
  • • 第五轮:Alice 拿走 6,剩余 n - 40
    • • Bob 需要拿走 5,条件是 n - 40 >= 5,即 n >= 45
  • • 第六轮:Bob 拿走 5,剩余 n - 45
    • • Alice 需要拿走 4,条件是 n - 45 >= 4,即 n >= 49
  • • 第七轮:Alice 拿走 4,剩余 n - 49
    • • Bob 需要拿走 3,条件是 n - 49 >= 3,即 n >= 52
    • • 但 n 的最大值是 50,因此游戏最多进行到第六轮。

胜负判断

Alice 获胜的条件是游戏在 Bob 的回合无法拿走足够的石头时结束。具体来说:

  • • 如果 n 满足 n - 10 < 9n < 19),Alice 直接获胜。
  • • 如果 n 满足 n - 19 - 8 < 7n < 34)且 n >= 19,Bob 在第三轮无法拿走 7,Alice 获胜。
  • • 如果 n 满足 n - 34 - 6 < 5n < 45)且 n >= 34,Bob 在第五轮无法拿走 5,Alice 获胜。
  • • 如果 n 满足 n - 45 - 4 < 3n < 52)且 n >= 49,Bob 在第七轮无法拿走 3,Alice 获胜。

因此,Alice 获胜的 n 的范围是:

  • n < 19
  • 27 <= n < 34
  • 40 <= n < 45
  • 49 <= n <= 50

代码中的数学公式

代码中的 canAliceWin 函数使用了以下公式: .

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
x := (21 - int(math.Ceil(math.Sqrt(float64(441 - n*8))))) / 2
return x%2 > 0

这个公式的推导如下:

  1. 1. 我们需要找到一个 x,使得 n 落在 Alice 获胜的区间。
  2. 2. Alice 获胜的 n 的临界点可以通过以下不等式描述:
    • • 第一轮:n < 19
    • • 第二轮:n >= 19n - 19 < 8(即 n < 27
    • • 第三轮:n >= 27n - 27 < 7(即 n < 34
    • • 以此类推。
  3. 3. 可以观察到 Alice 获胜的 n 的区间是:
    • [10, 18]n < 19
    • [27, 33]n >= 27n < 34
    • [40, 44]n >= 40n < 45
    • [49, 50]n >= 49n < 52
  4. 4. 这些区间的起始点是 10, 27, 40, 49,可以表示为:
    • • 第一区间:10 = 10
    • • 第二区间:27 = 10 + 9 + 8
    • • 第三区间:40 = 10 + 9 + 8 + 7 + 6
    • • 第四区间:49 = 10 + 9 + 8 + 7 + 6 + 5 + 4
  5. 5. 这些起始点可以表示为:
    • S(k) = 10 + 9 + 8 + ... + (11 - k),其中 k 是区间编号。
  6. 6. 通过数学推导,可以找到一个关于 n 的二次不等式,从而得到 x 的表达式。

时间复杂度和空间复杂度

  • • 时间复杂度:O(1),因为公式计算是常数时间操作。
  • • 空间复杂度:O(1),没有使用额外空间。

总结

  1. 1. Alice 第一次拿走 10 个石头。
  2. 2. 之后每次拿走的石头数量是对方上一次拿走的数量减 1。
  3. 3. 游戏在某个玩家无法按规则拿走足够的石头时结束。
  4. 4. Alice 获胜的条件是 n 落在特定的区间(n < 1927 <= n < 3440 <= n < 4549 <= n <= 50)。
  5. 5. 代码中的数学公式通过解二次不等式直接计算出 Alice 是否能获胜。
  6. 6. 时间复杂度和空间复杂度均为 O(1)

Go完整代码如下:

.

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
package main

import (
    "fmt"
    "math"
)

func canAliceWin(n int)bool {
    x := (21 - int(math.Ceil(math.Sqrt(float64(441-n*8))))) / 2
    return x%2 > 0
}

func main() {
    n := 12
    fmt.Println(canAliceWin(n))
}

Python完整代码如下:

.

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
# -*-coding:utf-8-*-

import math

def can_alice_win(n: int) -> bool:
    x = (21 - math.ceil(math.sqrt(441 - n * 8))) // 2
    return x % 2 > 0

if __name__ == "__main__":
    n = 12
    print(can_alice_win(n))

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2025-06-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
2021-12-03:石子游戏 IV。Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。 一开始,有 n 个石子堆
2021-12-03:石子游戏 IV。Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。
福大大架构师每日一题
2021/12/09
1.2K0
2021-12-03:石子游戏 IV。Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。
一开始,有 n 个石子堆
2021-12-03:石子游戏 IV。Alice 和 Bob 两个人轮流玩一个
2021-12-03:石子游戏 IV。Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。
福大大架构师每日一题
2021/12/03
2880
2023-05-09:石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始 。 有 n 块石子排成一排。 每个玩家的回合中,可以从行中 移除 最左边的石头或
2023-05-09:石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始 。
福大大架构师每日一题
2023/05/09
5850
2023-05-09:石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始 。 有 n 块石子排成一排。 每个玩家的回合中,可以从行中 移除 最左边的石头或
2024-06-15:用go语言,Alice 和 Bob 在一个环形草地上玩一个回合制游戏。 草地上分布着一些鲜花,其中 Ali
2024-06-15:用go语言,Alice 和 Bob 在一个环形草地上玩一个回合制游戏。
福大大架构师每日一题
2024/08/16
1430
2024-06-15:用go语言,Alice 和 Bob 在一个环形草地上玩一个回合制游戏。 草地上分布着一些鲜花,其中 Ali
LeetCode每日一题06-16
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。
玛卡bug卡
2022/09/20
2650
LeetCode每日一题06-16
2025-05-14:统计能获胜的出招序列数。用go语言,Alice 和 Bob 玩一个回合制幻想战斗游戏,游戏共进行 n 轮。
2025-05-14:统计能获胜的出招序列数。用go语言,Alice 和 Bob 玩一个回合制幻想战斗游戏,游戏共进行 n 轮。每轮双方同时召唤一种魔法生物,三种生物分别是火龙(F)、水蛇(W)和地精(E)。
福大大架构师每日一题
2025/05/14
550
2025-05-14:统计能获胜的出招序列数。用go语言,Alice 和 Bob 玩一个回合制幻想战斗游戏,游戏共进行 n 轮。
2022-05-03:Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它
2022-05-03:Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ,其中 stones[i] 是第 i 个石子的价值。
福大大架构师每日一题
2022/06/04
5420
2022-05-03:Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它
2024-11-03:得到更多分数的最少关卡数目。用go语言,Alice 和 Bob 正在进行一个有 n 个关卡的游戏,其中每个
2024-11-03:得到更多分数的最少关卡数目。用go语言,Alice 和 Bob 正在进行一个有 n 个关卡的游戏,其中每个关卡要么是困难模式(possible[i] == 0),要么是简单模式(possible[i] == 1)。玩家在游戏中获得分数的规则如下:通过简单模式的关卡可得 1 分,而遇到困难模式的关卡将扣除 1 分。
福大大架构师每日一题
2024/11/04
1360
2024-11-03:得到更多分数的最少关卡数目。用go语言,Alice 和 Bob 正在进行一个有 n 个关卡的游戏,其中每个
salesforce零基础学习(七十六)顺序栈的实现以及应用
该文章介绍了如何利用C++实现一个顺序栈,包括基本操作,如压栈、出栈、查看栈顶元素、查看栈顶元素的值、查看栈的大小以及清除栈。同时,文章还介绍了如何使用该顺序栈实现四则运算。
Zero-Zhang
2018/01/05
6560
salesforce零基础学习(七十六)顺序栈的实现以及应用
2025-04-15:吃掉所有兵需要的最多移动次数。用go语言,在一个 50 x 50 的国际象棋棋盘上,有一个骑士和若干个士兵
2025-04-15:吃掉所有兵需要的最多移动次数。用go语言,在一个 50 x 50 的国际象棋棋盘上,有一个骑士和若干个士兵。假设骑士的初始位置用两个整数 kx 和 ky 表示,同时士兵的位置用二维数组 positions 表示,其中 positions[i] = [xi, yi] 表示第 i 个士兵的位置。
福大大架构师每日一题
2025/04/15
680
2025-04-15:吃掉所有兵需要的最多移动次数。用go语言,在一个 50 x 50 的国际象棋棋盘上,有一个骑士和若干个士兵
2025-05-02:找出第 K 个字符Ⅰ。用go语言,Alice 和 Bob 玩一个游戏。起初,Alice 有一个字符串,内容
2025-05-02:找出第 K 个字符Ⅰ。用go语言,Alice 和 Bob 玩一个游戏。起初,Alice 有一个字符串,内容是 "a"。
福大大架构师每日一题
2025/05/02
680
2025-05-02:找出第 K 个字符Ⅰ。用go语言,Alice 和 Bob 玩一个游戏。起初,Alice 有一个字符串,内容
编程之美----NIM游戏
: 博弈游戏·Nim游戏 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 今天我们要认识一对新朋友,Alice与Bob。 Alice与Bob总是在进行各种各样的比试,今天他们在玩一个取石子的游戏。 在这个游戏中,Alice和Bob放置了N堆不同的石子,编号1..N,第i堆中有A[i]个石子。 每一次行动,Alice和Bob可以选择从一堆石子中取出任意数量的石子。至少取1颗,至多取出这一堆剩下的所有石子。 Alice和Bob轮流行动,取走最后一个石子的人获得胜利。 假设每一轮游戏
Gxjun
2018/03/26
1.5K0
2025-03-12:使数组等于目标数组所需的最少操作次数。用go语言,给定一个正整数数组 nums,Alice 和 Bob 正
2025-03-12:使数组等于目标数组所需的最少操作次数。用go语言,给定一个正整数数组 nums,Alice 和 Bob 正在进行一场游戏。游戏规则是,Alice 可以选择数组中所有的个位数或者所有的两位数,剩下的数字则由 Bob 得到。
福大大架构师每日一题
2025/03/13
920
2025-03-12:使数组等于目标数组所需的最少操作次数。用go语言,给定一个正整数数组 nums,Alice 和 Bob 正
Codeforces Round 960 (Div. 2)
他们轮流进行运算,爱丽丝先开始。不会运算的一方将输掉比赛。一开始,变量 mx 被设置为 0 。
摆烂小白敲代码
2024/09/23
1200
Codeforces Round 960 (Div. 2)
博弈专题入门总结(Nim 巴什 SG等证明+例题)
一堆n个物品,两个人轮流从这堆物品中取物, 规定每次取[1,m]个,最后取光者得胜,问先手必胜还是后手必胜。
Here_SDUT
2022/06/29
2.2K0
博弈专题入门总结(Nim 巴什 SG等证明+例题)
笨办法学 Java(二)
你在上一个练习中已经看到了这一点,但你可以在if语句的主体中放入任何你喜欢的东西,包括其他if语句。这被称为“嵌套”,在另一个if语句内部的if语句称为“嵌套 if”。
ApacheCN_飞龙
2024/01/26
3080
2023-07-05:爱丽丝和鲍勃继续他们的石子游戏 许多堆石子 排成一行,每堆都有正整数颗石子 piles[i] 游戏以谁手中
在每个玩家的回合中,该玩家可以拿走剩下的 前 X 堆的所有石子,其中 1 <= X <= 2M
福大大架构师每日一题
2023/07/25
2640
2023-07-05:爱丽丝和鲍勃继续他们的石子游戏 许多堆石子 排成一行,每堆都有正整数颗石子 piles[i] 游戏以谁手中
挑战程序竞赛系列(52):4.2 Nim 与 Grundy 数
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/77863352
用户1147447
2019/05/26
6700
概率入门:双色球中奖、购车摇号中签和德扑同花顺,哪个更容易?
导读:排列组合是我们在这本书中接触到的第一个概率论概念,也是我们在高中学过的一个概率学的入门概念。概念记不清了也不要紧,我们回忆一下在中学学过的排列组合都有哪些经典问题来的。
IT阅读排行榜
2018/09/29
1.7K0
概率入门:双色球中奖、购车摇号中签和德扑同花顺,哪个更容易?
博弈论基础_博弈论基础罗伯特
博弈论这个环节特别好玩,游戏嘛(不会的话做题就不好玩了,当年打比赛比赛结束后两三分钟才推出来,一看答案想撕草稿纸)
全栈程序员站长
2022/11/03
7250
博弈论基础_博弈论基础罗伯特
推荐阅读
2021-12-03:石子游戏 IV。Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。 一开始,有 n 个石子堆
1.2K0
2021-12-03:石子游戏 IV。Alice 和 Bob 两个人轮流玩一个
2880
2023-05-09:石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始 。 有 n 块石子排成一排。 每个玩家的回合中,可以从行中 移除 最左边的石头或
5850
2024-06-15:用go语言,Alice 和 Bob 在一个环形草地上玩一个回合制游戏。 草地上分布着一些鲜花,其中 Ali
1430
LeetCode每日一题06-16
2650
2025-05-14:统计能获胜的出招序列数。用go语言,Alice 和 Bob 玩一个回合制幻想战斗游戏,游戏共进行 n 轮。
550
2022-05-03:Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它
5420
2024-11-03:得到更多分数的最少关卡数目。用go语言,Alice 和 Bob 正在进行一个有 n 个关卡的游戏,其中每个
1360
salesforce零基础学习(七十六)顺序栈的实现以及应用
6560
2025-04-15:吃掉所有兵需要的最多移动次数。用go语言,在一个 50 x 50 的国际象棋棋盘上,有一个骑士和若干个士兵
680
2025-05-02:找出第 K 个字符Ⅰ。用go语言,Alice 和 Bob 玩一个游戏。起初,Alice 有一个字符串,内容
680
编程之美----NIM游戏
1.5K0
2025-03-12:使数组等于目标数组所需的最少操作次数。用go语言,给定一个正整数数组 nums,Alice 和 Bob 正
920
Codeforces Round 960 (Div. 2)
1200
博弈专题入门总结(Nim 巴什 SG等证明+例题)
2.2K0
笨办法学 Java(二)
3080
2023-07-05:爱丽丝和鲍勃继续他们的石子游戏 许多堆石子 排成一行,每堆都有正整数颗石子 piles[i] 游戏以谁手中
2640
挑战程序竞赛系列(52):4.2 Nim 与 Grundy 数
6700
概率入门:双色球中奖、购车摇号中签和德扑同花顺,哪个更容易?
1.7K0
博弈论基础_博弈论基础罗伯特
7250
相关推荐
2021-12-03:石子游戏 IV。Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。 一开始,有 n 个石子堆
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验