โปรแกรมตรวจสอบว่า Amal สามารถชนะเกมสโตนได้หรือไม่ใน Python

สมมติว่ามีผู้เล่นสองคนคือ Amal และ Bimal พวกเขากำลังเล่นเกม และโดยที่ Amal จะเริ่มก่อน ในขั้นต้น มีก้อนหินที่แตกต่างกันในกอง ในเทิร์นของผู้เล่นแต่ละคน เขาทำการเคลื่อนไหวโดยนำหินจำนวนสี่เหลี่ยมจัตุรัส (ที่ไม่ใช่ศูนย์) ออกจากกอง นอกจากนี้ หากผู้เล่นคนใดไม่สามารถเคลื่อนไหวได้ เขาจะแพ้เกม ดังนั้นหากเรามี n เราต้องตรวจสอบว่า Amal สามารถชนะเกมได้หรือไม่

ดังนั้น หากอินพุตเป็น n =21 เอาต์พุตจะเป็น True เพราะในตอนแรก Amal สามารถรับ 16 ได้ จากนั้น Bimal รับ 4 จากนั้น Amal รับ 1 และชนะเกม

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

สี่เหลี่ยม :=รายการใหม่
สี่เหลี่ยม :=1
เพิ่มขึ้น :=3
ในขณะที่กำลังสอง <=n ทำ
- ใส่สี่เหลี่ยมที่ส่วนท้ายของสี่เหลี่ยม
- สี่เหลี่ยม :=สี่เหลี่ยม + เพิ่มขึ้น
- เพิ่มขึ้น :=เพิ่มขึ้น + 2
ใส่สี่เหลี่ยมที่ส่วนท้ายของสี่เหลี่ยม
dp :=รายการขนาดว่าง (n + 1)
dp[0] :=เท็จ
สำหรับ k ในช่วง 1 ถึง n ทำ
- s :=0
- dp[k] :=เท็จ
- ในขณะที่ squares[s] <=k และ dp[k] ว่างเปล่า ให้ทำ
  - ถ้า dp[k - squares[s]] ว่างเปล่า แสดงว่า
    - dp[k] :=จริง
  - s :=s + 1
ส่งคืนองค์ประกอบสุดท้ายของ dp

ตัวอย่าง

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

def solve(n):
   squares = []
   square = 1
   increase = 3
   while square <= n:
      squares.append(square)
      square += increase
      increase += 2
   squares.append(square)

   dp = [None] * (n + 1)
   dp[0] = False
   for k in range(1, n + 1):
      s = 0
      dp[k] = False
      while squares[s] <= k and not dp[k]:
         if not dp[k - squares[s]]:
            dp[k] = True
         s += 1
   return dp[-1]

n = 21
print(solve(n))

อินพุต

ผลลัพธ์

True