使用Python判断我们在游戏中是否赢了

假设我们在玩一个两个玩家的游戏，其中有n个弹珠，每轮一个玩家必须拿走一个正整数的平方个弹珠。如果一个玩家无法拿走该平方数的弹珠，则他/她输了。因此，给定一个数字n，我们必须找出是否可以赢得游戏。我们总是第一轮并选择最优数量的弹珠。

因此，如果输入为14，则输出将为True。因为在第一轮中，我们拿走9个弹珠。从中剩下5个弹珠，另一个玩家可以最多拿走4个弹珠，留下1个弹珠。因此，在下一轮中，我们拿走最后一个弹珠，玩家无法有任何行动。因此，我们赢了。

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

如果n≤0，则
- 返回False
ans：= False
对于i从（n的平方根的整数部分到-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))