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

สมมติว่าเราเล่นเกม 2 คน มีลูกปัด n ลูก ในแต่ละรอบ ผู้เล่นต้องหยิบลูกปัดจำนวนที่เป็นจำนวนกำลังสองบวก หากผู้เล่นไม่สามารถหยิบได้ จะแพ้ กำหนดจำนวน n เราต้องหาว่าสามารถชนะเกมได้หรือไม่ เราเล่นก่อนและเลือกจำนวนลูกปัดอย่างเหมาะสม

เช่น ถ้าอินพุตคือ 14 ผลลัพธ์จะเป็น True เพราะในรอบแรกเราหยิบ 9 ลูก เหลือ 5 ลูก คู่แข่งหยิบได้สูงสุด 4 ลูก เหลือ 1 ลูก รอบต่อมาเราหยิบลูกสุดท้าย เหลือ 0 คู่แข่งไม่สามารถเล่นได้ เราชนะ

ขั้นตอนการแก้ปัญหา

1. ถ้า n <= 0 คืนค่า False
2. ans := False
3. สำหรับ i ในช่วง int(sqrt(n)) ลงถึง 1:
   • ถ้า i * i > n ออกจากลูป
   • ans := ans OR (not solve(n - i * i))
   • ถ้า ans เป็น True คืนค่า ans
4. คืนค่า ans

ตัวอย่างการใช้งาน

from math import sqrt

def solve(n):
    if n <= 0:
        return False
    ans = False
    for i in range(int(sqrt(n)), 0, -1):
        if i * i > n:
            break
        ans = ans | (not solve(n - i * i))
        if ans:
            return ans
    return ans

print(solve(14))

อินพุต

14

เอาต์พุต

True