Nim y el número de Grundy
Resuelva juegos imparciales con XOR
Nim y el número de Grundy es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Conozca el juego de Nim
En Nim hay varias pilas de piedras. En su turno puede retirar cualquier cantidad de una pila, y gana quien retira la última piedra. 🪨
La cantidad mágica: XOR
El juego completo se decide mediante el XOR de los tamaños de todas las pilas. Ese único número indica quién está ganando.
La regla de la nim-sum
Si el XOR de las pilas, llamado nim-sum, es cero, pierde el jugador al que le toca mover. Si no es cero, ese jugador gana.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pPor qué cero trae problemas
Desde una nim-sum igual a cero, cualquier movimiento rompe el equilibrio y deja al oponente una suma distinta de cero que siempre puede restaurar.
Encontrar el movimiento ganador
Cuando la nim-sum no es cero, siempre existe un movimiento que la devuelve a cero. Ese movimiento deja al oponente en una posición perdedora.
Más allá de Nim: números de Grundy
Para otros juegos imparciales usamos un número de Grundy por estado. Esto generaliza la idea de la nim-sum a casi cualquier juego de retirar elementos.
La operación mex
El valor de Grundy de un estado es el mex: el menor entero no negativo que falta entre los valores de Grundy de sus movimientos.
def mex(s):
i = 0
while i in s:
i += 1
return iCalcular Grundy mediante recursión
Explore recursivamente todos los estados alcanzables, reúna sus valores de Grundy y después calcule el mex de ese conjunto.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy cero es una derrota
Un estado con Grundy 0 es una posición perdedora, exactamente igual que una nim-sum igual a cero. Un valor distinto de cero significa una victoria.
El teorema de Sprague-Grundy
Para juegos independientes que se juegan a la vez, calcule el XOR de sus números de Grundy. Este resultado de Sprague-Grundy convierte cualquier suma de juegos en Nim. ✨
Cuándo se aplica
La teoría de Grundy requiere un juego imparcial: ambos jugadores tienen los mismos movimientos y gana quien mueve en último lugar. Compruébelo antes de utilizarla.
Comprobación rápida
Comienza una partida de Nim con pilas de 1, 2 y 3 piedras. ¿Está ganando?
Repaso
Nim depende del XOR de las pilas: con cero se pierde y con un valor distinto de cero se gana. Los números de Grundy y mex extienden esta idea a muchos juegos imparciales. 🏆
Preguntas frecuentes
¿La lección «Nim y el número de Grundy» es gratis?
Sí — el texto completo de «Nim y el número de Grundy» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Nim y el número de Grundy»?
Resuelva juegos imparciales con XOR Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Nim y el número de Grundy»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Estados ganadores y perdedores en juegos
- Nim y el número de Grundy
- Meet in the Middle
- Depure rápido: pruebas de estrés y triaje