兩個人拿硬幣，哈克解決方案

有一個線N硬幣，硬幣有不同的價值觀。兩名球員輪流從隊伍的一端拿到一枚硬幣，直到沒有剩餘硬幣。擁有更多金錢的玩家獲勝。 如果n是偶數，那麼是否有任何算法可以決定第一位玩家是否會在O（1）內存和O（n）時間內獲勝或失敗？

我已經解決了動態規劃的問題，但我不知道是什麼哈克算法是。搜索後，我找到了解決辦法，從here：

def firstWillWinEven(self, values): 
    """ 
    odd_s: sum of values at odd position 
    even_s: sum of values at even position 
    if odd_s == even_s, the first mover cannot win if the other player mimics the first player 
    if odd_s > even_s, the first mover chooses the odd position values, and FORCE the other player choose the even 
    position values. The strategy and outcome are similar when even_s > odd_s. 
    """ 
    odd_s = 0 
    even_s = 0 
    for i in xrange(len(values)): 
     if i%2 == 0: 
      even_s += values[i] 
     else: 
      odd_s += values[i] 

    return odd_s != even_s

雖然我可以理解，如果odd_s != even_s的第一人將永遠是贏家，但我就是不明白odd_s == even_s situtation。 如何證明如果odd_s == even_s沒有制勝策略？

來源

2015-07-04 laike9m

解決方案不正確。如果值爲3,1,2,4，則奇數位置值的總和等於偶數位置值的總和。但是第一個人可以通過挑選4然後選擇2或3來獲勝。 – interjay

@interjay所以這意味着hacky的解決方案應該是'if odd_s！= even_s：return true'，否則回落到正常的DP？ – laike9m

也許代碼的作者想要說的是，如果'odd_s == even_s'，即第一個玩家將永遠不會丟失，即，將選擇奇數偶數枚硬幣，但不是兩者。我認爲在這種情況下，第一個球員不會有任何普遍的贏球策略。 – afenster

原來我誤解了解決方案。下面是完整的解決方案：

def firstWillWin(self, values): 
    """ 
    :param values: a list of integers 
    :return: a boolean which equals to True if the first player will win 
    """ 
    n = len(values) 
    if n%2 == 0 and self.firstWillWinEven(values): 
     return True 

    return self.firstWillWinNormalCase(values)

如果odd_s != even_s那麼第一個人將贏得肯定。如果odd_s == even_s，我們不知道誰會贏，所以回落到firstWillWinNormalCase。

來源

2015-07-04 13:13:45 laike9m

兩個人拿硬幣，哈克解決方案

回答

相關問題