Python每日一练-----除数博弈
☀（day47：P44）
目录
📝题目：
🚩题目分析：
💡解题思路：
🌟解法一：
🌈代码实现
🌟解法二：
🌈代码实现
✏代码注释
📝题目：
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：
- 选出任一 x，满足 0 < x < n 且 n % x == 0 。
- 用 n - x 替换黑板上的数字 n 。
如果玩家无法执行这些操作，就会输掉游戏。(1 <= n <= 1000)
只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。
⭐示例 1：
输入：n = 2
输出：true
解释说明：爱丽丝选择 1，鲍勃无法进行操作。
⭐示例 2：
输入：n = 3
输出：false
解释说明：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
🚩题目分析：
分析博弈过程根据规律解题。
💡解题思路：
🌟解法一：
- n=1 的时候，区间 (0, 1) 中没有整数是 n的因数，所以此时 Alice 败。
- n = 2 的时候，Alice 只能拿 1，n 变成 1，（因为 0 < x < n，所以Bob不能拿1）Bob 无法继续操作，故Alice 胜。
- n = 3的时候，Alice 只能拿 1，n 变成 2，根据 n = 2的结论，我们知道此时 Bob 会获胜，Alice 败。
- n=4 的时候，Alice 能拿 1 或 2，如果Alice 拿 1，根据 n = 3 的结论，\text{Bob}Bob 会失败，Alice 会获胜。
- n = 5 的时候，Alice 只能拿 1，根据n=4 的结论，Alice 会失败。
- ......
我们猜想：n 为奇数的时候Alice（先手）必败，n 为偶数的时候 Alice （先手）必胜。
我们使用数学归纳法证明。
n = 1 和 n = 2时结论成立。
n > 2 时，假设n ≤ k 时该猜想成立，则 n=k+1 时：
如果 k为偶数，则 k + 1 为奇数，x 是k+1 的因数，只可能是奇数，而奇数减去奇数等于偶数，且 k+1−x ≤ k，故轮到 Bob 的时候都是偶数。而根据我们的猜想假设 n ≤ k 的时候偶数的时候先手必胜，故此时无论Alice 拿走什么，Bob 都会处于必胜态，所以Alice 处于必败态。
如果 k为奇数，k+1 为偶数，x 可以是奇数也可以是偶数，若Alice 减去一个奇数，那么 - k+1−x 是一个小于等于 k 的奇数，x1是k+1-x的因数，只能是奇数，此时Bob 占有它，k+1-x-x1为偶数且小于k，相当于Alice偶数先手，Bob处于必败态，则 Alice 处于必胜态。所以猜想成立。
根据题目都是Alice先手
🌈代码实现
def divisorGame(n): return n % 1 == 0或者
def divisorGame(n): return n & 1 == 0这两种写法都是判断n是否为偶数，第一种写法使用求模运算，第二种方法使用位运算。两种写法时间空间复杂度都是O(1)。不过第二种写法理论来说运算速度更快。
了解位运算：还在为原码、反码、补码和位运算搞得头昏脑涨？点这里，还你清析脑回路
🌟解法二：
我们按照游戏规则进行。
🌈代码实现
def divisorGame(n): dp = [] x = 1 flag = False while x < n + 1: if n % x == 0: n -= x dp.append(flag) flag = not flag x = 1 else: x += 1 return dp[-1]✏代码注释
def divisorGame(n): dp = [] # 用于储存游戏结果 x = 1 # Alice先手最小取1 flag = False # 初始化标记值 while x < n + 1: if n % x == 0: n -= x dp.append(flag) """轮到Bob的回合，说明Alice成功找到符合游戏规则的x， 我们将flag = False变成True，当Bob也从1开始寻找满足的x， 当Bob找到符合的x后，轮到Alic，这时将flag = True换成flag = False。 由此可以看出当下一个人找不到满足的x时，对应dp中的最后一个元素满足题意""" flag = not flagx = 1 else: x += 1 # 所取的x不满足游戏规则，需要提高x的值 return dp[-1]今天就到这，明天见。🚀
❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄
