Estados Vencedores e Perdedores em Jogos
Descubra quem vence com jogadas ideais.
Estados Vencedores e Perdedores em Jogos é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Dois jogadores, jogo perfeito
Em um jogo combinatório, dois jogadores alternam movimentos, ambos jogam perfeitamente e quem não puder se mover perde. Sua tarefa é apenas prever o vencedor. 🎯
Cada posição tem um rótulo
Cada posição do jogo é um estado. Sua tarefa é rotular cada estado como vitória ou derrota para o jogador que deve jogar.
O significado de um estado vencedor
Um estado é um estado vencedor se o jogador da vez tiver pelo menos um movimento que leve a um estado perdedor para o adversário.
O significado de um estado perdedor
Um estado é um estado perdedor quando cada movimento que você fizer entrega ao adversário um estado vencedor. Você fica sem saída, não importa o que faça.
O caso-base
A posição em que você não pode fazer movimento algum é o caso-base. O jogador que se depara com ela já perdeu, então rotule-a como derrota.
Construindo a partir do fim
Comece pelos casos-base e avance para fora deles. O rótulo de cada novo estado depende apenas dos estados aos quais seus movimentos levam.
Um bom movimento basta
Para vencer, você precisa apenas de um movimento para um estado perdedor do adversário. Encontrar qualquer rota de escape já é suficiente.
Um pequeno exemplo
Retire 1 ou 2 pedras de uma pilha; quem retirar a última vence. Com 0 pedras, o jogador da vez perde, então essa é uma posição perdedora.
Programe a verificação de vitória
Essa recursão rotula um estado testando cada movimento e aplicando a recursão ao resultado. ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))Memorize para manter a velocidade
Os estados se repetem entre os ramos, então armazene cada resultado em cache. Uma simples memorização transforma o trabalho exponencial em tempo linear.
from functools import lru_cache
@lru_cache(None)
def win(n):
return n != 0 and any(not win(n - k) for k in (1, 2))A simetria é um atalho
Se uma posição for perfeitamente simétrica, o segundo jogador muitas vezes poderá espelhar os movimentos e vencer. Fique atento a esse truque de espelhamento.
Verificação rápida
Você se depara com um estado. Quando ele é um estado perdedor para você?
Recapitulação
Agora você rotula os estados: um win tem um movimento para uma derrota do adversário, enquanto uma derrota não tem nenhum. Construa a partir dos casos-base e use memorização. 🧠
Perguntas Frequentes
A aula “Estados Vencedores e Perdedores em Jogos” é grátis?
Sim — o texto completo de “Estados Vencedores e Perdedores em Jogos” é 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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Estados Vencedores e Perdedores em Jogos”?
Descubra quem vence com jogadas ideais. Você pratica Coding Interview Prep 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep 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 1 de 4.
Quanto tempo leva a aula “Estados Vencedores e Perdedores em Jogos”?
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 Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep 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