问题:
有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬币的人获胜。
请判定 第一个玩家 是输还是赢?
样例
n = 1, 返回 true.
n = 2, 返回 true.
n = 3, 返回 false.
n = 4, 返回 true.
n = 5, 返回 true.
分析:
- 隐含假设二人都是高手,都会尽可能采取最优策略让自己获胜
- 从后向前分析,即最后剩多少硬币时第一个人可以获胜?一定是3个。因此逐渐递推,只要是3个一组,对方先取,就一定获胜。
- 唯一坏的情况就是n是3的倍数。
代码:
bool firstWillWin(int n) {
// write your code here
return n%3;
}
只有一行,竟还是中等难度。