题目描述
- 两个人一起玩 Nim 游戏：
- 桌子上有一堆石头。你们轮流进行自己的回合， 你作为先手。
- 每一回合，轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。
- 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。
- 如果可以赢，返回 true；否则，返回 false。
example
input : n = 4
output : false
note : 1. 你移除1颗石头；你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 你移除2颗石头；你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3. 你移走3颗石头；你的朋友移走了最后一块石头。你的朋友赢了。
=> 在所有结果中，你的朋友是赢家。
input : n = 1
output : true
note : 你移除1颗石头。你赢了。
input : n = 2
output : true
note : 你移除2个石头。你赢了。解题思路
- 逐步增加石头数量来做分析
- 明确条件：你作为先手，你们每一步都是最优解（对于自己来说是最优解，目的是让对方输掉游戏）
- 1、石头数量在[1,3]之间，你可以直接取走所有的石头，你胜定。
- 2、石头数量恰好为 4 颗，参考 example 中的第一个例子，不论你取走几颗（1~3颗），按对自身最优解的原则，对手肯定会取走剩下的所有石头，对手胜定；
- 同理，反过来思考，如果轮到对手时，只剩4颗石头，那不论对手取走几颗，按对自身最优解的原则，你肯定会取走剩下所有的石头，你胜定。
- 3、石头数量在[5,7]之间，你如果想取胜，参考上一条的思路，就要保证让对手面临4颗石头（如，5颗的时候你取走1颗，7颗的时候你取走3颗）你胜定
- 4、石头数量恰好为 8 颗，参考上述分析1和分析2，不论你取走几颗（1~3颗），剩下的石头数量必然大于4，按对自身最优解的原则，对手只需要且肯定会让你下一次取的时候面对4颗石头，对手胜定。
- 5、拓展到[9,+∞)范围中，参考上述分析 1 — 4
- 只要轮到你取的时候，面临的是 4的倍数 颗石头，不论你取几颗，按对自身最优解的原则，对手只需要让你接下来每一次都继续面临 4 或 4的倍数颗石头，对手胜定。
- 反之，只要你能让对方先面临 4的倍数 颗石头，你胜定。
- 总结：在你先手的情况下，
- 如果游戏开始的时候是 4 或 4的倍数 颗石头，不论你怎么取，输定。
- 如果游戏开始的时候不是 4 或 4的倍数 颗石头，一定可以做到在你取了之后，马上让对手面对 4 或 4 的倍数颗石头，胜定。
代码（Java）
public class Solution {
public boolean canWinNim(int n) {
// 代码只需要判断先手面对的石头数，是不是4的倍数就好了。
// 不是则返回 true，是则返回 false。
return (n % 4) != 0;
}
}
本文作者：
whtli
本文链接： https://hexo.whtli.cn/archives/5b7d327e.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
本文链接： https://hexo.whtli.cn/archives/5b7d327e.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。