Nim และจำนวน Grundy
แก้เกมแบบไม่ฝักใฝ่ฝ่ายใดด้วย XOR
Nim และจำนวน Grundy เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ทำความรู้จักเกม Nim
ใน Nim มีกองหินหลายกอง ในตาของคุณ คุณจะหยิบหินออกจากกองใดกองหนึ่งกี่ก้อนก็ได้ และผู้ที่หยิบก้อนสุดท้ายเป็นผู้ชนะ 🪨
ปริมาณมหัศจรรย์: XOR
ผลแพ้ชนะของเกมทั้งหมดตัดสินด้วย XOR ของขนาดกองหินทุกกอง ตัวเลขเดียวนี้บอกได้ว่าใครกำลังเป็นฝ่ายชนะ
กฎผลรวมของ Nim
หาก XOR ของกองหิน ซึ่งเรียกว่า ผลรวม nim มีค่าเป็นศูนย์ ผู้เล่นที่กำลังจะเดินจะแพ้ หากไม่เป็นศูนย์ ผู้เล่นคนนั้นจะชนะ
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pทำไมศูนย์จึงเป็นสัญญาณอันตราย
จากผลรวม nim ที่เป็น ศูนย์ การเดินทุกครั้งจะทำลายสมดุล และมอบผลรวมที่ไม่เป็นศูนย์ให้ฝ่ายตรงข้าม ซึ่งฝ่ายตรงข้ามจะทำให้กลับมาเป็นศูนย์ได้เสมอ
ค้นหาการเดินที่ชนะ
เมื่อผลรวม nim ไม่เป็นศูนย์ จะมีการเดินหนึ่งครั้งที่ทำให้ผลรวมกลับเป็น ศูนย์ได้เสมอ การเดินนั้นจะทำให้ฝ่ายตรงข้ามตกอยู่ในสถานะแพ้
นอกเหนือจาก Nim: ตัวเลข grundy
สำหรับเกมที่ผู้เล่นมีทางเลือกเหมือนกันแบบอื่น ๆ เราใช้ ตัวเลข grundyประจำแต่ละสถานะ แนวคิดนี้ขยายแนวคิดผลรวม nim ไปยังเกมผลัดกันหยิบแทบทุกชนิด
การดำเนินการ mex
ค่าของ grundy ในสถานะหนึ่งคือ mex ซึ่งเป็นจำนวนเต็มไม่ติดลบที่น้อยที่สุดที่ไม่ปรากฏในค่าของ grundy จากการเดินของสถานะนั้น
def mex(s):
i = 0
while i in s:
i += 1
return iคำนวณ grundy ด้วยการเรียกซ้ำ
เรียกซ้ำไปยังสถานะที่เข้าถึงได้ทั้งหมด รวบรวมค่าของ grundy แล้วหา mex ของเซตนั้น
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})grundy เป็นศูนย์หมายถึงแพ้
สถานะเกมที่มีค่า grundy 0 เป็นตำแหน่งแพ้ เช่นเดียวกับผลรวม nim ที่เป็นศูนย์ ส่วนค่าที่ไม่เป็นศูนย์หมายถึงชนะ
ทฤษฎี Sprague-grundy
สำหรับเกมอิสระที่เล่นพร้อมกัน ให้ทำ XOR ค่าของ grundy ของแต่ละเกม ผลลัพธ์ Sprague-grundy นี้เปลี่ยนผลรวมของเกมใด ๆ ให้กลายเป็น Nim ได้ ✨
กรณีที่ใช้ได้
ทฤษฎี grundy ต้องใช้กับเกมที่ ผู้เล่นมีทางเลือกเหมือนกัน: ผู้เล่นทั้งสองมีการเดินชุดเดียวกัน และผู้ที่เดินเป็นคนสุดท้ายจะชนะ โปรดตรวจสอบเงื่อนไขนี้ก่อนนำไปใช้
ตรวจสอบอย่างรวดเร็ว
คุณเริ่มเกม Nim ด้วยกองหินขนาด 1, 2 และ 3 คุณกำลังเป็นฝ่ายชนะหรือไม่
ทบทวน
Nim ขึ้นอยู่กับ XOR ของกองหิน: ศูนย์หมายถึงแพ้ และค่าที่ไม่เป็นศูนย์หมายถึงชนะ ตัวเลข grundy และ mex ขยายแนวคิดนี้ไปยังเกมที่ผู้เล่นมีทางเลือกเหมือนกันหลายรูปแบบ 🏆
คำถามที่พบบ่อย
บทเรียน “Nim และจำนวน Grundy” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “Nim และจำนวน Grundy” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “Nim และจำนวน Grundy”
แก้เกมแบบไม่ฝักใฝ่ฝ่ายใดด้วย XOR คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “Nim และจำนวน Grundy” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สถานะชนะและแพ้ในเกม
- Nim และจำนวน Grundy
- พบกันตรงกลาง
- แก้บั๊กเร็ว: การทดสอบความเค้นและคัดแยกปัญหา