nim-游戏
Tips
题目
你和你的朋友, 两个人一起玩 Nim:
- 桌子上有一堆石头.
- 你们轮流进行自己的回合, 你作为先手.
- 每一回合, 轮到的人拿掉 1 - 3 块石头.
- 拿掉最后一块石头的人就是获胜者.
假设你们每一步都是最优解. 请编写一个函数, 来判断你是否可以在给定石头数量为 n 的情况下赢得游戏. 如果可以赢, 返回 true; 否则, 返回 false.
提示:
1 <= n <= 2³¹ - 1
示例
输入: n = 4
输出: false
解释: 以下是可能的结果:
1. 移除1颗石头. 你的朋友移走了3块石头, 包括最后一块. 你的朋友赢了.
2. 移除2个石子. 你的朋友移走2块石头, 包括最后一块. 你的朋友赢了.
3.你移走3颗石子. 你的朋友移走了最后一块石头. 你的朋友赢了.
在所有结果中, 你的朋友是赢家.
输入: n = 1
输出: true
输入: n = 2
输出: true
题解
这道题可以使用博弈论的知识来解决.
- 当石头数量
n小于等于3时, 先手可以一次性拿走所有石头, 因此先手必胜. - 当石头数量
n等于4时, 无论先手拿走多少石头, 后手都可以拿走剩余的石头, 因此先手必败. - 当石头数量
n大于4时, 如果n不是4的倍数, 那么先手可以通过拿走一定数量的石头, 使得剩余的石头数量是4的倍数, 从而让后手必败. - 如果
n是4的倍数, 那么无论先手拿走多少石头, 后手都可以拿走一定数量的石头, 使得剩余的石头数量仍然是4的倍数, 最终先手必败.
因此, 当 n 不是 4 的倍数时, 先手必胜; 当 n 是 4 的倍数时, 先手必败.
/**
* @param {number} n
* @return {boolean}
*/
var canWinNim = function (n) {
return n % 4 !== 0
}