โปรแกรมหาผู้ชนะเกมกำจัดชุดองค์ประกอบใน Python

สมมุติว่าเรามีชุดของจำนวนธรรมชาติ n ตัวแรก {1..n} Amal และ Bimal กำลังเล่นเกม กฎของเกมมีดังนี้

อามาลเล่นก่อนเสมอ
ในแต่ละการเคลื่อนไหว ผู้เล่นปัจจุบันจะเลือกเลขเฉพาะ p จากเซต จากนั้นผู้เล่นจะลบ p และตัวคูณทั้งหมดออกจากชุด
ใครไม่ขยับจะแพ้เกมนี้ ถ้ามี n เราต้องหาชื่อผู้ชนะ

ดังนั้น หากอินพุตมีค่าเท่ากับ n =5 เอาต์พุตจะเป็น Amal เนื่องจากเซตเริ่มต้นคือ {1,2,3,4,5} ตอนนี้ให้ Amal เลือกตัวเลข p =2 และลบ 2, 4 ออกจากชุด ดังนั้นชุดปัจจุบันคือ {1,3,5} เหลือจำนวนเฉพาะสองจำนวน ดังนั้น Bimal อาจเลือกจำนวนใดๆ ก็ได้ แต่ไม่มีองค์ประกอบเหลืออยู่ เพื่อลบออกและในที่สุด Amal ก็ลบไพรม์อื่นและชนะเกม

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

primes :=อาร์เรย์ขนาด 100000 เริ่มแรกทั้งหมดเป็น 0
ตะแกรง :=อาร์เรย์ขนาด 100000 เริ่มต้นทั้งหมดเป็น 0
สำหรับฉันในช่วง 2 ถึง 99999 ทำ
- ถ้าตะแกรง[i] เท่ากับ 0 แล้ว
  - primes[i] :=ไพรม์[i-1]+1
  - สำหรับ j ในช่วง i ถึง 100000 อัปเดตในแต่ละขั้นตอนโดย i ทำ
    - ตะแกรง[j] :=ฉัน
- มิฉะนั้น
  - primes[i] :=ไพรม์[i-1]
จากวิธีหลัก ให้ทำดังนี้ -
ส่งคืน "Bimal" หากจำนวนเฉพาะ [n] เป็นเลขคี่ มิฉะนั้น "Amal"

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

ผลลัพธ์

Amal