สมมติว่าเรากำลังเล่นเกมที่มีผู้เล่นสองคนซึ่งมีลูกหินจำนวน n ลูก และในแต่ละรอบ ผู้เล่นจะต้องนำลูกหินเป็นจำนวนกำลังสองเป็นบวก ถ้าผู้เล่นรับลูกแก้วจำนวนเท่านั้นไม่ได้ เขา/เธอก็จะแพ้ ดังนั้น เมื่อให้หมายเลข n เราต้องค้นหาว่าเราจะชนะเกมได้หรือไม่ เราทำการเลี้ยวแรกเสมอและเลือกจำนวนลูกหินที่เหมาะสมที่สุด
ดังนั้นหากอินพุตเท่ากับ 14 เอาต์พุตจะเป็น True เพราะรอบแรกเราเอาลูกหิน 9 ลูก เหลือลูกหิน 5 ลูก ซึ่งผู้เล่นคนอื่นสามารถรับลูกหินได้สูงสุด 4 ลูก โดยเหลือลูกหิน 1 ลูกไว้ข้างหลัง ดังนั้น ในเทิร์นถัดไป เราจะเอาลูกแก้วลูกสุดท้ายทิ้งลูกแก้ว 0 ลูกไว้ข้างหลังคู่ต่อสู้ไม่สามารถเคลื่อนไหวได้ ดังนั้นเราจึงชนะ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ถ้า n <=0 แล้ว
- คืนค่าเท็จ
- ตอบ :=ผิด
- สำหรับฉันในช่วงจำนวนเต็มช่วงของ (รากที่สองของ (n)) ถึง -1 ลดลง 1 ทำ
- ถ้า i * i> n แล้ว
- ออกมาจากวงจร
- ans :=ans OR (ไม่แก้ (n - i * i))
- ถ้า ans เป็นจริง
- คืนสินค้า
- ถ้า i * i> n แล้ว
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
