Nim i liczba Grundy’ego
Rozwiązywanie gier bezstronnych za pomocą XOR
Nim i liczba Grundy’ego to bezpłatna lekcja Competitive Programming Academy 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 Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy 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. 🏆
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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Nim i liczba Grundy’ego”?
Rozwiązywanie gier bezstronnych za pomocą XOR Ćwiczysz Competitive Programming Academy 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ąć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy 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 Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy 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