3

パズルは次のとおりです。

n 個のコインが一列に並び、コインにはさまざまな値があります。コインがなくなるまで、2 人のプレイヤーが交代で列の端からコインを 1 枚取ります。より多くのお金を持つプレイヤーが勝ちます。n が偶数の場合、最初のプレイヤーが O(1) メモリと O(n) 時間で勝つか負けるかを決定できるハッキーなアルゴリズムはありますか?

動的計画法で問題を解決しましたが、ハッキーなアルゴリズムが何であるかがわかりません。検索した後、ここから解決策を見つけました：

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でした。次の場合、勝利戦略がないことをどのように証明しodd_s == even_sますか?

4

1 に答える 1

0

解決策を誤解していたことが判明しました。完全なソリューションは次のとおりです。

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-04T13:13:45.160 に答える