问2/9游戏(在Facebook接受采访)

EN

解决这类问题的最佳方法。

首先，你需要对游戏理论的有基本的理解，。很基本的。这就是你意识到的事实，对于一个给定的数字N，对于首发球员有一个获胜策略，或者对他的对手有一个制胜策略。因此，你必须假设他们都知道策略，并发挥他们所能做的最好的动作。

然后开始使用，熟悉的游戏。你在低水平上练习。你很快就会注意到，在2-9的比赛中，先发就赢了，而在10胜18负的情况下，他必须输掉.因此，您的函数已经为N<=18的情况做好了准备。

然后你开始考虑的一般获胜策略，。知道策略会给你算法。5分钟后(越快越好)，你就会明白你不能及时找到获胜的策略，因为在这种情况下并不明显。所以你决定给计算机一些基本原理，让它为你解决这个难题。你知道你会使用递归。

您试图找到递归的规则。你可能想从结尾或开始开始。我将从最后描述这个方法。

这场比赛的目标是把你的对手推到那个区域，在那里他必须给你胜利。而不是自己被逼到那个区域。从N/9到N有一个获胜的区域。如果一个人被逼在N/9/2和N/9之间打球，他一定会输。(因为他的两个动作都把他的对手推到了制胜区。)所以你写你的函数：

wins(n) {
  // returns 1, if starting player is able to reach
  // the range [n, 2*n) with his move
  if (n<=18) {
    if (n<=9)
      return 1;
    else
      return 0;
  } else {
    // I must push him to the zone between N/9/2 and N/9
    return wins(n/18);
  }

如果你到了那个地步，你就通过了。还有一些细节，比如是使用float还是int，还是使用int来整整。但总的来说，你表现出了正确的思维方式，你已经准备好面对面试官了:)

编辑：实际上，上面的代码中有一个错误。“胜利”与“能够到达范围(n,2n)”是不一样的。这里可能需要两个函数：wins(n)和reaches_slightly_above(n)__。后者将以递归方式调用，在18以下返回的值应该是不同的，类似于https://stackoverflow.com/a/13367642/772981解决方案中的值。但是，下面的解决方案和一般方法应该是可以的。

从下到上的替代方法是使用以下函数：

wins(a,n) {
  if (9*a >= n)
    // I win easily
    return 1;
  else
    // if one of my moves pushes the opponent to the zone
    // where he's not able to win, then I win!
    return !wins(2*a, n) || !wins(9*a, n);
}

如果他们要求n，则返回win(1,n)的值。这个算法的复杂性并不明显，但我相信它是对数的。

因为它们必须精确地到达N，所以只有当N为2^a * 9^b形式时才有可能，其中一个a, b也允许为0。

在上面找到a和b：如果是a + b = even，那么第二个玩家就会赢，否则第一个会赢。

这是因为，在每一步中，玩家都会一步一步地接近a或b，因此也就会一步一步地接近a + b。因此，问题归结为:给定k，如果玩家在每一步都必须从k中减去1，那么哪个玩家将首先达到0？

最佳的比赛通常是与对手的移动相反，除了在开始和结束的时候。

通过与递归解决方案的比较，可以根据数字-1的基数18表示中最重要的数字计算出答案如下：

def win29(n):
    if n<=9: return True
    n-=1
    while n>=18:
        n = n//18
    return n==1 or 4<=n<=8