Difficulty: Easy
Tags: Brainteaser
问题描述
Nim游戏的规则是：桌子上有一堆石子一共n个，你和小明轮流从石子堆中取石子，一次可以取1~3个石子。取到最后一个石子的人赢得游戏。你是先手，小明后手。当然你和小明取石子的策略都是最优的。
解决方案
这个问题的关键在于思考在石子个数在多少个的时候你会赢或者输。
当石子个数小于等于3的时候，你是必胜的；当石子个数为4的时候，你就会输了，因为不管你取几个，小明都可以取到第4个石子。
那个下一个危险的石子个数是多少呢？8, 12, 16…是4的倍数。
当石子个数为4的倍数的时候，不管你一次取几个(假设为i个)，小明都可以取j个，来使i+j=4，从而让你必输。
当石子个数不为4的倍数的时候，因为我们已经知道先手并且石子个数为4的倍数的话必输，那么你可以先取几个让石子堆的个数为4的倍数，这时候是小明取石子，可以理解为小明为『先手』而此时的石子堆个数为4的倍数，那么小明必输，你必胜。
引申一下这个游戏，当你一次最多可以取m个石子的时候，那么m+1对于你来说就是危险数字(death number)，石子个数为m+1的倍数的时候并且你先手的时候你必输。
▷ Time Complexity: O(1)
▷ Space Complexity: O(1)
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;
}
};
1 | class Solution { |