Nim og Grundy-tallet
Løs upartiske spill med XOR
Nim og Grundy-tallet er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Møt Nim-spillet
I Nim finnes det flere hauger med steiner. På din tur fjerner du et valgfritt antall fra én haug, og spilleren som tar den siste steinen, vinner. 🪨
Den magiske størrelsen: XOR
Hele spillet avgjøres av XOR av størrelsene på alle haugene. Dette ene tallet forteller hvem som vinner.
Nim-sum-regelen
Hvis XOR-en av haugene, kalt nim-sum, er null, taper spilleren som skal trekke. Hvis den ikke er null, vinner spilleren.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pHvorfor null betyr trøbbel
Fra en null nim-sum vil hvert trekk bryte balansen og gi motstanderen en sum som ikke er null, og den kan motstanderen alltid gjenopprette.
Finn vinner-trekket
Når nim-summen ikke er null, finnes det alltid et trekk som fører den tilbake til null. Det trekket setter motstanderen i en tapende posisjon.
Utover Nim: Grundy-tall
For andre upartiske spill bruker vi et Grundy-tall for hver tilstand. Det generaliserer nim-sum-ideen til nesten alle spill der man tar bort elementer.
mex-operasjonen
En tilstands Grundy-verdi er mex: det minste ikke-negative heltallet som mangler blant Grundy-verdiene til trekkene fra tilstanden.
def mex(s):
i = 0
while i in s:
i += 1
return iBeregn Grundy rekursivt
Gå rekursivt gjennom alle nåbare tilstander, samle Grundy-verdiene deres, og ta deretter mex av mengden.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy null er et tap
En enkelt spilltilstand med Grundy 0 er en tapende posisjon, akkurat som en nim-sum lik null. En verdi som ikke er null, betyr seier.
Sprague-Grundy-teoremet
For uavhengige spill som spilles samtidig tar du XOR av Grundy-tallene deres. Dette Sprague-Grundy-resultatet gjør enhver sum av spill om til Nim. ✨
Når det kan brukes
Grundy-teorien krever et upartisk spill: Begge spillerne har de samme trekkene, og den som gjør det siste trekket, vinner. Kontroller dette før du bruker teorien.
Rask kontroll
Du starter et Nim-spill med haugene 1, 2 og 3. Vinner du?
Oppsummering
Nim avhenger av XOR av haugene: null betyr tap, og en verdi som ikke er null, betyr seier. Grundy-tall og mex utvider dette til mange upartiske spill. 🏆
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Nim og Grundy-tallet» gratis?
Ja – hele teksten i «Nim og Grundy-tallet» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Nim og Grundy-tallet»?
Løs upartiske spill med XOR Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Nim og Grundy-tallet»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Vinnende og tapende tilstander i spill
- Nim og Grundy-tallet
- Møt på midten
- Feilsøk raskt: stresstester og triage