导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-292.Nim Game

题目

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.

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.

Hint:

If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

翻译

你在与你的朋友玩Nim游戏:桌子上有一堆石子,每次你们中的一人拿走其中的1到3块。拿走最后一块石头的人将取得胜利。从你开始拿石子。
你们都很聪明,并且都会采取最优策略。编写函数,判断对于给出的石子数,你是否可以取得胜利。
例如,如果有4个石子,那么你将永远赢不了游戏:不管你拿走1、2还是3颗石子,你的朋友都将拿走最后一块。
提示:
如果有5个石子,你能够找到确保你获得胜利的方法吗?

本题主要考虑对经典的博弈论模型Nim游戏的理解,在第一次取走石子之后,将两个人各取一次作为一轮,如果要确保胜利,则每轮拿走的石子数一样,均为4即可:对方1自己3、对方2自己2、对方1自己3。所以只要第一轮可以取到石子即可保证自己最后一个拿:

1
2
3
4
5
public class Solution {
public boolean canWinNim(int n) {
return (n % 4 != 0);
}
}