你和你的朋友,两个人一起玩 Nim 游戏:

  • 桌子上有一堆石头。
  • 你们轮流进行自己的回合, 你作为先手 。
  • 每一回合,轮到的人拿掉 1 - 3 块石头。
  • 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数,来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢,返回 true;否则,返回 false 。

输入格式

一个整数,表示石头的数量。

输出格式

一个布尔值,表示是否可以赢得游戏。

数据范围

1 <= n <= 231 - 1

输入样例:

n = 4

输出样例:

false

样例解释:

以下是可能的结果:

  1. 移除1颗石头。你的朋友移走了3块石头,包括最后一块。你的朋友赢了。
  2. 移除2个石子。你的朋友移走2块石头,包括最后一块。你的朋友赢了。 3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。 在所有结果中,你的朋友是赢家。

输入样例:

n = 1

输出样例:

true

输入样例:

n = 2

输出样例:

true

题目分析

我们可以找找规律: 对于当前局面,我们判断最优拿多少个能胜:

n   拿  剩  胜负
1   1   0   胜
2   2   0   胜
3   3   0   胜

4   不管拿(1、2、3)个,都会使对方达到上述必胜状态,对方必胜。
5   1   4   胜
6   2   4   胜
7   3   4   胜

8   不管拿(1、2、3)个,都会使对方达到上述必胜状态,对方必胜。
9   1   8   胜
10  2   8   胜
11  3   8   胜

所以, 对于当前局面,我们可以发现,只要当前石子数为 4 的倍数,那么必败。

代码实现

n MOD 4

分类: MathThought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status