leetcode292：Nim 游戏（nim-game）

[carloscn]

问题描述

你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。 你们轮流进行自己的回合， 你作为先手 。 每一回合，轮到的人拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1： 输入：n = 4 输出：false 解释：以下是可能的结果:

1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3. 你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。

在所有结果中，你的朋友是赢家。

示例 2： 输入：n = 1 输出：true

示例 3： 输入：n = 2 输出：true   提示： 1 <= n <= 231 - 1

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/nim-game

[carloscn]

问题分析

怎么能赢，永远让对方保持4的倍数。例如如下过程：

对方拿了数字之后，始终减到4个倍数，丢给对方，一直保持这个准则，就可以赢。所以直接判断就可以了。

static bool is_win(int64_t n)
{
    return n % 4 != 0;
}

[carloscn]

方法二（递归找规律）

上面的方法很难想到，我们可以使用递归帮忙找到规律。

static bool is_win_by_rec(int64_t n, bool *result)
{
    bool ret = 0;
    bool f1 = 0, f2 = 0, f3 = 0, f4 = 0;

    if (result[n] != 0) {
        return result[n] == 1;
    }
    if (n <= 3) {
        result[n] = 1;
        return true;
    }
    f1 = is_win_by_rec(n - 1, result);
    f2 = is_win_by_rec(n - 2, result);
    f3 = is_win_by_rec(n - 3, result);
    ret = !(f1 && f2 && f3);
    result[n] = ret ? true : false;

    return ret;
}

int main(void)
{
    int ret = 0;
    int64_t val = 0;
    bool rom[1000];
    bool res = 0;

    memset(rom, 0, sizeof(bool) * 1000);

    for (val = 0; val < 500; val ++) {
        res = is_win_by_rec(val, rom);
        printf("%lld -> %d\n", val, res);
    }

finish:
    return ret;
}

[carloscn]

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/common/09_nim-game_292.c

result: