D64 292. Nim Game

题目链接

292. Nim Game

题目分析

假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿 1~3 颗石头。拿到最后一颗石头的一方为剩方。第一轮由你开始捡石头。
同时假设你和你的朋友都足够聪明，每次都能采取最优策略。

现给定一个石头数量，判断你最终是否能取得胜利。

思路

我们先从少一点开始推广到 n 个石头。

如果有 1～3 颗石头，因为规定了是你开始、还假设会采取最优策略，那么你是能获胜的。也即，对方不会在拿走石头后剩下 1

假设有 4 颗石头。
你拿 1 颗，会剩下 3 颗。对方全拿，对方赢 。
你拿 2 颗，会剩下 2 颗。对方全拿，对方赢 。
你拿 3 颗，会剩下 1 颗。对方全拿，对方赢 。
即，怎么拿都是你输。

假设有 5 颗石头。
你拿 1 颗，会剩下 4 颗。
对方拿走 1 颗，剩下 3 颗给你，你全拿，你赢。
对方拿走 2 颗，剩下 2 颗给你，你全拿，你赢。
对方拿走 3 颗，剩下 1 颗给你，你全拿，你赢。
你拿 2 颗，会剩下 3 颗。对方全拿，对方赢 。
你拿 3 颗，会剩下 2 颗。对方全拿，对方赢 。
因此，这一轮你会选择拿 1 颗，剩下 4 颗。

假设有 6 颗石头。
你拿 1 颗，会剩下 5 颗。
对方拿走 1 颗，剩下 4 颗给你，参考一开始就只有 4 颗的情况，对方赢 。
对方拿走 2 颗，剩下 3 颗给你，你全拿，你赢。
对方拿走 3 颗，剩下 2 颗给你，你全拿，你赢。
你拿 2 颗，会剩下 4 颗。
对方拿走 1 颗，剩下 3 颗给你，你全拿，你赢。
对方拿走 2 颗，剩下 2 颗给你，你全拿，你赢。
对方拿走 3 颗，剩下 1 颗给你，你全拿，你赢。
你拿 3 颗，会剩下 3 颗。对方全拿，对方赢 。
因此，这一轮你会选择拿 2 颗，剩下 4 颗。

假设有 7 颗石头。
你拿 1 颗，会剩下 6 颗。
对方拿走 1 颗，剩下 5 颗给你，参考一开始就只有 5 颗的情况，你赢。
对方拿走 2 颗，剩下 4 颗给你，对方赢 。
对方拿走 3 颗，剩下 3 颗给你，你全拿，你赢。
你拿 2 颗，会剩下 5 颗。
对方拿走 1 颗，剩下 4 颗给你，对方赢 。
对方拿走 2 颗，剩下 3 颗给你，你全拿，你赢。
对方拿走 3 颗，剩下 2 颗给你，你全拿，你赢。
你拿 3 颗，会剩下 4 颗。
对方拿走 1 颗，剩下 3 颗给你，你全拿，你赢。
对方拿走 2 颗，剩下 2 颗给你，你全拿，你赢。
对方拿走 3 颗，剩下 1 颗给你，你全拿，你赢。
因此，这一轮你会选择拿 3 颗，剩下 4 颗。

假设有 8 颗石头。
你拿 1 颗，会剩下 7 颗。
对方拿走 1 颗，剩下 6 颗给你，参考一开始就只有 6 颗的情况，你赢。
对方拿走 2 颗，剩下 5 颗给你，参考一开始就只有 5 颗的情况，你赢。
对方拿走 3 颗，剩下 4 颗给你，对方赢 。
你拿 2 颗，会剩下 6 颗。
对方拿走 1 颗，剩下 5 颗给你，你赢。
对方拿走 2 颗，剩下 4 颗给你，对方赢。
对方拿走 3 颗，剩下 3 颗给你，你全拿，你赢。
你拿 3 颗，会剩下 5 颗。
对方拿走 1 颗，剩下 4 颗给你，对方赢。
对方拿走 2 颗，剩下 3 颗给你，你全拿，你赢。
对方拿走 3 颗，剩下 2 颗给你，你全拿，你赢。
因此，必输无疑。

我们可以得出规律。当剩下的石头为 4 的整数倍、双方都采取最优策略时，先下手的一方为输家。

因此这个题目就很简单了，只要判断给定的数字是否是 4 的整数倍即可。

最终代码

<?php
class Solution {

    /**
         * @param Integer $n
              * @return Boolean
                   */
                       function canWinNim($n) {return $n%4!=0;}
                                   }

                               
                               若觉得本文章对你有用，欢迎用 [爱发电](https://afdian.net/@skys215) 资助。