【題目描述】
There are n coins in a line. Two players take turns to take one or two coins from right side until there are no more coins left. The player who take the last coin wins.
Could you please decide the?first?play will win or lose?
有?n?個硬幣排成一條線。兩個參賽者輪流從右邊依次拿走 1 或 2 個硬幣，直到?jīng)]有硬幣為止。拿到最后一枚硬幣的人獲勝。
請判定?第一個玩家?是輸還是贏？
【題目鏈接】
www.lintcode.com/en/problem/coins-in-a-line/
【題目解析】
其實此問題如果從另一個角度思考，就是從最后剩余1個或2個硬幣時進行倒推，尋找規(guī)律：
先手輸：
o o o | o o o
先手勝：
o | o o o
制勝的方法就是一定在倒數(shù)第二個回合時，讓對手面對3個硬幣，這樣因為自己可以拿1或者2個硬幣，那么無論對手選1個或者2個，己方都可以拿到最后一個硬幣。這個規(guī)律就是每次讓對手都面對3的倍數(shù)個硬幣，那么無論對方取1個或者2個，只需要取相應(yīng)的硬幣數(shù)，讓剩下的硬幣數(shù)目保持3X，這樣就能夠保證取勝。對于先手而言，如果自己第一輪面對的就是3的倍數(shù)個硬幣，那么對手則可以使用同樣的策略讓自己一方每次面對3X個硬幣。于是先手是否獲勝的唯一要素就是初始硬幣數(shù)目，在不為3的整數(shù)倍情況下，先手都可以獲勝。這樣的話，算法時間復(fù)雜度和空間復(fù)雜度都為O(1)。
【參考答案】
