Nim e o Número de Grundy
Resolva jogos imparciais com XOR.
Nim e o Número de Grundy é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Conheça o jogo Nim
Em Nim, há várias pilhas de pedras. Na sua vez, você remove qualquer quantidade de uma pilha, e vence o jogador que retirar a última pedra. 🪨
A quantidade mágica: XOR
O jogo inteiro é decidido pelo XOR dos tamanhos de todas as pilhas. Esse único número informa quem está vencendo.
A regra da soma de Nim
Se o XOR das pilhas, chamado de soma de Nim, for zero, o jogador da vez perde. Se for diferente de zero, esse jogador vence.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pPor que zero significa problema
A partir de uma soma de Nim zero, qualquer movimento quebra o equilíbrio e entrega ao adversário uma soma diferente de zero, que ele sempre consegue restaurar.
Encontrando o movimento vencedor
Quando a soma de Nim é diferente de zero, sempre existe um movimento que a leva de volta a zero. Esse movimento coloca o adversário em uma posição perdedora.
Além de Nim: números de Grundy
Para outros jogos imparciais, usamos um número de Grundy por estado. Ele generaliza a ideia da soma de Nim para quase qualquer jogo de remoção.
A operação mex
O valor de Grundy de um estado é o mex: o menor inteiro não negativo ausente entre os valores de Grundy de seus movimentos.
def mex(s):
i = 0
while i in s:
i += 1
return iCalculando Grundy por recursão
Aplique a recursão a todos os estados alcançáveis, reúna seus valores de Grundy e então calcule o mex desse conjunto.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy zero é derrota
Um estado de jogo com Grundy 0 é uma posição perdedora, exatamente como uma soma de Nim igual a zero. Um valor diferente de zero significa vitória.
O teorema de Sprague-Grundy
Para jogos independentes disputados ao mesmo tempo, calcule o XOR de seus números de Grundy. Esse resultado de Sprague-Grundy transforma qualquer soma de jogos em Nim. ✨
Quando ele se aplica
A teoria de Grundy exige um jogo imparcial: os dois jogadores têm os mesmos movimentos e vence quem fizer o último movimento. Verifique isso antes de usá-la.
Verificação rápida
Você começa um jogo de Nim com pilhas de 1, 2 e 3 pedras. Está vencendo?
Recapitulação
Nim depende do XOR das pilhas: zero significa derrota, e um valor diferente de zero significa vitória. Os números de Grundy e o mex ampliam essa ideia para muitos jogos imparciais. 🏆
Aprenda Python com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 30
- Aulas
- 120
Perguntas Frequentes
A aula “Nim e o Número de Grundy” é grátis?
Sim — o texto completo de “Nim e o Número de Grundy” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Nim e o Número de Grundy”?
Resolva jogos imparciais com XOR. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Nim e o Número de Grundy”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Estados Vencedores e Perdedores em Jogos
- Nim e o Número de Grundy
- Encontro no Meio
- Depure Rapidamente: Testes de Estresse e Triagem