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

Arnab Chakraborty

更新於: 2021年10月23日

141 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習