Python游戏胜负判断程序

假设我们正在玩一个两人游戏，游戏中有n颗弹珠，每一轮，玩家必须拿走正方形数量的弹珠。如果玩家无法拿走正方形数量的弹珠，则该玩家输。因此，给定一个数字n，我们必须确定我们能否赢得游戏。我们总是先走，并选择最佳数量的弹珠。

因此，如果输入是14，则输出为True。因为在第一轮，我们拿走9颗弹珠。剩下5颗弹珠，另一位玩家最多可以拿走4颗弹珠，剩下1颗弹珠。因此，在下一轮，我们拿走最后一颗弹珠，对手无法行动，我们获胜。

为了解决这个问题，我们将遵循以下步骤：

  • 如果 n <= 0，则
    • 返回 False
  • ans := False
  • 对于 i 从 n 的平方根的整数部分到 -1，递减 1，执行：
    • 如果 i * i > n，则
      • 跳出循环
    • ans := ans OR (not solve(n - i * i))
    • 如果 ans 为 True，则
      • 返回 ans
  • 返回 ans

示例

让我们看看下面的实现以更好地理解：

from math import sqrt

def solve(n):
   if n <= 0:
      return False
   ans = False
   for i in range(int(sqrt(n)), 0, -1):
      if i * i > n:
         break
      ans = ans | (not solve(n - i * i))
      if ans:
         return ans
   return ans

print(solve(14))

输入

14

输出

True

更新于：2021年10月16日

486 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告