292.Nim游戏
292.1 题目
你和你的朋友，两个人一起玩 Nim 游戏：
- 桌子上有一堆石头。
- 你们轮流进行自己的回合，你作为先手。
- 每一回合，轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false。
示例 1：
输入：n = 4
输出：false
解释：以下是可能的结果:
- 移除 1 颗石头。你的朋友移走了 3 块石头，包括最后一块。你的朋友赢了。
- 移除 2 个石子。你的朋友移走 2 块石头，包括最后一块。你的朋友赢了。
- 你移走 3 颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。
示例 2：
输入：n = 1
输出：true
示例 3：
输入：n = 2
输出：true
提示：
1 <= n <= 2^31 - 1
292.2 题解
方法一：取余法
思路
这是一道博弈论题目。关键在于分析必胜态和必败态。
必败态：无论怎么操作，对手都能赢的状态。
必胜态：存在一种操作，能让对手进入必败态。
分析：
- n=1,2,3：你拿走所有石头，必胜
- n=4：无论拿1、2、3块，对手都能拿走剩余的，你必败
- n=5,6,7：你可以拿1、2、3块，让对手面对4块，你必胜
- n=8：无论拿多少，对手都能让你面对4块，你必败
规律：n是4的倍数时必败，否则必胜。
举个例子：n=4
- 你拿1块，对手拿3块，对手赢
- 你拿2块，对手拿2块，对手赢
- 你拿3块，对手拿1块，对手赢
- 无论怎么拿都是输！
复杂度分析
- 时间复杂度：
O(1) - 空间复杂度：
O(1)
代码
// 方法一：取余法
// 如果石头数量是4的倍数，那么无论拿掉几块石头，最后都会剩下4块，对手可以根据剩下的石头数量拿掉对应的石头，最终获胜。
// 如果石头数量不是4的倍数，那么先手总是可以通过拿掉适当数量的石头，使得剩余的石头数量变成4的倍数，从而让对手面临必败局面。
static bool CanWinNim1(int n)
{
return n % 4 != 0;
}
292.3 代码
using System;
class Program
{
static void Main()
{
#region 题目
// 你和你的朋友，两个人一起玩 Nim 游戏：
// 桌子上有一堆石头。
// 你们轮流进行自己的回合， 你作为先手 。
// 每一回合，轮到的人拿掉 1 - 3 块石头。
// 拿掉最后一块石头的人就是获胜者。
// 假设你们每一步都是最优解。
// 请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
// 示例 1：
// 输入：n = 4
// 输出：false
// 解释：以下是可能的结果:
// 1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
// 2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
// 3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
// 在所有结果中，你的朋友是赢家。
// 示例 2：
// 输入：n = 1
// 输出：true
// 示例 3：
// 输入：n = 2
// 输出：true
// 提示：
// 1 <= n <= 2^31 - 1
#endregion
#region 测试
// 示例 1
int stones1 = 4;
bool result1 = CanWinNim1(stones1);
Console.WriteLine($"示例1 方法1 输出：{result1}");
// 示例 2
int stones2 = 1;
bool result2 = CanWinNim1(stones2);
Console.WriteLine($"示例2 方法1 输出：{result2}");
// 示例 3
int stones3 = 2;
bool result3 = CanWinNim1(stones3);
Console.WriteLine($"示例3 方法1 输出：{result3}");
#endregion
}
#region 答案
// 方法一：取余法
// 如果石头数量是4的倍数，那么无论拿掉几块石头，最后都会剩下4块，对手可以根据剩下的石头数量拿掉对应的石头，最终获胜。
// 如果石头数量不是4的倍数，那么先手总是可以通过拿掉适当数量的石头，使得剩余的石头数量变成4的倍数，从而让对手面临必败局面。
static bool CanWinNim1(int n)
{
return n % 4 != 0;
}
#endregion
}
292.4 运行结果
示例1 方法1 输出：False
示例2 方法1 输出：True
示例3 方法1 输出：True
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
