Nim i liczba Grundy’ego
Rozwiązywanie gier bezstronnych za pomocą XOR
Nim i liczba Grundy’ego to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Poznajmy grę Nim
W grze Nim znajduje się kilka kupek kamieni. W swoim ruchu można usunąć dowolną liczbę kamieni z jednej kupki, a wygrywa gracz, który zabierze ostatni kamień. 🪨
Magiczna wielkość: XOR
O wyniku całej gry decyduje operacja XOR na rozmiarach wszystkich kupek. Ta jedna liczba wskazuje, kto ma wygrywającą pozycję.
Reguła sumy Nim
Jeśli XOR rozmiarów kupek, nazywany nim-sum, wynosi zero, gracz wykonujący ruch przegrywa. Jeśli jest różny od zera, ten gracz wygrywa.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pDlaczego zero oznacza kłopoty
Przy zerowej sumie nim każdy ruch zaburza równowagę, przekazując przeciwnikowi niezerową sumę, którą może on zawsze przywrócić do zera.
Znajdowanie wygrywającego ruchu
Gdy suma nim jest różna od zera, zawsze istnieje ruch, który sprowadza ją z powrotem do zera. Taki ruch pozostawia przeciwnika w przegranej pozycji.
Poza grą Nim: liczby Grundy’ego
W innych grach bezstronnych każdemu stanowi przypisujemy liczbę Grundy’ego. Uogólnia ona ideę sumy nim na niemal każdą grę polegającą na zabieraniu elementów.
Operacja mex
Wartość Grundy’ego stanu to mex: najmniejsza nieujemna liczba całkowita, której brakuje wśród wartości Grundy’ego dla jego ruchów.
def mex(s):
i = 0
while i in s:
i += 1
return iObliczanie liczby Grundy’ego rekurencyjnie
Należy rekurencyjnie przejść do wszystkich osiągalnych stanów, zebrać ich wartości Grundy’ego, a następnie obliczyć mex tego zbioru.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Zero Grundy’ego oznacza przegraną
Pojedynczy stan gry o wartości Grundy 0 jest pozycją przegraną, dokładnie tak jak pozycja z sumą nim równą zero. Wartość niezerowa oznacza wygraną.
Twierdzenie Sprague’a-Grundy’ego
Dla niezależnych gier rozgrywanych jednocześnie należy wykonać XOR ich liczb Grundy’ego. Ten wynik Sprague’a-Grundy’ego zamienia dowolną sumę gier w grę Nim. ✨
Kiedy można je stosować
Teoria Grundy’ego wymaga gry bezstronnej: obaj gracze mają te same ruchy, a wygrywa osoba wykonująca ostatni ruch. Przed zastosowaniem tej teorii należy to sprawdzić.
Szybkie sprawdzenie
Rozpoczynają Państwo grę Nim z kupkami o rozmiarach 1, 2 i 3. Czy mają Państwo wygrywającą pozycję?
Podsumowanie
Gra Nim opiera się na operacji XOR na rozmiarach kupek: zero oznacza przegraną, a wartość niezerowa — wygraną. Liczby Grundy’ego i operacja mex rozszerzają tę metodę na wiele gier bezstronnych. 🏆
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
Często zadawane pytania
Czy lekcja „Nim i liczba Grundy’ego” jest bezpłatna?
Tak — pełny tekst „Nim i liczba Grundy’ego” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Nim i liczba Grundy’ego”?
Rozwiązywanie gier bezstronnych za pomocą XOR Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Nim i liczba Grundy’ego”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Stany wygrywające i przegrywające w grach
- Nim i liczba Grundy’ego
- Spotkanie pośrodku
- Szybkie debugowanie: testy obciążeniowe i triage