除数博弈

算法

Posted by CH on May 16, 2020

题目

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

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

选出任一 x,满足 0 < x < N 且 N % x == 0 。 用 N - x 替换黑板上的数字 N 。 如果玩家无法执行这些操作,就会输掉游戏。

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

题干

选出x比N小并且可以被x整除

再把N-x作为开局

都以最佳状态参与游戏- 即 每次选择都是以对自己最有利的进行

思路

数学逻辑

首页从逻辑角度来看 每个玩家如何保证自己赢面最大

涉及到整除 就有奇数和偶数之分

如果N为奇数 只有奇数可以整除奇数 奇数-奇数=偶数 那么给下一个玩家的数必为偶数

如果N为偶数 能被偶数整除 也能被奇数整除

如果选了偶数 偶数-偶数必为偶数 那么给下一个玩家的数必为偶数

如果选了奇数 偶数-奇数必为奇数 那么给下一个玩家的数必为奇数

那到底选哪种才是最有利的 我们来想想最终什么情况会输掉游戏

已知N为递减的 会无限趋向为1 当有一方拿到1时另一方无法做下去 拿到1的一方获胜

那如何拿到1呢 根据我们上面的推论 接收到的为奇数方有可能拿到同为奇数的1

所以爱丽丝如果是偶数开局 选取奇数 让鲍勃只能给它返回偶数 就能保证这个偶数无限趋向于2

再选择1爱丽丝就可以稳操胜券

如果爱丽丝是奇数开局 那么就不太妙了 它只能返回偶数给鲍勃 鲍勃同样可以利用这个规律

只返回奇数给爱丽丝 让其返回偶数给鲍勃 同样可以稳操胜券

所以这个题目的答案即 开局是否为奇数或者偶数

动态规划

我们首先尝试把几个数的结果列出 看看有没有规律可循

N=1 的时候,区间 (0, 1)中没有整数是 n 的因数,所以此时 Alice 败。

N=2 的时候,Alice 只能拿 1,N 变成 1,Bob 无法继续操作,故 Alice 胜。

N=3 的时候,Alice 只能拿 1,N 变成 2,根据 N=2 的结论,我们知道此时 Bob 会获胜,Alice 败。

N=4 的时候,Alice 能拿 1 或 2,如果 Alice 拿 1,根据 N=3 的结论,Bob 会失败,Alice 会获胜。

N=5 的时候,Alice 只能拿 1,根据 N =4 的结论,Alice 会失败。 ……

假设他们直接的胜负结果是人为的必然关系 (Alice可以选一个数让鲍勃一定失败 鲍勃也可以)

因为N=5这类的之后的数字都可以通过前面的结论获取结果

那么我们就可以根据初始的结论 来循环暴力获取后面的解

保证减去数之后上一个值的解为false就可以保证自己的胜利

解答

数学逻辑

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

动态规划

class Solution {
    public boolean divisorGame(int n) {
        //缓存计算结果
        boolean[] numResults = new boolean[n+5];

        numResults[1] = false;
        numResults[2] = true;
        
        //循环获取后面的结果解
        for(int i=3;i<=n;++i){ //让i=n 可以让j可以取到n-1
            for(int j=1;j<i;++j){ //循环获取可以取的竖
                if(i%j==0 && !numResults[i-j]){ //如果值可以整除并且根据之前的结果拿到必赢的方案 true 保证上个结果也就是鲍勃为false
                    numResults[i] = true;
                    break;
                }
            }
        }

        return numResults[n];
    }
}

时空复杂度分析

如果采用逻辑数学解法 时间复杂度为O(1) 空间复杂度为O(1)

如果采用动态规划解法 时间复杂度为O(N^2) 空间复杂度为o(N)

结语

此题涉及到数学的基本定义 并且算一种逻辑数学题 估计掌握这些原理的小学生也可以解出来 足以阐明数学基础的重要性

也涉及到动态规划 如何利用之前的结果来帮助我们寻找定论 虽然我没有真正学过动态规划 不过根据此题 隐隐有点理解 动态规划的特点 (假设一个定论 根据前面的运行结果 循环获取最终结果) 至于这种理解是不是完全正确 等之后真正系统的学习动态规划后再见分晓