超简单的博弈算法题，一行代码解决！

我就是我 2021-10-30 03:14 230阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

今天分享一道超简单的博弈题，通过找规律的方式来发现其中的奥秘，最后只需要一行代码解决。

### 题目描述 ###

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 `N` 。在每个玩家的回合，玩家需要执行以下操作：

*  选出任一 `x`，满足 `0 < x < N` 且 `N % x == 0` 。
 *  用 `N - x` 替换黑板上的数字 `N` 。

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 `True`，否则返回 `false`。假设两个玩家都以最佳状态参与游戏。

**示例 1：**

输入：2
    输出：true
    解释：爱丽丝选择 1，鲍勃无法进行操作。

**示例 2：**

输入：3
    输出：false
    解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

**提示：**

1.  `1 <= N <= 1000`

### 题目解析 ###

对于这种博弈类的题目，如果没有思路的话我们不妨多举几个例子，尝试着从中找寻规律。

*  假设 `N = 1`，爱丽丝没得选择，直接失败，即 **鲍勃获胜**；
 *  假设 `N = 2`，爱丽丝有选择，她可以选择 `x = 1`，鲍勃面对的就是 `N = 2 - 1 = 1`，无法操作，**爱丽丝获胜**；
 *  假设 `N = 3`，爱丽丝只能选择 `x = 1`，因为选 `x = 2` 不满足 `3 % 2 = 0`，鲍勃面对的就是 `N = 3 - 1 = 2`，参考上面 `N = 2` 的情形，此时鲍勃为 `N = 2` 的先手，**鲍勃获胜**；
 *  假设 `N = 4`，爱丽丝可以选择 `x = 1` 来使鲍勃遇到 `N = 3` 的情况，**爱丽丝获胜**；

貌似有个规律：N 为奇数时， **鲍勃获胜**；N 为偶数时， **爱丽丝获胜**。

是这样吗？

是的！

事实上，无论 N 为多大，最终都是在 **N = 2** 这个临界点结束的。谁最后面对的是 **N = 2** 的情形，谁就能获胜（这句话不太理解的话，仔细看看 N = 2、N = 3 这两种情形）。

接下来，我们得知道一个数学小知识：**奇数的因子（约数）只能是奇数，偶数的因子（约数）可以是奇数或偶数**。

**千万不要忽略 1 也是因子！**

爱丽丝是游戏开始时的先手。

*  当她面对的 N 为偶数时，她 **一定可以** 选到一个 N 的奇数因子 x（比如 1 ），将 N - x 这个奇数传给鲍勃；用 `N - x` 替换黑板上的数字 `N` ，鲍勃面对的就是奇数 N，只能选择 N 的奇数因子 x，`奇数 - 奇数 = 偶数`，此时传给爱丽丝的又是偶数。这样轮换下去爱丽丝会遇到 **N = 2** 的情形，然后获胜；
 *  当爱丽丝遇到的 N 是奇数时，只能传给鲍勃偶数或无法操作 (N = 1) ，无法获胜。

### 代码实现 ###

class Solution {
        public boolean divisorGame(int N) {
            return N % 2 == 0;
        }
    }

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20211029/3382464ee4b74dc7abf2d236b2f21451.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png]: /images/20211029/8e5a20588bd9408f860b3bd8c54e3b4d.png