在 Python 中找到獲勝者，方法是不斷對陣列中的元素進行兩兩差值運算，直到無法進行為止

假設我們有一個包含正整數的陣列 A，元素是唯一的，現在，兩個玩家 P 和 Q 正在玩一個遊戲。在每次移動中，任何一個玩家從陣列中選擇兩個數字 a 和 b，如果 |a – b| 在之後不在陣列中，則該玩家將此數字新增到陣列中。當一個玩家無法進行移動時，該玩家輸掉遊戲。如果玩家 P 總是先開始遊戲，我們必須找到遊戲獲勝者。

因此，如果輸入類似於 A = [8,9,10]，則輸出將為 P。

要解決此問題，我們將遵循以下步驟：

• n := 陣列的大小

• g := arr[0]，max_val := arr[0]

• 對於 i 從 1 到 n，執行

  • g := gcd(g, arr[i])

  • max_val := max_val 和 arr[i] 中的最大值

• total :=(max_val / g) - n

• 如果 total 為奇數，則

  • 返回 'P'

• 返回 'Q'

示例

讓我們看看以下實現以更好地理解：

 線上演示

from math import gcd
def who_is_the_winner(arr) :
   n = len(arr)
   g = arr[0]
   max_val = arr[0]
   for i in range(1, n) :
      g = gcd(g, arr[i])
      max_val = max(max_val, arr[i])
   total = (max_val / g) - n
   if (total % 2 == 1) :
      return 'P'
   return 'Q'

arr = [8,9,10]
print(who_is_the_winner(arr))

輸入

[8,9,10]

輸出

P

Arnab Chakraborty

更新於: 2020-08-27

113 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始