Python程序：找出集合元素移除游戏中获胜者

假设我们有一组前 n 个自然数 {1..n}。阿马尔和比马尔正在玩一个游戏。游戏规则如下：

  • 阿马尔总是先手

  • 在每次移动中，当前玩家从集合中选择一个素数 p。然后，该玩家移除 p 及其所有倍数。

  • 谁没有移动谁就输掉比赛。如果我们有 n，我们必须找到获胜者的名字。

因此，如果输入像 n = 5，则输出将是阿马尔，因为初始集合是 {1,2,3,4,5}。现在假设阿马尔选择一个数字 p = 2，并从集合中移除 2、4，所以当前集合是 {1,3,5}，还有两个素数剩下，所以比马尔可以选择其中任何一个，但没有剩余元素可以移除，最后阿马尔移除另一个素数并赢得比赛。

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

  • primes := 一个大小为 100000 的数组，最初所有值都为 0
  • sieve := 一个大小为 100000 的数组，最初所有值都为 0
  • 对于 i 从 2 到 99999，执行以下操作：
    • 如果 sieve[i] 等于 0，则：
      • primes[i] := primes[i-1]+1
      • 对于 j 从 i 到 100000，每次递增 i，执行以下操作：
        • sieve[j] := i
    • 否则：
      • primes[i] := primes[i-1]
  • 从主方法执行以下操作：
  • 如果 primes[n] 为奇数，则返回“比马尔”，否则返回“阿马尔”。

示例

让我们看看以下实现以获得更好的理解：

primes = [0 for i in range(100001)]
sieve = [0 for i in range(100001)]
for i in range(2, 100000):
   if sieve[i] == 0:
      primes[i] = primes[i-1]+1

      for j in range(i, 100001, i):
         sieve[j] = i
   else:
      primes[i] = primes[i-1]

def solve(n):
   return "Bimal" if primes[n] % 2 == 0 else "Amal"

n = 5
print(solve(n))

输入

5

输出

Amal

更新于: 2021年10月23日

141 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告