Nim e numero di Grundy
Risolvere giochi imparziali con XOR
Nim e numero di Grundy è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Alla scoperta del gioco del Nim
Nel Nim ci sono diversi mucchi di pietre. A ogni turno si può rimuovere un numero qualsiasi di pietre da un solo mucchio e vince chi prende l'ultima pietra. 🪨
La quantità magica: XOR
L'intero gioco è determinato dallo XOR delle dimensioni di tutti i mucchi. Quel singolo numero indica chi è in posizione vincente.
La regola del nim-sum
Se lo XOR dei mucchi, detto nim-sum, è zero, il giocatore di turno perde. Se è diverso da zero, quel giocatore vince.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pPerché zero è un problema
Partendo da un nim-sum zero, ogni mossa rompe l'equilibrio e lascia all'avversario un nim-sum diverso da zero, che potrà sempre riportare a zero.
Trovare la mossa vincente
Quando il nim-sum è diverso da zero, esiste sempre una mossa che lo riporta a zero. In questo modo l'avversario si trova in una posizione perdente.
Oltre il Nim: i numeri di Grundy
Per gli altri giochi imparziali usiamo un numero di Grundy per ogni stato. Questo generalizza l'idea del nim-sum a quasi tutti i giochi di rimozione.
L'operazione mex
Il valore di Grundy di uno stato è il suo mex: il più piccolo intero non negativo assente tra i valori di Grundy delle sue mosse.
def mex(s):
i = 0
while i in s:
i += 1
return iCalcolare Grundy con la ricorsione
Applichi la ricorsione a tutti gli stati raggiungibili, raccolga i relativi valori di Grundy e poi calcoli il mex di quell'insieme.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy zero significa sconfitta
Un singolo stato di gioco con Grundy 0 è una posizione perdente, proprio come un nim-sum pari a zero. Un valore diverso da zero indica una vittoria.
Il teorema di Sprague-Grundy
Per giochi indipendenti giocati contemporaneamente, calcoli lo XOR dei relativi numeri di Grundy. Questo risultato di Sprague-Grundy trasforma qualunque somma di giochi in Nim. ✨
Quando si applica
La teoria di Grundy richiede un gioco imparziale: entrambi i giocatori hanno le stesse mosse e vince chi effettua l'ultima. Lo verifichi prima di applicarla.
Verifica rapida
Inizia una partita di Nim con i mucchi 1, 2 e 3. Si trova in una posizione vincente?
Riepilogo
Il Nim dipende dallo XOR dei mucchi: zero significa sconfitta, un valore diverso da zero significa vittoria. I numeri di Grundy e il mex estendono questa idea a molti giochi imparziali. 🏆
Domande Frequenti
La lezione «Nim e numero di Grundy» è gratuita?
Sì — il testo completo di «Nim e numero di Grundy» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Nim e numero di Grundy»?
Risolvere giochi imparziali con XOR Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Nim e numero di Grundy»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Stati vincenti e perdenti nei giochi
- Nim e numero di Grundy
- Meet in the Middle
- Debug rapido: stress test e triage