问石头游戏-2玩家玩得很完美。

EN

我增加了第二个答案，因为我的第一个答案提供了没有优化的背景理论。但是，由于OP显然是在寻找一些优化和一个没有大量递归的非常快速的解决方案，所以我采纳了我自己的建议：

当然，真正快速的方法是做更多的数学，找出一些简单的属性，你可以检查它是胜利者还是输家。

我将使用我在这里定义的术语，所以如果这没有意义，请读这个答案！具体来说，n是一堆大小，k是要移除的石头数，n是一个胜利者，如果玩家A有一个从一堆大小n开始的获胜策略，否则它就是输家。让我们从下面的关键洞察力开始：

大多数数字都是赢家。

为什么这是真的？对于小数字来说并不明显:0是输家，1是赢家，2是输家，3是赢家，4也是，但5又是输家。但对于更大的数字，它变得更加明显。

如果某个整数p很大并且是一个失败者，那么p+1，p+2，.对于一些大小约为sqrt(p)的k_m，p+k_m都是赢家。这是因为一旦我找到一个失败者，对于任何没有太多大的堆，我可以移除几块石头，让我的对手和那个失败者在一起。关键是确定k的最大有效值是什么，因为k是以起始桩大小n而不是最终桩大小p来定义的。

因此，问题是，给定一些整数p，k的值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

因此，对于(1- sqrt(1+4p) )/2和(1+sqrt(1+4p))/2之间的k值，满足这个不等式，当然，sqrt(1+4p)至少是sqrt(5) > 2，所以左端点是负的。然后k_m = floor((1+sqrt(1+4p))/2)。

更重要的是，我声称p之后的下一个输家是数字L=p+ k_m + 1。

定理:如果p是失败者，则L=p+ k_m +1也是失败者，每一个整数p

证明：我们已经证明了区间p+1中的每一个整数n，p+k_m是胜利者，所以我们只需要证明L是失败者。

相反，假设L是胜利者。然后，存在约1 <= k <= sqrt(L)，使得L是一个失败者(根据定义)。既然我们已经证明了整数p+1，.，p+k_m是胜利者，我们就必须有L <= p，因为没有小于L的数和大于p的数都可以是输家。但这意味着L <= p+k和so k满足方程k <= sqrt(L) <= sqrt(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

QED

上面的定理给了我们一个很好的方法，因为我们现在知道胜利者落入由单个输家分开的整数区间，我们知道如何计算两个输家之间的间隔。特别是，如果p是一个失败者，那么p+ k_m +1就是一个失败者

k_m =楼层((1+sqrt(1+4p))/2)。

现在，我们可以用纯迭代的方式重写函数，这种方式应该是快速的，并且需要恒定的空间。方法是简单地计算输家的顺序，直到我们找到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);  
}

你必须从最后反复思考这场比赛:显然，要想赢，你必须拿出最后一块石头。

• 1英石:第一个玩家获胜。现在轮到A去取唯一的石头了。
• 2块石头:第二名玩家获胜。A不能拿两块石头，但必须取一块。所以A不得不拿一块石头，把另一块石头留给B去拿。
• 3块石头:第一名选手获胜。仍然没有其他选择。A不得不拿一块石头，微笑着，因为他们知道B不能用两块石头赢。
• 4块石头:第一名选手获胜。现在A可以选择留下两三块石头了。从上面的情况来看，A知道如果给三块石头，B会赢，但是如果给两块，B会输，所以A会取两块石头。
• 5块石头:第二名玩家获胜。即使A可以选择留下三块或四块石头，如果给出任何一种量，B都会赢。

正如您所看到的，您可以很容易地计算出谁将赢得一个与n的石头游戏，通过完全了解的结果与1到n-1石头游戏。

因此，算法解决方案将创建一个布尔数组wins，其中，如果玩家给定i石头将赢得游戏，则wins[i]为真。wins[0]初始化为false。然后，从一开始就通过扫描数组的可达部分来迭代填充数组的其余部分，以找出虚假条目。如果找到一个假条目，则当前条目设置为true，因为A可以使板处于B的松散状态，否则设置为false。

我将以校长的回答为基础，因为答案已经相当接近了。问题是如何有效地计算这些值。

答案是:我们不需要整个数组。只有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，它返回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;
}