Nim et le nombre de Grundy
Résoudre les jeux impartiaux avec XOR
Nim et le nombre de Grundy est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Découvrez le jeu de Nim
Dans Nim, plusieurs tas de pierres sont disposés devant vous. À votre tour, retirez autant de pierres que vous le souhaitez d’un seul tas ; le joueur qui prend la dernière pierre gagne. 🪨
La quantité magique : XOR
Tout le jeu est déterminé par le XOR des tailles de tous les tas. Ce nombre unique indique qui est en position de gagner.
La règle de la somme de Nim
Si le XOR des tas, appelé la somme de Nim, vaut zéro, le joueur dont c’est le tour perd. S’il est différent de zéro, ce joueur gagne.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pPourquoi zéro annonce des difficultés
À partir d’une somme de Nim nulle, chaque coup rompt l’équilibre et donne à l’adversaire une somme non nulle qu’il peut toujours rétablir.
Trouver le coup gagnant
Lorsque la somme de Nim est non nulle, il existe toujours un coup qui la ramène à zéro. Ce coup place votre adversaire dans une position perdante.
Au-delà de Nim : les nombres de Grundy
Pour les autres jeux impartiaux, nous utilisons un nombre de Grundy par état. Il généralise l’idée de somme de Nim à presque tous les jeux de retrait.
L’opération mex
La valeur de Grundy d’un état est le mex : le plus petit entier non négatif absent des valeurs de Grundy de ses coups.
def mex(s):
i = 0
while i in s:
i += 1
return iCalculer Grundy par récursion
Lancez une récursion sur tous les états atteignables, rassemblez leurs valeurs de Grundy, puis prenez le mex de cet ensemble.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Un Grundy nul est une défaite
Un état de jeu dont le Grundy vaut 0 est une position perdante, exactement comme une somme de Nim nulle. Une valeur non nulle signifie une victoire.
Le théorème de Sprague-Grundy
Pour des jeux indépendants joués simultanément, faites le XOR de leurs nombres de Grundy. Ce résultat de Sprague-Grundy transforme toute somme de jeux en une partie de Nim. ✨
Quand l’utiliser
La théorie de Grundy nécessite un jeu impartial : les deux joueurs disposent des mêmes coups et le dernier à jouer gagne. Vérifiez ce point avant de l’utiliser.
Vérification rapide
Vous commencez une partie de Nim avec des tas de 1, 2 et 3 pierres. Êtes-vous en position de gagner ?
Récapitulatif
Nim repose sur le XOR des tas : zéro signifie une défaite, une valeur non nulle une victoire. Les nombres de Grundy et mex étendent cette idée à de nombreux jeux impartiaux. 🏆
Questions Fréquemment Posées
La leçon « Nim et le nombre de Grundy » est-elle gratuite ?
Oui — le texte complet de « Nim et le nombre de Grundy » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Nim et le nombre de Grundy » ?
Résoudre les jeux impartiaux avec XOR Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Nim et le nombre de Grundy » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- États gagnants et perdants dans les jeux
- Nim et le nombre de Grundy
- Diviser pour mieux régner au milieu
- Déboguer rapidement : tests de contrainte et triage