O jeito que realmente funciona para resolver exercícios de dar troco
A primeira coisa que quase todo mundo faz errado é começar tentando adivinhar quantas moedas precisam ser usadas. Isso funciona em problemas pequenos de livro didático, mas quando o troco sobe para valores como R$ 97,00 ou R$ 193,50, o método falha rápido. Eu já vi gente passar vinte minutos num único exercício desse tipo só porque insistia na abordagem intuitiva. O problema central em exercicios para dar troco é que eles testam dois conceitos distintos: o algoritmo guloso (greedy) e a programação dinâmica. A maior parte dos materiais que você encontra na internet trata apenas do primeiro, o que é suficiente para provas do ensino médio, mas insuficiente para qualquer coisa que se aproxime de um contexto real ou de uma competição de algoritmos.
exercicios para dar troco: o que realmente importa dominar
Pegar as notas e moedas de maior valor primeiro e ir reduzindo o troco até zerar. Esse é o algoritmo guloso. Para o sistema monetário brasileiro, ele funciona perfeitamente na maioria dos casos práticos porque as nossas denominações -- 1, 2, 5, 10, 20, 50, 100 -- foram justamente construídas de forma que o guloso sempre entrega a solução ótima. Isso não é universal. Se um dia você precisar implementar um caixa para uma moeda fictícia com denominações como 1, 3 e 4 reais, o guloso vai falhar. Para dar 6 reais, ele escolhe 4 + 1 + 1, que são três moedas, enquanto a resposta correta é 3 + 3, apenas duas. A programação dinâmica resolve isso. Você constrói uma tabela onde cada posição armazena o menor número de moedas necessário para atingir aquele valor. A complexidade é O(n * V), onde n é o número de denominações disponíveis e V é o valor do troco. Em problemas mais simples, esse overhead é desnecessário, mas quando as restrições do enunciado aumentam -- valores de troco acima de mil reais ou conjuntos de moedas personalizados -- é a única abordagem segura.
O que as pessoas normalmente não entendem é quando usar cada um. Se o exercício pede o troco com as moedas brasileiras padrão e o valor está dentro de uma faixa razoável, o guloso é mais rápido de escrever e mais fácil de depurar. Ele roda em tempo constante na prática porque o número de denominações é fixo e pequeno. A programação dinâmica é mais lenta na escrita e consome memória proporcional ao valor do troco, mas garante corretude mesmo com conjuntos de moedas malucos. Um detalhe que aparece todo ano em listas de exercícios e que gera confusão desnecessária: o troco pode ser zero. Isso acontece quando o valor pago é exatamente igual ao preço. O resultado esperado é sempre uma lista vazia ou um contador zerado, dependendo de como o exercício pede a saída. Já vi gente tratar esse caso como exceção e complicar a lógica desnecessariamente. Trate zero como entrada válida desde o início e evite condições especiais depois.
Outro ponto que merece atenção é a leitura dos dados. Exercícios de dar troco frequentemente vêm com múltiplos casos de teste. O padrão mais comum é ler até o final da entrada ou até encontrar um valor sentinela como zero. Se você não tratar isso no código, o programa pode travar ou processar entradas extras. Isso é mais frequente do que deveria em listas enviadas por professores que copiam exercícios de fontes internacionais sem adaptar para o padrão brasileiro de entrada. Eu tive um problema específico recentemente com uma lista que usava moedas em centavos sem vírgula -- o troco era dado como 97 representando 97 centavos, mas as moedas vinham em reais. Fui perder uns quinze minutos confirmando se era um bug no meu código ou uma pegadinha no enunciado antes de perceber que precisava converter tudo para a menor unidade antes de rodar qualquer algoritmo. A lição prática é: normalize todas as entradas para a mesma unidade antes de começar.
implementação prática com o algoritmo guloso
O código é simples. Você cria um array com as denominações em ordem decrescente, itera sobre elas e a cada etapa divide o troco restante pelo valor da moeda atual. O quociente é a quantidade daquela moeda, e o resto vira o novo troco a ser processado. Quando o troco chega a zero, você para. Em Python, por exemplo, ficaria algo próximo disso: pegar as denominações [100, 50, 20, 10, 5, 2, 1], fazer um loop com divisão inteira e módulo, e armazenar os resultados. Funciona, é legível, e resolve praticamente todo exercício que você vai encontrar em material didático brasileiro. Se o professor pedir para usar exatamente esse algoritmo, não insista em implementar programação dinâmica só para demonstrar conhecimento. Você vai ganhar tempo e evitar bugs desnecessários.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Se quiser o código completo ou exemplos prontos para rodar, dá para encontrar em repositórios de competições de programação com buscas diretas. O importante é entender o padrão antes de copiar, senão na hora de adaptar para variações do exercício você vai travar.
quando o guloso não é suficiente
Se o exercício mencionar explicitamente que as moedas podem ser arbitrarias ou se o valor do troco for parte de uma entrada maior onde a otimalidade é obrigatória, a programação dinâmica entra em cena. A ideia básica é manter um vetor dp onde dp[i] guarda o mínimo de moedas para o valor i. Você inicializa dp[0] como zero e todos os outros como infinito. Em seguida, para cada valor de i de 1 até V, você testa cada moeda disponível e atualiza dp[i] se encontrar uma combinação melhor. O custo adicional é real. Para um troco de R$ 500,00 com denominações em centavos, você termina com um vetor de 50.000 posições. Em linguagens interpretadas isso pode levar alguns segundos se não houver otimização. Em linguagens compiladas como C++ ou Rust, é praticamente instantâneo. Se o exercício permite Python e o valor é grande, considere usar uma lista com type hint ou até mesmo um array do módulo array para reduzir overhead de memória.
Existe também uma terceira via que poucos materiais citam: branch and bound com poda. Ela é útil quando o conjunto de moedas é grande e o valor do troco é muito alto, mas você não quer o custo completo da programação dinâmica. Você explora as combinações de cima para baixo e descarta ramos que já ultrapassaram uma solução conhecida. Funciona bem em cenários competitivos, mas é overkill para a maioria dos exercícios acadêmicos. O erro mais comum em programação dinâmica aplicada a troco é inicializar mal a tabela. Se você colocar zero em todas as posições em vez de infinito, o algoritmo vai propagar zeros e entregar resultados absurdos. Isso acontece com frequência porque quem está aprendendo tende a pensar nos valores como quantidades válidas desde o início, quando na verdade precisam ser marcados como inacessíveis até serem computados corretamente.
dicas que realmente ajudam na prática
Primeiro, sempre verifique se o troco pode ser formado com as moedas disponíveis. Se o menor denominador for 5 e o troco terminar em 3, é impossível. Nesses casos, a resposta correta do exercício costuma ser algo como -1 ou uma mensagem de impossibilidade. Trate isso antes de rodar qualquer algoritmo e economiza processamento. Segundo, escreva o código de forma modular. Separe a função que calcula o troco da função que lê a entrada e imprime a saída. Isso facilita testar com valores fixos antes de submeter e torna mais fácil identificar onde o erro está quando o resultado não bate.
Terceiro, use cases de borda no seu teste local. Troco zero, troco menor que a menor moeda, troco exatamente igual a uma moeda, troco que exige muitas moedas pequenas. Se o seu código passa nesses casos, a chance de passar no exercício principal é alta. Quarto, não se apegue a uma única linguagem. O algoritmo guloso é tão simples que implementar em C, Python ou JavaScript leva o mesmo tempo. Se um judge não aceita Python por timeout, migre para C++ rápido. Perder tempo otimizando uma implementação ruim em vez de trocar de linguagem é um erro comum de quem está começando.
O problema de depender só de exercícios prontos é que eles criam uma falsa sensação de domínio. Você consegue resolver os dados de teste do material, mas quando a banca muda as regras -- por exemplo, pedindo para listar todas as combinações possíveis em vez da ótima -- trava. Treine variar o requisito do exercício antes de considerar que dominou o assunto.
