Nim en het Grundy-getal
Impartiale spellen met XOR oplossen
Nim en het Grundy-getal is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 2 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Maak kennis met het Nim-spel
In Nim zijn er meerdere stapels stenen. Tijdens je beurt haal je een willekeurig aantal stenen uit één stapel en wint de speler die de laatste steen pakt. 🪨
De magische hoeveelheid: XOR
Het hele spel wordt bepaald door de XOR van de groottes van alle stapels. Dat ene getal vertelt je wie er wint.
De nim-somregel
Als de XOR van de stapels, de nim-som genoemd, nul is, verliest de speler die aan de beurt is. Is de waarde niet nul, dan wint die speler.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pWaarom nul problemen betekent
Vanuit een nim-som van nul verbreekt elke zet het evenwicht. Je geeft de tegenstander dan een som die niet nul is en die hij of zij altijd kan herstellen.
De winnende zet vinden
Als de nim-som niet nul is, bestaat er altijd een zet die deze weer op nul brengt. Daarmee geef je de tegenstander een verliezende positie.
Verder dan Nim: Grundy-getallen
Voor andere onpartijdige spellen gebruiken we per toestand een Grundy-getal. Dit breidt het idee van de nim-som uit naar bijna elk spel waarin je iets wegneemt.
De mex-bewerking
De Grundy-waarde van een toestand is de mex: het kleinste niet-negatieve gehele getal dat ontbreekt in de Grundy-waarden van zijn zetten.
def mex(s):
i = 0
while i in s:
i += 1
return iGrundy berekenen met recursie
Voer recursie uit op alle bereikbare toestanden, verzamel hun Grundy-waarden en neem daarna de mex van die verzameling.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy nul betekent verlies
Een speltoestand met Grundy 0 is een verliezende positie, precies zoals een nim-som van nul. Een waarde die niet nul is, betekent winst.
De stelling van Sprague-Grundy
Bij onafhankelijke spellen die tegelijk worden gespeeld, neem je de XOR van hun Grundy-getallen. Dit Sprague-Grundy-resultaat maakt van elke som van spellen een Nim-spel. ✨
Wanneer het van toepassing is
De Grundy-theorie vereist een onpartijdig spel: beide spelers hebben dezelfde zetten en de speler die als laatste een zet doet, wint. Controleer dat voordat je de theorie gebruikt.
Snelle controle
Je begint een Nim-spel met stapels van 1, 2 en 3 stenen. Win je?
Samenvatting
Bij Nim draait alles om de XOR van de stapels: nul betekent verlies, niet nul betekent winst. Grundy-getallen en mex breiden dit uit naar veel onpartijdige spellen. 🏆
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Nim en het Grundy-getal” gratis?
Ja — de volledige tekst van “Nim en het Grundy-getal” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Nim en het Grundy-getal”?
Impartiale spellen met XOR oplossen Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Nim en het Grundy-getal”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Winnende en verliezende toestanden in spellen
- Nim en het Grundy-getal
- Meet in the Middle
- Snel debuggen: stresstests en triage