Nim ve Grundy Sayısı
Tarafsız oyunları XOR ile çözün.
Nim ve Grundy Sayısı, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Nim oyunuyla tanışın
Nim oyununda birkaç taş yığını vardır. Sıranız geldiğinde bir yığından istediğiniz sayıda taş kaldırırsınız ve son taşı alan oyuncu kazanır. 🪨
Sihirli nicelik: XOR
Oyunun tamamını, tüm yığın boyutlarının XOR işlemi belirler. Bu tek sayı kimin kazanacağını söyler.
Nim toplamı kuralı
Yığınların XOR işlemine Nim toplamı denir. Bu toplam sıfırsa sıradaki oyuncu kaybeder; sıfır değilse o oyuncu kazanır.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pSıfır neden sorun demektir
Sıfır Nim toplamından sonra yapılan her hamle dengeyi bozar ve rakibe, her zaman yeniden oluşturabileceği sıfır olmayan bir toplam bırakır.
Kazandıran hamleyi bulma
Nim toplamı sıfır değilse, onu yeniden sıfıra götüren bir hamle her zaman vardır. Bu hamle rakibinizi kaybeden konumuna getirir.
Nim'in ötesi: Grundy sayıları
Diğer tarafsız oyunlar için her durum başına bir Grundy sayısı kullanırız. Bu, Nim toplamı fikrini neredeyse her taş alma oyununa geneller.
mex işlemi
Bir durumun Grundy değeri mex'tir: hamlelerinin Grundy değerleri arasında bulunmayan en küçük negatif olmayan tam sayı.
def mex(s):
i = 0
while i in s:
i += 1
return iGrundy'yi özyinelemeyle hesaplama
Ulaşılabilen tüm durumlar üzerinde özyinelemeli olarak ilerleyin, bunların Grundy değerlerini toplayın ve ardından bu kümenin mex'ini alın.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy sıfır bir kayıptır
Grundy 0 olan tek bir oyun durumu, tıpkı Nim toplamının sıfır olması gibi kaybettiren bir konumdur. Sıfır olmayan değer kazanma anlamına gelir.
Sprague-Grundy teoremi
Aynı anda oynanan bağımsız oyunların Grundy sayılarına XOR uygulayın. Bu Sprague-Grundy sonucu, herhangi bir oyun toplamını Nim'e dönüştürür. ✨
Ne zaman uygulanır
Grundy kuramı tarafsız bir oyun gerektirir: iki oyuncunun hamleleri aynı olmalı ve son hamleyi yapan kazanmalıdır. Kullanmadan önce bunu kontrol edin.
Hızlı kontrol
1, 2 ve 3 taşlık yığınlarla bir Nim oyununa başlıyorsunuz. Kazanıyor musunuz?
Özet
Nim, yığınların XOR işlemine dayanır: sıfır kaybettirir, sıfır olmayan değer kazandırır. Grundy sayıları ve mex, bu fikri birçok tarafsız oyuna genişletir. 🏆
Sıkça Sorulan Sorular
“Nim ve Grundy Sayısı” dersi ücretsiz mi?
Evet — “Nim ve Grundy Sayısı” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Nim ve Grundy Sayısı” dersinde ne öğreneceğim?
Tarafsız oyunları XOR ile çözün. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Nim ve Grundy Sayısı” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Oyunlarda Kazanma ve Kaybetme Durumları
- Nim ve Grundy Sayısı
- Ortada Buluşma
- Hızlı Hata Ayıklama: Stres Testleri ve Triage