2025-06-10:移除石头游戏。用go语言,Alice 和 Bob 玩一个拿石头的游戏,规则如下:
给定初始石头总数 n,如果 Alice 最终获胜,返回 true,否则返回 false。
1 <= n <= 50。
输入:n = 12。
输出:true。
解释:
Alice 第一次操作中移除 10 个石头,剩下 2 个石头给 Bob 。
Bob 无法移除 9 个石头,所以 Alice 赢下游戏。
题目来自力扣3360。
我们需要找到一个通用的方法来判断 Alice 是否能获胜。以下是游戏的步骤:
n - 10
个石头。10 - 1 = 9
个石头:n - 10 < 9
,Bob 无法拿走 9 个,直接输掉游戏,Alice 获胜。n - 10 - 9 = n - 19
个石头。9 - 1 = 8
个石头:n - 19 < 8
,Alice 无法拿走 8 个,输掉游戏,Bob 获胜。n - 19 - 8 = n - 27
个石头。8 - 1 = 7
个石头:n - 27 < 7
,Bob 无法拿走 7 个,输掉游戏,Alice 获胜。n - 27 - 7 = n - 34
个石头。游戏的关键在于:
我们需要找到 n
的临界值,使得 Alice 能够获胜。具体来说:
n - 10 < 9
(即 n < 19
),Alice 直接获胜。n - 10 - 9 < 8
(即 n < 27
),Bob 会在第二轮获胜。n - 10 - 9 - 8 < 7
(即 n < 34
),Alice 会在第三轮获胜。游戏结束的条件是:在某一轮中,剩余的石头不足以让当前玩家拿走所需的石头数量。
n - 10
。n - 10 >= 9
,即 n >= 19
。n - 19
。n - 19 >= 8
,即 n >= 27
。n - 27
。n - 27 >= 7
,即 n >= 34
。n - 34
。n - 34 >= 6
,即 n >= 40
。n - 40
。n - 40 >= 5
,即 n >= 45
。n - 45
。n - 45 >= 4
,即 n >= 49
。n - 49
。n - 49 >= 3
,即 n >= 52
。n
的最大值是 50,因此游戏最多进行到第六轮。Alice 获胜的条件是游戏在 Bob 的回合无法拿走足够的石头时结束。具体来说:
n
满足 n - 10 < 9
(n < 19
),Alice 直接获胜。n
满足 n - 19 - 8 < 7
(n < 34
)且 n >= 19
,Bob 在第三轮无法拿走 7,Alice 获胜。n
满足 n - 34 - 6 < 5
(n < 45
)且 n >= 34
,Bob 在第五轮无法拿走 5,Alice 获胜。n
满足 n - 45 - 4 < 3
(n < 52
)且 n >= 49
,Bob 在第七轮无法拿走 3,Alice 获胜。因此,Alice 获胜的 n
的范围是:
n < 19
27 <= n < 34
40 <= n < 45
49 <= n <= 50
代码中的 canAliceWin
函数使用了以下公式:
.
x := (21 - int(math.Ceil(math.Sqrt(float64(441 - n*8))))) / 2
return x%2 > 0
这个公式的推导如下:
x
,使得 n
落在 Alice 获胜的区间。n
的临界点可以通过以下不等式描述:n < 19
n >= 19
且 n - 19 < 8
(即 n < 27
)n >= 27
且 n - 27 < 7
(即 n < 34
)n
的区间是:[10, 18]
(n < 19
)[27, 33]
(n >= 27
且 n < 34
)[40, 44]
(n >= 40
且 n < 45
)[49, 50]
(n >= 49
且 n < 52
)10, 27, 40, 49
,可以表示为:10 = 10
27 = 10 + 9 + 8
40 = 10 + 9 + 8 + 7 + 6
49 = 10 + 9 + 8 + 7 + 6 + 5 + 4
S(k) = 10 + 9 + 8 + ... + (11 - k)
,其中 k
是区间编号。n
的二次不等式,从而得到 x
的表达式。O(1)
,因为公式计算是常数时间操作。O(1)
,没有使用额外空间。n
落在特定的区间(n < 19
、27 <= n < 34
、40 <= n < 45
、49 <= n <= 50
)。O(1)
。.
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))
}
.
# -*-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))