乐趣区

关于leetcode:LeetCode-1025-除数博弈-Python

jiezi

1025. 除数博弈

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/divisor-game

题目

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

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

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

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

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

示例 1：

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

示例 2：

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

提醒：

  • 1 <= N <= 1000

解题思路

思路：递推

在这里，咱们要从题目外面中找出法则。这里先将题目中游戏规则列举进去：

  • 给定数字 N，任取一数 x（0 < x < N），且 N % x == 0；
  • 入选定后，用 N – x 代替本来的 N。

在这里，依据下面的游戏规则，咱们先列举 N（1 <= N <= 1000）不同取值状况下，会呈现怎么的后果：

  • 当 N = 1，因为抽取数字 x 必须大于 0 且小于 N，这里无满足条件的数字，断定爱丽丝输；
  • 当 N = 2，这里爱丽丝只能取 1，那么 N 随之会变为 1，依据下面的剖析，此时鲍勃无奈操作，断定鲍勃输，爱丽丝赢；
  • 当 N = 3，此时爱丽丝只能选取 1，N 随之变为 2，这里依据 N = 2 的剖析，此时鲍勃取 1，爱丽丝输；
  • 当 N = 4，爱丽丝可取 1 或 2。若取 1 时，依据 N = 3 的剖析，这里鲍勃只能取 1，爱丽丝随后再取 1，鲍勃无奈操作，为输。爱丽丝赢;
  • 当 N = 5，爱丽丝同样只能取 1，那么依据 N = 4 的剖析，爱丽丝最终会输；
  • ……

在这里，能够发现，当 N 为奇数时，爱丽丝先抉择的状况下会输；而 N 为偶数时，爱丽丝后手会赢。尝试用 数学归纳法 证实这个论断是否可行：

  • 当 N = 1 和 N = 2 时，可直接判断，论断成立。

  • 当 N > 2 时，分状况进行探讨（题目曾经阐明两个玩家都以最佳状态参加游戏），假如 N <= m 论断成立，那么当 N=m+1 时，状况如下：

    • 当 m 为偶数时，m+1 为奇数，x 的取值必须是 N(也就是 m+1) 的约数，那么 x 只能取奇数，那么新的 N=N-x（也就是 m+1-x）为偶数，此时 m+1-x <= m，后面假如 N <= m 时，偶数的状况下，后手的玩家会赢。那么在这里，无论爱丽丝先手取值拿走什么数字，剩下的都是偶数，此时轮到鲍勃抉择，那么鲍勃肯定能赢，而爱丽丝会输；
    • 当 m 为奇数时，m+1 为偶数，此时 x 的取值能够是偶数也能够是奇数。如果此时爱丽丝先手抉择奇数，那么剩下的也肯定奇数，而且 m+1-x <= m，此时轮到鲍勃抉择，依据后面的剖析，N <= m 时，奇数状况下，先手玩家肯定输，所以无论此时鲍勃如何抉择什么都会输，那么爱丽丝赢。

那么，后面假如的论断成立，所以只有判断给定的 N 值是奇数还是偶数，则能够断定玩家输赢。

代码十分简洁，因为本题是博弈题，次要还是从题目中总结出法则。

代码实现 

class Solution:
    def divisorGame(self, N: int) -> bool:
        return N % 2 == 0

实现后果

欢送关注

公众号【书所集录】

退出移动版