ค้นหาผู้ชนะโดยเพิ่มความแตกต่างขององค์ประกอบในอาร์เรย์จนเป็นได้ใน Python

สมมติว่าเรามีอาร์เรย์ A ที่เป็นจำนวนเต็มบวก องค์ประกอบไม่ซ้ำกัน ตอนนี้ผู้เล่นสองคน P และ Q กำลังเล่นเกม ในแต่ละการเคลื่อนไหว ผู้เล่นคนใดคนหนึ่งหยิบตัวเลขสองตัว a และ b จากอาร์เรย์ และถ้า |a – b| ไม่อยู่ในอาร์เรย์หลังจากนั้นผู้เล่นจะเพิ่มหมายเลขนี้ลงในอาร์เรย์ เมื่อผู้เล่นไม่สามารถทำการย้ายเกมได้ เราต้องหาผู้ชนะของเกมหากผู้เล่น P เริ่มเกมเสมอ

ดังนั้นหากอินพุตเป็น A =[8,9,10] เอาต์พุตจะเป็น P

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ arr

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

• สำหรับผมอยู่ในช่วง 1 ถึง n ทำ

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

  • max_val :=สูงสุดของ max_val, arr[i]

• รวม :=(max_val / g) - n

• ถ้าผลรวมเป็นเลขคี่

  • ส่งคืน '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