我被问到这个问题:谷歌的类似问题.在Facebook采访中被问到类似的问题.
确定2/9数字游戏的赢家
两名玩家玩下面的游戏:他们选择一个随机数N(小于20亿),然后从1开始,轮流将前一轮的数字乘以2或9(他们的选择).到达N的人首先获胜.
候选人应该编写一个函数给出N判定谁获胜(第一或第二个玩家？)
2/9的基本随机选择是否可用于乘法工作,或者他们希望我们在移动中添加智能.例如:从乘以2开始,只有当你看到另一个人无法比你更快达到N时才乘以9？
处理这类问题的最佳方法是什么？
这类问题的最佳方法.
首先,您需要对游戏理论有基本的了解.真的很基本.那就是你意识到这样一个事实,即对于一个给定的数字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以上:if a + b = even,那么第二个玩家将获胜,否则第一个将获胜.
这是因为,在每一步,玩家越来越接近一个a或b一个,因此接近a + b一个.所以问题减少到:给定k,如果每个步骤一个玩家必须减去1 k,哪个玩家将首先达到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
答案（我不是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.
我没有完整的数学演示，所以我可能是错的。
如果两个玩家（或至少其中一个）都知道如何玩，这应该是正确的答案。
我能得到这份工作吗？:)