石头游戏 - 2 名玩家完美玩
A stone game - 2 players play perfectly
最近学习了nim game和grundy number
我被困在一个问题上。请给我一些想法
问题：
A 和 B 用一堆石头玩游戏。 A开始游戏，他们交替着手。在每一步中，玩家必须从堆中移除至少一个且不超过 sqrt 的数字石子。因此，例如，如果一堆包含 10 颗石子，那么玩家可以从这堆中取出 1、2、3 颗石子。
A 和 B 都玩得很好。不能做出有效移动的玩家输了。现在你得到了石头的数量，你必须找到如果双方都玩得最好的玩家将会获胜。
例子
n=3 胜，
n=5乙赢
n<=10^12
我可以用Grundy number 来解决这个石头数量少的问题https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/?
grundy 函数是 g(x)，x 是剩余的石头。
呼叫 F(s) 是我们可以从 x 石头中获得的剩余石头数量的集合。
如果 s 是终端位置，则 g(s)=0
如果 s 不是终端位置，设 X = {g(t)| F(s) 中的 t}。那么，s的grundy数就是不在X中的大于等于0的最小整数。
例如 x=10 所以 F(x)={9,8,7} 取 1,2 或 3 个石头。 (平方(10)<=3)
如果 g(n)>0 => 先手赢
g(0)=0
g(1)=1
g(2)=0
g(3)=1
g(4)=2
....
但是这个算法很慢。
提前致谢。
你必须从头开始递归地思考这个游戏：显然，要赢，你必须拿走最后一块石头。
1石：先手为胜。轮到A拿唯一的石头了。
2 石子：第二位玩家获胜。 A 不能拿两块石头，但必须拿一块。于是A只好拿了一块石头，把另一块石头留给B拿。
3 石子：先手获胜。仍然别无选择。 A只得拿一子，笑了笑，因为他们知道B拿两子是赢不了的。
4 石子：先手获胜。现在 A 可以选择留下两块或三块石头。由上可知，A知道三颗棋子B赢，两颗棋子B输，所以A拿两颗棋子。
5 石子：第二位玩家获胜。即使 A 可以选择留下三或四颗棋子，但只要给定任意数量，B 都会获胜。
如您所见，您可以通过完全了解 1 到 n-1 子的游戏结果，轻松计算出谁将赢得 n 子游戏。
算法解决方案将因此创建一个布尔数组 wins，如果玩家给出 i 个棋子将赢得游戏，则 wins[i] 为真。 wins[0] 被初始化为 false。然后通过扫描数组的可到达部分以查找错误条目，从头开始迭代填充数组的其余部分。如果发现错误的条目，则当前条目设置为真，因为A可以让B处于松散状态，否则设置为假。
像这样的游戏（Towers of Hanoi 是另一个经典例子）旨在说明归纳和递归的数学原理，其中递归在编程中尤为重要。
我们要判断一堆 n 子是赢还是输。直觉上，获胜的一堆是这样的，无论你的对手做出什么样的选择，你总能拿走一定数量的石头来保证你会赢。同样，失败的一堆是这样的，无论你做出什么选择，你总是给你的对手留下一个获胜的策略。
显然，n = 0是一个失败的堆；你已经输了。而 n = 1 是一个获胜的筹码，因为你拿走了一个石头并离开了你的对手 n=0。 n=2呢？好吧，你只能拿一块石头，此时你已经给了你的对手一个胜利堆（n=1），所以n=2 是一个失败的数字。我们可以使这个在数学上更精确。
Definition: An integer n is a loser if n=0 or for every integer k between 1 and sqrt(n), n-k is a winner. An integer n is a winner if there exists some integer k between 1 and sqrt(n) such that n-k is a loser.
在这个定义中，n是堆的大小，k是你选择拿的石子数。如果每移除一个有效数量的石子都会给你的对手一个获胜的一堆，那么一堆就是失败的一堆，而获胜的一堆是 一些 选择给你的对手失败的一堆。
当然，这个定义应该会让你有点不安，因为我们实际上不知道除了 n=0,1,2 之外它是否有意义已经检查过了。也许某个数字符合赢家 和输家 的定义，或者两者都不符合。这肯定会令人困惑。这就是归纳法的用武之地。
Theorem: Every nonnegative integer is either a winner or a loser, but not both.
证明： 我们将使用Strong or Complete Induction的原理。我们知道 n=0 是输家（根据定义）并且我们已经证明 n=1 是赢家并且 n=2直接输了。这些是我们的基本案例。
现在让我们考虑一些整数 n_0 > 2 我们假设（使用强归纳法）每个小于 [= 的非负整数136=]要么是赢家要么是输家，但不是两者都是。让 s = floor(sqrt(n_0)) 并考虑整数集 P = {n_0-s, n_0-s+1, ..., n_0 - 1}。 （因为 {1, 2, ..., s} 是要移除的石子的可能选择集合，P 是石堆的集合我可以离开我的对手。）通过强归纳法，因为 P 中的每个值都是小于 n_0 的非负整数，每个他们要么是赢家要么是输家（但不是两者都是）。如果 any 中的值 P 是输家，那么根据定义，n_0 是输家获胜者（因为你移除了足够多的石头让你的对手失去了一堆）。如果不是，则 P 中的每个 值都是赢家，因此 n_0 是失败者（因为无论你拿了多少石子，你的对手仍然有一堆获胜的棋子）。因此，n_0要么是赢家，要么是输家，但不能两者兼而有之。
通过强归纳法，我们得出结论，每个非负整数要么是赢家，要么是输家，但不是两者都是。
QED
好的，如果您熟悉归纳法，那将非常简单。但我们所展示的是，我们非常直观的定义实际上是有道理的，你得到的每一堆要么是赢家（如果你玩得对）要么是输家（如果你的对手玩得对）。我们如何确定哪个是哪个？
好吧，归纳法直接导致递归。让我们为我们的两个定义编写递归函数：n 是赢家还是输家？这是一些没有错误检查的类似 C 的伪代码。
bool is_winner(int n) {
// check all valid numbers of stones to remove (k)
for (int k = 1; k <= sqrt(n); k++) {
if (is_loser(n-k)) {
// I can force the loser n-k on my opponent, so n is a winner
return true;
}
}
// I didn't find a way to force a loser on my opponent, so this must be a loser.
return false;
}
bool is_loser(int n) {
if (n == 0) { // this is our base case
return true;
}
for (int k = 1; k <= sqrt(n); k++) {
if (!is_winner(n-k)) {
// we found a way to give them a pile that ISN'T a winner, so this isn't a loser
return false;
}
}
// Nope: every pile we can give our opponent is a winner, so this pile is a loser
return true;
}
当然，上面的代码有些多余，因为我们已经表明每个数字要么是赢家，要么是输家。因此，将 is_loser 实现为仅返回 !is_winner 更有意义，反之亦然。也许我们会 is_winner 作为一个独立的实现。
bool is_winner(int n) {
if (n < 0) {
// raise error
} else if (n == 0) {
return false; // 0 is a loser
} else {
for (int k = 1; k <= sqrt(n); k++) {
if (!is_winner(n-k)) {
// we can give opponent a loser, this is a winner
return true;
}
}
// all choices give our opponent a winner, this is a loser
return false;
}
}
要用这个函数来回答问题，如果游戏开始时有 n 个石子，玩家 A 先走，双方都玩得最好，玩家 A 获胜，如果 is_winner(n) 如果 !is_winner(n) 则玩家 B 获胜。要弄清楚他们的玩法应该是什么，如果你有赢牌，你应该选择一些有效的 k 这样 n-k 是输家（它哪个无关紧要，但最大的价值将使游戏结束得最快）如果给你一堆失败的东西，你选择什么并不重要——这就是失败者的意义，但同样，选择k的最大值会使游戏结束得更快
None这个还真是考虑性能了。由于 n 可能非常大，因此您可以考虑很多事情。例如，至少在单个递归调用中预先计算您要考虑的 n 的常见小值，或使用 Memoization。此外，正如我之前建议的那样，删除 k 的最大值以更少的回合结束游戏。同样，如果你反转循环并首先检查 k 的最大允许值，你应该能够减少递归调用的次数。
当然，真正快速的方法是做更多的数学运算并找出 n 的一些简单属性，你可以检查它是否是赢家或输家。
我将以 cmaster 的回答为基础，因为它已经非常接近了。问题是如何有效地计算这些值。
答案是：我们不需要整个数组。只有 false 值很有趣。让我们来分析一下：
如果我们在数组中有一个 false 值，那么接下来的几项将是 true 因为它们可以移除石头，这样其他玩家就会落在 false价值。问题是：会有多少 true 个条目？
如果我们位于 false 条目 z，则条目 x 将是 true 条目（如果 x - sqrt(x) <= z）。我们可以解决 x 并得到：
x <= 1/2 * (1 + 2 * z + sqrt(1 + 4 * z))
这是最后一个 true 条目。例如。对于 z = 2，这个 returns 4。下一个条目将是错误的，因为玩家只能移除石头，这样对手将在 true 个条目出现。
知道了这一点，我们的算法就差不多完成了。从已知的 false 值开始（例如 0）。然后，迭代移动到下一个 false 值，直到达到 n.
bool isWinner(long long n)
{
double loser = 0;
while(n > loser)
loser = floor(0.5 * (1 + 2 * loser + sqrt(1 + 4 * loser))) + 1;
return n != loser;
}
我添加第二个答案是因为我的第一个答案提供了没有优化的背景理论。但是由于 OP 显然正在寻找一些优化和非常快速的解决方案而无需大量递归，我采纳了自己的建议：
Of course, the really fast way to do this is to do some more math and figure out some simple properties of n you can check that will determine whether or not it is a winner or a loser.
我将使用我在此处定义的术语，所以如果这没有意义，请阅读该答案！具体来说，n是堆的大小，k是要移除的石子数量，n是如果玩家 A 从一堆大小 n 开始有获胜策略，则获胜，否则为失败。让我们从以下关键见解开始：
Most numbers are winners.
为什么是这样？对于小数字并不明显：0 是输家，1 是赢家，2 是输家，3 是赢家，4 也是，但 5 又是输家。但是对于更大的数字，它变得更加明显。
如果某个整数 p 很大并且是输家那么 p+1, p+2, ... p+k_m 都是一些 k_m 的赢家，其大小约为 sqrt(p)。这是因为一旦我找到一个失败者，对于任何比这个大不了太多的堆，我都可以移除一些石头让我的对手留下那个失败者。关键是确定 k 的最大有效值是多少，因为 k 是根据起始堆大小 定义的n 而不是最终的堆大小 p.
所以问题就变成了，给定一些整数 p，k 的值是 k <= sqrt(n) 其中 n = p+k。换句话说，给定 p，什么起始堆大小 n 允许我删除 k 并留下我的对手有 p。好吧，因为 n = p+k 并且值都是非负的，我们必须有
k <= sqrt(n) = sqrt(p+k) ==> k^2 <= p + k ==> k^2 - k - p <= 0.
这是k中的二次方程，对于p的任何固定值。可以使用二次公式找到解集的端点：
k = (1 +- sqrt(1 + 4p))/2
因此，不等式满足 k 在 (1-sqrt(1+4p))/2 和 (1+sqrt(1+4p))/ 之间的值2.当然，sqrt(1+4p)至少是sqrt(5) > 2，所以左端点为负。那么 k_m = floor((1+sqrt(1+4p))/2).
更重要的是，我声称 p 之后的下一个失败者是数字 L = p + k_m + 1 .让我们尝试证明这一点：
Theorem: If p is a loser, then L = p + k_m + 1 is also a loser and every integer p < n < L is a winner.
证明： 我们已经证明了区间[p+1, p+[中的每个整数n =156=]]是赢家，那么我们只需要证明L是输家即可。
相反，假设 L 是赢家。然后存在一些 1 <= k <= sqrt(L) 这样 L - k 是一个失败者（根据定义）。因为我们已经证明整数 p+1, ..., p+k_m 是赢家，所以我们必须有 L - k <= p 因为没有小于 L 和大于 p 的数字可以输。但这意味着 L <= p + k 等 k 满足等式 k <= sqrt(L) <=平方根（p + k）。我们已经证明方程 k <= sqrt(p + k) 的解不大于 (1+sqrt(1+4p))/2，所以任何整数解都必须满足k <= k_m。但是 L - k = p + k_m + 1 - k >= p + k_m + 1 - k_m = p + 1。这是一个矛盾，因为 p < L - k < L 并且我们已经证明不存在大于 p 且小于 L.
QED
上面的定理给了我们一个很好的方法，因为我们现在知道赢家落入由一个输家隔开的整数区间，并且我们知道如何计算两个输家之间的区间。特别地，如果 p 是输家，那么 p + k_m + 1 是输家，其中
k_m = floor((1+sqrt(1+4p))/2).
现在我们可以以纯迭代的方式重写函数，这种方式应该很快并且需要常数 space。该方法只是简单地计算失败者的序列，直到我们找到 n（在这种情况下它是失败者）或确定 n 位于两个失败者之间的间隔。
bool is_winner(int n) {
int p = 0;
// loop through losers until we find one at least as large as n
while (p < n) {
int km = floor((1+sqrt(1+4p))/2);
p = p + km + 1;
}
/* if we skipped n while computing losers,
* it is a winner that lies in the interval
* between two losers. So n is a winner as
* long as it isn't equal to p.*/
return (p != n);
}
public class Solution {
public boolean canWinNim(int n) {
if(n % 4 == 0)
{
return false;
}
else
{
return true;
}
}
}
最近学习了nim game和grundy number 我被困在一个问题上。请给我一些想法
问题： A 和 B 用一堆石头玩游戏。 A开始游戏，他们交替着手。在每一步中，玩家必须从堆中移除至少一个且不超过 sqrt 的数字石子。因此，例如，如果一堆包含 10 颗石子，那么玩家可以从这堆中取出 1、2、3 颗石子。 A 和 B 都玩得很好。不能做出有效移动的玩家输了。现在你得到了石头的数量，你必须找到如果双方都玩得最好的玩家将会获胜。 例子
n=3 胜，
n=5乙赢
n<=10^12
我可以用Grundy number 来解决这个石头数量少的问题https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/?
grundy 函数是 g(x)，x 是剩余的石头。 呼叫 F(s) 是我们可以从 x 石头中获得的剩余石头数量的集合。 如果 s 是终端位置，则 g(s)=0
如果 s 不是终端位置，设 X = {g(t)| F(s) 中的 t}。那么，s的grundy数就是不在X中的大于等于0的最小整数。
例如 x=10 所以 F(x)={9,8,7} 取 1,2 或 3 个石头。 (平方(10)<=3)
如果 g(n)>0 => 先手赢
g(0)=0
g(1)=1
g(2)=0
g(3)=1
g(4)=2 ....
但是这个算法很慢。
提前致谢。
你必须从头开始递归地思考这个游戏：显然，要赢，你必须拿走最后一块石头。
1石：先手为胜。轮到A拿唯一的石头了。
2 石子：第二位玩家获胜。 A 不能拿两块石头，但必须拿一块。于是A只好拿了一块石头，把另一块石头留给B拿。
3 石子：先手获胜。仍然别无选择。 A只得拿一子，笑了笑，因为他们知道B拿两子是赢不了的。
4 石子：先手获胜。现在 A 可以选择留下两块或三块石头。由上可知，A知道三颗棋子B赢，两颗棋子B输，所以A拿两颗棋子。
5 石子：第二位玩家获胜。即使 A 可以选择留下三或四颗棋子，但只要给定任意数量，B 都会获胜。
如您所见，您可以通过完全了解 1 到 n-1 子的游戏结果，轻松计算出谁将赢得 n 子游戏。
算法解决方案将因此创建一个布尔数组 wins，如果玩家给出 i 个棋子将赢得游戏，则 wins[i] 为真。 wins[0] 被初始化为 false。然后通过扫描数组的可到达部分以查找错误条目，从头开始迭代填充数组的其余部分。如果发现错误的条目，则当前条目设置为真，因为A可以让B处于松散状态，否则设置为假。
像这样的游戏（Towers of Hanoi 是另一个经典例子）旨在说明归纳和递归的数学原理，其中递归在编程中尤为重要。
我们要判断一堆 n 子是赢还是输。直觉上，获胜的一堆是这样的，无论你的对手做出什么样的选择，你总能拿走一定数量的石头来保证你会赢。同样，失败的一堆是这样的，无论你做出什么选择，你总是给你的对手留下一个获胜的策略。
显然，n = 0是一个失败的堆；你已经输了。而 n = 1 是一个获胜的筹码，因为你拿走了一个石头并离开了你的对手 n=0。 n=2呢？好吧，你只能拿一块石头，此时你已经给了你的对手一个胜利堆（n=1），所以n=2 是一个失败的数字。我们可以使这个在数学上更精确。
Definition: An integer n is a loser if n=0 or for every integer k between 1 and sqrt(n), n-k is a winner. An integer n is a winner if there exists some integer k between 1 and sqrt(n) such that n-k is a loser.
在这个定义中，n是堆的大小，k是你选择拿的石子数。如果每移除一个有效数量的石子都会给你的对手一个获胜的一堆，那么一堆就是失败的一堆，而获胜的一堆是 一些 选择给你的对手失败的一堆。
当然，这个定义应该会让你有点不安，因为我们实际上不知道除了 n=0,1,2 之外它是否有意义已经检查过了。也许某个数字符合赢家 和输家 的定义，或者两者都不符合。这肯定会令人困惑。这就是归纳法的用武之地。
Theorem: Every nonnegative integer is either a winner or a loser, but not both.
证明： 我们将使用Strong or Complete Induction的原理。我们知道 n=0 是输家（根据定义）并且我们已经证明 n=1 是赢家并且 n=2直接输了。这些是我们的基本案例。
现在让我们考虑一些整数 n_0 > 2 我们假设（使用强归纳法）每个小于 [= 的非负整数136=]要么是赢家要么是输家，但不是两者都是。让 s = floor(sqrt(n_0)) 并考虑整数集 P = {n_0-s, n_0-s+1, ..., n_0 - 1}。 （因为 {1, 2, ..., s} 是要移除的石子的可能选择集合，P 是石堆的集合我可以离开我的对手。）通过强归纳法，因为 P 中的每个值都是小于 n_0 的非负整数，每个他们要么是赢家要么是输家（但不是两者都是）。如果 any 中的值 P 是输家，那么根据定义，n_0 是输家获胜者（因为你移除了足够多的石头让你的对手失去了一堆）。如果不是，则 P 中的每个 值都是赢家，因此 n_0 是失败者（因为无论你拿了多少石子，你的对手仍然有一堆获胜的棋子）。因此，n_0要么是赢家，要么是输家，但不能两者兼而有之。
通过强归纳法，我们得出结论，每个非负整数要么是赢家，要么是输家，但不是两者都是。
QED
好的，如果您熟悉归纳法，那将非常简单。但我们所展示的是，我们非常直观的定义实际上是有道理的，你得到的每一堆要么是赢家（如果你玩得对）要么是输家（如果你的对手玩得对）。我们如何确定哪个是哪个？
好吧，归纳法直接导致递归。让我们为我们的两个定义编写递归函数：n 是赢家还是输家？这是一些没有错误检查的类似 C 的伪代码。
bool is_winner(int n) {
// check all valid numbers of stones to remove (k)
for (int k = 1; k <= sqrt(n); k++) {
if (is_loser(n-k)) {
// I can force the loser n-k on my opponent, so n is a winner
return true;
}
}
// I didn't find a way to force a loser on my opponent, so this must be a loser.
return false;
}
bool is_loser(int n) {
if (n == 0) { // this is our base case
return true;
}
for (int k = 1; k <= sqrt(n); k++) {
if (!is_winner(n-k)) {
// we found a way to give them a pile that ISN'T a winner, so this isn't a loser
return false;
}
}
// Nope: every pile we can give our opponent is a winner, so this pile is a loser
return true;
}
当然，上面的代码有些多余，因为我们已经表明每个数字要么是赢家，要么是输家。因此，将 is_loser 实现为仅返回 !is_winner 更有意义，反之亦然。也许我们会 is_winner 作为一个独立的实现。
bool is_winner(int n) {
if (n < 0) {
// raise error
} else if (n == 0) {
return false; // 0 is a loser
} else {
for (int k = 1; k <= sqrt(n); k++) {
if (!is_winner(n-k)) {
// we can give opponent a loser, this is a winner
return true;
}
}
// all choices give our opponent a winner, this is a loser
return false;
}
}
要用这个函数来回答问题，如果游戏开始时有 n 个石子，玩家 A 先走，双方都玩得最好，玩家 A 获胜，如果 is_winner(n) 如果 !is_winner(n) 则玩家 B 获胜。要弄清楚他们的玩法应该是什么，如果你有赢牌，你应该选择一些有效的 k 这样 n-k 是输家（它哪个无关紧要，但最大的价值将使游戏结束得最快）如果给你一堆失败的东西，你选择什么并不重要——这就是失败者的意义，但同样，选择k的最大值会使游戏结束得更快
None这个还真是考虑性能了。由于 n 可能非常大，因此您可以考虑很多事情。例如，至少在单个递归调用中预先计算您要考虑的 n 的常见小值，或使用 Memoization。此外，正如我之前建议的那样，删除 k 的最大值以更少的回合结束游戏。同样，如果你反转循环并首先检查 k 的最大允许值，你应该能够减少递归调用的次数。
当然，真正快速的方法是做更多的数学运算并找出 n 的一些简单属性，你可以检查它是否是赢家或输家。
我将以 cmaster 的回答为基础，因为它已经非常接近了。问题是如何有效地计算这些值。
答案是：我们不需要整个数组。只有 false 值很有趣。让我们来分析一下：
如果我们在数组中有一个 false 值，那么接下来的几项将是 true 因为它们可以移除石头，这样其他玩家就会落在 false价值。问题是：会有多少 true 个条目？
如果我们位于 false 条目 z，则条目 x 将是 true 条目（如果 x - sqrt(x) <= z）。我们可以解决 x 并得到：
x <= 1/2 * (1 + 2 * z + sqrt(1 + 4 * z))
这是最后一个 true 条目。例如。对于 z = 2，这个 returns 4。下一个条目将是错误的，因为玩家只能移除石头，这样对手将在 true 个条目出现。
知道了这一点，我们的算法就差不多完成了。从已知的 false 值开始（例如 0）。然后，迭代移动到下一个 false 值，直到达到 n.
bool isWinner(long long n)
{
double loser = 0;
while(n > loser)
loser = floor(0.5 * (1 + 2 * loser + sqrt(1 + 4 * loser))) + 1;
return n != loser;
}
我添加第二个答案是因为我的第一个答案提供了没有优化的背景理论。但是由于 OP 显然正在寻找一些优化和非常快速的解决方案而无需大量递归，我采纳了自己的建议：
Of course, the really fast way to do this is to do some more math and figure out some simple properties of n you can check that will determine whether or not it is a winner or a loser.
我将使用我在此处定义的术语，所以如果这没有意义，请阅读该答案！具体来说，n是堆的大小，k是要移除的石子数量，n是如果玩家 A 从一堆大小 n 开始有获胜策略，则获胜，否则为失败。让我们从以下关键见解开始：
Most numbers are winners.
为什么是这样？对于小数字并不明显：0 是输家，1 是赢家，2 是输家，3 是赢家，4 也是，但 5 又是输家。但是对于更大的数字，它变得更加明显。
如果某个整数 p 很大并且是输家那么 p+1, p+2, ... p+k_m 都是一些 k_m 的赢家，其大小约为 sqrt(p)。这是因为一旦我找到一个失败者，对于任何比这个大不了太多的堆，我都可以移除一些石头让我的对手留下那个失败者。关键是确定 k 的最大有效值是多少，因为 k 是根据起始堆大小 定义的n 而不是最终的堆大小 p.
所以问题就变成了，给定一些整数 p，k 的值是 k <= sqrt(n) 其中 n = p+k。换句话说，给定 p，什么起始堆大小 n 允许我删除 k 并留下我的对手有 p。好吧，因为 n = p+k 并且值都是非负的，我们必须有
k <= sqrt(n) = sqrt(p+k) ==> k^2 <= p + k ==> k^2 - k - p <= 0.
这是k中的二次方程，对于p的任何固定值。可以使用二次公式找到解集的端点：
k = (1 +- sqrt(1 + 4p))/2
因此，不等式满足 k 在 (1-sqrt(1+4p))/2 和 (1+sqrt(1+4p))/ 之间的值2.当然，sqrt(1+4p)至少是sqrt(5) > 2，所以左端点为负。那么 k_m = floor((1+sqrt(1+4p))/2).
更重要的是，我声称 p 之后的下一个失败者是数字 L = p + k_m + 1 .让我们尝试证明这一点：
Theorem: If p is a loser, then L = p + k_m + 1 is also a loser and every integer p < n < L is a winner.
证明： 我们已经证明了区间[p+1, p+[中的每个整数n =156=]]是赢家，那么我们只需要证明L是输家即可。
相反，假设 L 是赢家。然后存在一些 1 <= k <= sqrt(L) 这样 L - k 是一个失败者（根据定义）。因为我们已经证明整数 p+1, ..., p+k_m 是赢家，所以我们必须有 L - k <= p 因为没有小于 L 和大于 p 的数字可以输。但这意味着 L <= p + k 等 k 满足等式 k <= sqrt(L) <=平方根（p + k）。我们已经证明方程 k <= sqrt(p + k) 的解不大于 (1+sqrt(1+4p))/2，所以任何整数解都必须满足k <= k_m。但是 L - k = p + k_m + 1 - k >= p + k_m + 1 - k_m = p + 1。这是一个矛盾，因为 p < L - k < L 并且我们已经证明不存在大于 p 且小于 L.
QED
上面的定理给了我们一个很好的方法，因为我们现在知道赢家落入由一个输家隔开的整数区间，并且我们知道如何计算两个输家之间的区间。特别地，如果 p 是输家，那么 p + k_m + 1 是输家，其中
k_m = floor((1+sqrt(1+4p))/2).
现在我们可以以纯迭代的方式重写函数，这种方式应该很快并且需要常数 space。该方法只是简单地计算失败者的序列，直到我们找到 n（在这种情况下它是失败者）或确定 n 位于两个失败者之间的间隔。
bool is_winner(int n) {
int p = 0;
// loop through losers until we find one at least as large as n
while (p < n) {
int km = floor((1+sqrt(1+4p))/2);
p = p + km + 1;
}
/* if we skipped n while computing losers,
* it is a winner that lies in the interval
* between two losers. So n is a winner as
* long as it isn't equal to p.*/
return (p != n);
}
public class Solution {
public boolean canWinNim(int n) {
if(n % 4 == 0)
{
return false;
}
else
{
return true;
}
}
}