LeetCode292 Nim Game

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

样例

1
2
3
For example, if there are 4 stones in the heap, then you will never win the game: 
no matter 1, 2, or 3 stones you remove, the last stone will always be removed by
your friend.

思路

给一堆石子,然后两个人轮流从堆中取走1-3个,规定取走最后一个石子的人获胜。现在给定石子的个数,问先手能否获胜。

典型的尼姆游戏,用SG函数打个表找找规律即可。可以发现当石子个数为4的倍数时,其SG函数值为0,此时先手必败。

关于NIM游戏和SG函数,可以参阅:博弈之 Nim 游戏和 sg 函数

前12个SG函数值

代码

1
2
3
4
5
6
class Solution {
public:
bool canWinNim(int n) {
return n % 4;
}
};

打表程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;

int sg[105];

int getSG(int x) {
if (sg[x] >= 0) return sg[x];
else if (x <= 0) return 0;
set<int> s;
for (int i = 1; i <= 3; ++i) s.insert(getSG(x - i));
for (int i = 0; ; ++i) if (!s.count(i)) return sg[x] = i;
}

void solve() {
memset(sg, -1, sizeof(sg));
for (int i = 0; i < 100; ++i) cout << "sg[" << i << "] = " << getSG(i) << endl;
}

int main() {
solve();
}
分享到 评论