我正在尝试解决Hackerrank挑战石头游戏,以下是(缩短的)问题陈述。
我想出了以下解决方案:
# The lines below are for the Hackerrank submission
# T = int(raw_input().strip())
# ns = [int(raw_input().strip()) for _ in range(T)]
T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]
legal_moves = [2, 3, 5]
def which_player_wins(n):
if n <= 1:
return "Second" # First player loses
elif n in legal_moves:
return "First" # First player wins immediately
else:
next_ns = map(lambda x: n - x, legal_moves)
next_ns = filter(lambda x: x >= 0, next_ns)
next_n_rewards = map(which_player_wins, next_ns) # Reward for opponent
if any(map(lambda x: x=="Second", next_n_rewards)): # Opponent enters a losing position
return "First"
else:
return "Second"
for n in ns:
print which_player_wins(n)
这个算法本质上是极小化极大算法,因为它会向前看一步,然后递归调用同一个函数。问题在于,在Hackerrank中,由于超时而终止:
事实上,我注意到评估which_player_wins(40)
已经需要约2秒钟。有没有更快的解决方案,不会超时?