有人问我这样一个问题：类似的问题在谷歌。类似的问题是在Facebook的采访要求。

I was asked this question: similar question at google. Similar question was asked during Facebook interview.

确定的2/9数字游戏的赢家

Determine winner of 2/9 number game

两名球员发挥以下游戏：他们选择一个随机数N（小于2十亿），然后，从1开始，轮流乘从previous又与2个或9（自己选择）的数量。   凡达到N首胜。

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.

应该写一个函数，指定N决定谁赢（第一或第二的球员？）

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

请问一个基本随机选择2/9乘法工作或他们会要我们加智力做出举动。对于前：首先乘以2和9相乘，只有当你看到其他人将无法以更快的达到ñ比你

Will a basic random choice of 2/9 for multiplication work or they'd want us to add intelligence in making moves. For ex: start with multiplication with 2 and multiply with 9 only when you see the other person will not be able to reach N quicker than you?

什么是处理这些类型的问题，最好的方法是什么？

What is the best way to approach these type of questions?

推荐答案

这类问题最好的办法。

首先，你需要有一个游戏的理论基本的了解。很基本的。这就是你意识到这样一个事实，即对于一个给定数量N有任何一个成功的策略，供玩家谁启动或一个成功的策略，他oponent。所以，你必须假定他们都知道战略，发挥最佳的移动，他们可以。

First you need to have the basic understanding of the theory of games. Really basic. That is you are conscious of the fact, that for a given number N there is either a winning strategy for player who starts or a winning strategy for his oponent. So you must assume that they both know the strategy and play the best moves they can.

然后你开始为熟悉游戏。练习在低水平。你很快发现，对于2-9的起动器取胜，而对于10-18，他一定会输。所以，你的函数准备的情况下 N'LT; = 18

Then you start to become familiar with the game. You practice on a low level. You quickly notice that for 2-9 the starter is winning, while for 10-18 he must lose. So your function is ready for a case of N<=18.

然后你开始的思维一般的制胜战略。知道了策略会给你的算法。 5分钟后（越早越好），你明白，你不适合及时找到制胜战略，因为它不是明显在这种情况下。所以你决定给电脑的一些基本原则，让它解决这一难题为您服务。你知道你将使用递归。

Then you start thinking of a general winning strategy. Knowing the strategy would give you the algorithm. After 5 minutes (the sooner the better) you understand that you won't fit in time to find the winning strategy, as it is not obvious in that case. So you decide to give the computer some basic principles and let it solve the puzzle for you. You know you'll use the recursion.

您试图找到递归规则。您可能需要从最终还是从头开始。我将描述从最终的办法。

You try to find the rule for recursion. You may want to start from the end or from the beginning. I'll describe the approach from the end.

本场比赛的目标是为把你的对手的区域，在那里，他必须给你胜利。而不是推送到该区域自己。从N / 9与N有赢得一个区域。如果一个人被压从N / 9/2和N / 9之间玩，他一定会输。 （因为无论他的动作推他的对手获胜的区域。）所以，你写你的函数：

The goal of the game is to push your opponent to the zone, where he must give you the victory. And not get pushed to that zone yourself. From N/9 to N there is a zone for winning. If one is pushed to play from between N/9/2 and N/9, he must lose. (Because both his moves push his opponent to the winning zone.) So you write your function:

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类型。但总的来说，你表现出思维的正道，你准备好去面对面试官：）

If you reached that point, you passed. There are details left, like whether to use float or int, whether to round up or down using int. But in general you showed the right way of thinking and you're ready to face the interviewer :)

修改：其实，有在code以上的错误。 胜利，是不一样的能够到达的范围内（N，2n个）。也许2功能是必需的位置：胜（N）和 reaches_slightly_above（N）。后者将被称为递归的方式，回到低于18的值应该是不同的，就像那些在彼得·德Rivaz解决方案。但是下面的解决方案和一般的做法应该没问题。的

EDIT: Actually there is a mistake in the code above. "Winning" is not the same as "being able to reach the range (n,2n)". Maybe 2 functions are necessary here: wins(n) and reaches_slightly_above(n). The latter would be called in a recursive way, and the values returned below 18 should be different, resemble the ones in the solution of Peter de Rivaz. However the solution below and the general approach should be ok.

在另一种方法，自下而上去了，将使用的功能：

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 ，返回的价值取胜（1，N）。该算法的复杂性并不明显，但我相信这是对数。

If they ask for n, you return the value of win(1,n). The complexity of this algorithm is not obvious, but I believe it's logarithmic.