algorithm - 2/9 游戏(Facebook 采访)

Question

有人问我这个问题:similar question在谷歌。类似的问题在 Facebook 采访中被问到。

Determine winner of 2/9 number game

Two players play the following game: they pick a random number N (less than 2 billion) then, starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice). Whoever reaches N first wins.

The candidate should write a function that given N decides who wins (first or second player?)

将 2/9 的基本随机选择用于乘法运算，否则他们希望我们在走棋时增加智能。例如:从乘法 2 开始，只有当您看到其他人无法比您更快地达到 N 时才乘以 9？

解决此类问题的最佳方法是什么？

Answer 1

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

首先，您需要对游戏理论有基本的了解。真的很基本。也就是说，您意识到一个事实，即对于给定的数字 N，开始的玩家有一个获胜策略，或者他的对手有一个获胜策略。因此，您必须假设他们都知道该策略并发挥了他们所能发挥的最佳作用。

然后您开始熟悉游戏。你在低层次上修炼。您很快就会注意到，对于 2-9，首发者获胜，而对于 10-18，他必须输。因此，您的函数已准备好处理 N<=18 的情况。 .

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

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

游戏的目标是将你的对手推到禁区，他必须在那里给你胜利。不要自己被推到那个区域。从 N/9 到 N 有一个获胜区域。如果有人被迫从 N/9/2 和 N/9 之间下棋，他必须输。 (因为他的两个 Action 都将他的对手推向了胜利区。)所以你写下你的函数:

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)”不同。这里可能需要 2 个函数:wins(n)和 reaches_slightly_above(n) .后者将以递归方式调用，返回的值低于 18 应该是不同的，类似于 Peter de Rivaz 的解决方案中的值。 .但是下面的解决方案和一般方法应该没问题。

另一种方法，从下到上，是使用函数:

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) 的值.这个算法的复杂度并不明显，但我相信它是对数的。