目录
  1. 1. Description
  2. 2. Solution
算法-尼姆游戏(吃花生米问题)

Description

尼姆游戏。有总数为n的石头,每个人可以拿1~3个石头,两个人交替拿,拿到最后一个的人获胜。究竟是先手有利,还是后手有利?

Solution

1个石子,先手全部拿走;
2个石子,先手全部拿走;
3个石子,先手全部拿走;
4个石子,后手面对的是先手的第1,2,3情况,后手必胜;
5个石子,先手拿走1个让后手面对第4种情况,后手必败;
6个石子,先手拿走2个让后手面对第4种情况,后手必败;
……
容易看出来,只有当出现了4的倍数,先手无可奈何,其余情况先手都可以获胜。

1
2
3
4
5
6
7
8
9
class Solution {
public:
bool canWinNim(int n) {
if(n % 4 == 0)
return false;
else
return true;
}
};
文章作者: 李浩
文章链接: https://leehoward.cn/2019/10/15/算法-尼姆游戏(吃花生米问题)/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 leehoward
打赏
  • 微信
  • 支付宝

评论