此类问题的最佳方法。
首先你需要对博弈论有基本的了解。真的很基础。那就是你意识到这样一个事实，对于给定的数字 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）”不同。这里可能需要 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)。这个算法的复杂性并不明显，但我相信它是对数的。
由于它们必须精确地达到N，这只有在N是 形式时才有可能2^a * 9^b，其中之一也a, b允许为 0。
查找a及b以上：如果a + b = even，则第二个玩家获胜，否则第一个玩家获胜。
这是因为，在每一步，玩家都会接近其中一个a或b一个，因此接近a + b一个。所以问题简化为：给定k，如果每一步玩家必须从 中减去 1 k，那么哪个玩家将首先达到 0？
The optimal play will normally be to play the opposite of the opponent's move except right at the start and end.
By comparing with a recursive solution, it turns out that the answer can be computed based on the most significant digit in a base 18 representation of the number-1 as follows:
def win29(n):
if n<=9: return True
n-=1
while n>=18:
n = n//18
return n==1 or 4<=n<=8
无论只是试图满足或满足或超越N，这都可以通过确定在各种情况下总是获胜的策略来解决。我将介绍 5 个案例（或 2 个案例，其中第二个案例有 4 个子案例），涵盖所有案例N并给出每个案例的获胜策略。
考虑一下T = ceil( log(N)/log(18) )，那就是让满足或超过T的最小功率。18^TN
如果18^(T-1) * 9 < N那么第一个玩家总是输给一个理想的对手。每当第一个玩家选择 2 时，第二个玩家选择 9。每当第一个玩家选择 9 时，第二个玩家选择 2。这样，第二个玩家的回合总是以 18 的力量结束。T回合后，第二个玩家获胜。第一个玩家不能在前一轮获胜，因为乘以 9 不足以超过N（所以乘以 2 也不是）。
所以，现在让我们考虑 18^(T-1) * 9 >= N并选择最小的k这样18^(T-1) * 2^k > N。有四种可能k = 1, 2, 3, or 4。
(k = 1)第一个玩家获胜。第一个玩家可以从 2 开始，然后像上面的第二个玩家一样玩，在接下来的每一轮中与其他玩家玩相反的数字，直到下一轮。第二个玩家将始终面对初始 2 的 18 倍的幂。在 18^(T-2) * 2 时，玩家二最多可以18^(T-1)通过乘以 9 达到，这不足以获胜，并且可以在最少返回18^(T-2)*4哪个玩家可以乘以 9 获胜18^(T-1)*2。
(k = 3)第一个玩家也获胜。这一次玩家一从 9 开始并像以前一样玩。第二个玩家将始终面对初始 9 的 18 倍的幂。在 18^(T-2) * 9 时，玩家二最多可以达到18^(T-2) * 9 * 9 < 18^(T-2) * 18 * 8 = 18^(T-1) * 2^3，因此不足以获胜，并且至少可以返回 18^ (T-1) 乘以 2，哪个玩家乘以 9 并获胜。
(k = 2 or 4)第二名玩家获胜。这里第二个玩家应该像以前一样玩相反的数字，直到接近尾声，这样每一轮玩家一个以 18 的幂开始。在18^(T-2)，玩家一个最多可以达到18^(T-2)* 9 < 18^(T-1)，因此不足以获胜。如果他返回 18^(T-2)*9，则玩家二获胜，18^(T-2)*9*9 > 18^(T-2)*18*4 = 18^(T-1)*2^2如果玩家一返回18^(T-2)*2，则玩家二返回18^(T-2)*4。然后玩家一最多可以制作18^(T-2)*4*9 = 18^(T-1)*2，这仍然不够。而现在玩家一至少可以回归18^(T-2)*8，这足以让玩家二达到目标18^(T-2)*8*9 = 18^(T-1)*4。
是的，你应该考虑双方球员的最佳发挥并决定谁会赢。
在这里，一个简单的递归思维可以引导您找到解决方案。
如果玩家有号码n，n*9 >= N则当前玩家将赢得比赛。
否则，他会将2*n或9*n传给第二名玩家。2*n现在，只有当他（和9*n）提供给第二名的两个选项都导致第二名的中奖号码时，第一名才会输掉比赛，否则他将有机会再次选择中奖号码。
因此，我们可以编写如下递归方法：
因为游戏中的所有数字都将具有格式：2^i * 9^j我们可以编写：
F(i, j) = true; if (2^i * 9^j * 9) >= N
!(F(i+1, j) && F(i, j+1)); otherwise
解决方案将在 中F(0, 0)，无论第一玩家是否获胜。
如果 N 可以被 2 和 9 整除，那么会有很好的答案，并且有一些很好的博弈论方法。这是一种简单的 Javascript 动态编程方法，可以为任何可能的 N 提供答案。
function getWhoWins(n) {
if(getWhichPlayerWins(0, 1, n) === 0) {
console.log("First player wins for " + n);
} else {
console.log("Second player wins for " + n);
}
}
// Returns 0 if first, 1 if 2nd player would win
function getWhichPlayerWins(currentPlayer, currentNumber, targetNumber) {
if(currentNumber * 9 >= targetNumber) {
return currentPlayer;
}
var nextPlayer = (currentPlayer + 1) % 2;
if(getWhichPlayerWins(nextPlayer, currentNumber *2, targetNumber) === currentPlayer || getWhichPlayerWins(nextPlayer, currentNumber *9, targetNumber) === currentPlayer) {
return currentPlayer;
}
return nextPlayer;
}
该解决方案的时间复杂度为 O(2*logN) = O(logN)。
组合博弈论研究了诸如此类的两人、确定性博弈。这种无聊的博弈论与经济学中流行的更有用的诺伊曼和纳什博弈论无关。开创性的工作是一本令人愉快的书，名为 Conway、Berlekamp 和 Guy 的 Winning Ways。
想想。对于任何游戏，要么：
你的游戏是一个特例，一个不偏不倚的游戏，游戏的状态对两个玩家来说都是一样的。最好的例子是一个名为 Nim 的简单火柴游戏。碰巧所有不偏不倚的博弈都等价于 Nim（这就是 Sprague Grundy 定理），所以所有不偏不倚的博弈都可以完全解决。
让我们解决你的游戏。游戏的可能状态是正整数。我们将每个状态分类为第二个玩家获胜（我们将此类游戏标记为零“0”游戏）或第一个玩家获胜（我们将此类游戏标记为星号“*”游戏）。
大于或等于 N 的整数都是零游戏，因为此时游戏已经结束。不管是谁出手，都已经输了。
轮到的玩家可以移动到上面的零位置的状态是明星游戏。因此整数 nN/9 <= n < N都是明星游戏 - 获胜的举动是乘以 9。
轮到的玩家别无选择只能移动到明星位置的状态再次为零。所以整数 n,N/9/2 <= n < N/9是零位。我们的球员输了。
等等。使用类似的论点，我们最终将所有整数归为一。
对于 N=1000 来说，
概括我们得出彼得的结论https://stackoverflow.com/a/13367642/284795
答案（我不是 100% 确定）：
r = N mod 18
if r belongs to (1,9] player 1 wins
if r belongs to (9,18) or is =1 then player 2 wins.
我没有完整的数学演示，所以我可能是错的。
如果两个玩家（或至少其中一个）都知道如何玩，这应该是正确的答案。
我能得到这份工作吗？:)
有趣的帖子和答案。我很想提出一个理论上的蛮力函数，它使用 2/9 因子枚举所有组合路径到 N <= 2X10^12（或尽可能接近）。我说“理论上的”是因为我假设这种计算能力甚至超过了 FB？