在 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

更新于: 2020-08-27

113 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告