สถานะชนะและแพ้ในเกม
วิเคราะห์ว่าใครชนะเมื่อเล่นอย่างเหมาะสมที่สุด
สถานะชนะและแพ้ในเกม เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ผู้เล่นสองคน เล่นอย่างสมบูรณ์แบบ
ใน เกมเชิงการจัดแบบ ผู้เล่นสองคนผลัดกันเดิน ทั้งคู่เล่นอย่างสมบูรณ์แบบ และผู้ที่ไม่สามารถเดินได้จะแพ้ หน้าที่ของคุณคือทำนายผู้ชนะเท่านั้น 🎯
ทุกสถานะมีป้ายกำกับ
สถานะของเกมแต่ละแบบเรียกว่า สถานะ งานทั้งหมดของคุณคือกำกับทุกสถานะว่าเป็นสถานะชนะหรือแพ้สำหรับผู้เล่นที่กำลังจะเดิน
ความหมายของสถานะชนะ
สถานะหนึ่งเป็น สถานะชนะ หากผู้เล่นที่กำลังจะเดินมีอย่างน้อยหนึ่งการเดินที่นำไปสู่สถานะแพ้ของฝ่ายตรงข้าม
ความหมายของสถานะแพ้
สถานะหนึ่งเป็น สถานะแพ้ เมื่อทุกการเดินที่คุณทำจะมอบสถานะชนะให้ฝ่ายตรงข้าม คุณติดอยู่ในสถานการณ์ที่ไม่ว่าทำอย่างไรก็ไม่รอด
กรณีฐาน
ตำแหน่งที่ไม่สามารถเดินได้เลยคือ กรณีฐาน ผู้เล่นที่พบตำแหน่งนี้แพ้ไปแล้ว ดังนั้นให้กำกับตำแหน่งนี้ว่าแพ้
สร้างจากด้านล่างขึ้นมา
เริ่มจากกรณีฐานแล้วค่อย ๆ ขยายออกไป ป้ายกำกับของสถานะใหม่แต่ละสถานะขึ้นอยู่กับสถานะที่ การเดินของมันนำไปถึงเท่านั้น
การเดินที่ดีเพียงครั้งเดียวก็พอ
หากต้องการชนะ คุณต้องการเพียง หนึ่งการเดินไปยังสถานะแพ้ของฝ่ายตรงข้าม การพบทางหนีเพียงทางเดียวก็เพียงพอ
ตัวอย่างสั้น ๆ
ให้หยิบหิน 1 หรือ 2 ก้อนจากกอง และผู้ที่หยิบก้อนสุดท้ายเป็นผู้ชนะ เมื่อมี หิน 0 ก้อน ผู้ที่กำลังเดินจะแพ้ ดังนั้นจึงเป็นสถานะแพ้
เขียนการตรวจสอบผู้ชนะ
การเรียกซ้ำนี้กำกับสถานะด้วยการลองทุกการเดิน แล้วเรียกซ้ำกับผลลัพธ์ที่ได้ ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))จดจำผลลัพธ์เพื่อให้เร็ว
สถานะเดิมเกิดซ้ำในหลายแขนง ดังนั้นให้แคชผลลัพธ์แต่ละรายการ บันทึกช่วยจำแบบง่าย ๆ จะเปลี่ยนงานจากเลขชี้กำลังให้เป็นเวลาเชิงเส้น
from functools import lru_cache
@lru_cache(None)
def win(n):
return n != 0 and any(not win(n - k) for k in (1, 2))สมมาตรคือทางลัด
หากตำแหน่งมี สมมาตรอย่างสมบูรณ์ ผู้เล่นคนที่สองมักเลียนแบบการเดินและเป็นฝ่ายชนะได้ โปรดสังเกตกลเม็ดการเลียนแบบนี้
ตรวจสอบอย่างรวดเร็ว
คุณกำลังอยู่ในสถานะหนึ่ง เมื่อใดสถานะนั้นจึงเป็นสถานะแพ้สำหรับคุณ
ทบทวน
ขณะนี้คุณสามารถกำกับสถานะได้แล้ว: win มีการเดินหนึ่งครั้งที่นำไปสู่ความพ่ายแพ้ของฝ่ายตรงข้าม ส่วนสถานะแพ้ไม่มีการเดินเช่นนั้น ให้สร้างจากกรณีฐานและจดจำผลลัพธ์ 🧠
คำถามที่พบบ่อย
บทเรียน “สถานะชนะและแพ้ในเกม” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “สถานะชนะและแพ้ในเกม” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “สถานะชนะและแพ้ในเกม”
วิเคราะห์ว่าใครชนะเมื่อเล่นอย่างเหมาะสมที่สุด คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “สถานะชนะและแพ้ในเกม” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สถานะชนะและแพ้ในเกม
- Nim และจำนวน Grundy
- พบกันตรงกลาง
- แก้บั๊กเร็ว: การทดสอบความเค้นและคัดแยกปัญหา