لعبة Nim وعدد Grundy
حل الألعاب المحايدة باستخدام XOR
لعبة Nim وعدد Grundy درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
تعرّفوا إلى لعبة Nim
في Nim توجد عدة أكوام من الحجارة. وفي دوركم، أزيلوا أي عدد من كومة واحدة، ويفوز اللاعب الذي يأخذ الحجر الأخير. 🪨
الكمية السحرية: XOR
تتحدد اللعبة بأكملها من خلال XOR لأحجام جميع الأكوام. فهذا العدد الوحيد يخبركم بمن سيفوز.
قاعدة مجموع Nim
إذا كان XOR للأكوام، المسمى nim-sum، يساوي صفرًا، فإن اللاعب الذي عليه الدور يخسر. وإذا كان غير صفري، يفوز ذلك اللاعب.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pلماذا يعني الصفر وجود مشكلة
انطلاقًا من nim-sum يساوي صفرًا، تؤدي كل نقلة إلى كسر التوازن، فتمنح الخصم مجموعًا غير صفري يمكنه دائمًا إعادته إلى الصفر.
العثور على النقلة الرابحة
عندما يكون nim-sum غير صفري، توجد دائمًا نقلة تعيده إلى الصفر. وتضع هذه النقلة الخصم في وضع خاسر.
ما بعد Nim: أعداد Grundy
نستخدم في الألعاب المحايدة الأخرى عدد Grundy لكل حالة. وهو يعمم فكرة nim-sum على أي لعبة تقريبًا تعتمد على أخذ العناصر.
عملية 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-sum يساوي صفرًا. أما القيمة غير الصفرية فتعني الفوز.
مبرهنة Sprague-Grundy
بالنسبة إلى الألعاب المستقلة التي تُلعب معًا، احسبوا XOR لأعداد Grundy الخاصة بها. وتحول نتيجة Sprague-Grundy هذه مجموع أي ألعاب إلى لعبة Nim. ✨
متى تنطبق
تحتاج نظرية Grundy إلى لعبة محايدة؛ أي إن كلا اللاعبين يملكان النقلات نفسها، ويفوز آخر من ينفذ نقلة. تحققوا من ذلك قبل استخدامها.
تحقق سريع
تبدؤون لعبة Nim بأكوام أحجامها 1 و2 و3. هل أنتم الفائزون؟
مراجعة
تعتمد Nim على XOR للأكوام: فالقيمة الصفرية تعني الخسارة، وغير الصفرية تعني الفوز. وتوسع أعداد Grundy وmex هذه الفكرة لتشمل كثيرًا من الألعاب المحايدة. 🏆
الأسئلة الشائعة
هل درس «لعبة Nim وعدد Grundy» مجاني؟
نعم — نص درس «لعبة Nim وعدد Grundy» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «لعبة Nim وعدد Grundy»؟
حل الألعاب المحايدة باستخدام XOR تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «لعبة Nim وعدد Grundy»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حالات الفوز والخسارة في الألعاب
- لعبة Nim وعدد Grundy
- الالتقاء في المنتصف
- تصحيح الأخطاء بسرعة: اختبارات الضغط والفرز