(0.5) Você sabe que existem notas de
2,00, R $5,00, R $ 10,00, R $20,00, R $ 50,00
\mathrm{R} $100,00
\mathrm{R} $ 1,00
\mathrm{R} $10,00
\mathrm{R} $ 100,00
\mathrm{R} $35,00
\mathrm{R} $ 50,00
\mathrm{R} $1,00
\mathrm{R} $ 2,00
\mathrm{R} $1,00
\mathrm{R} $ 5,00
\mathrm{R} $5,00
\mathrm{R} $ 10,00
R $10,00+R $ 5,00$ ).
Passo 1
O que o problema pede e os dados que temos:
- Temos as cédulas/moeda disponíveis com valores:
, , , , , e a moeda de . - O preço da compra é um inteiro entre
e (mas vamos deixar o programa funcionando para qualquer inteiro não negativo). - O pagamento é um inteiro maior ou igual ao preço.
- O objetivo: calcular o troco (pagamento menos preço) e devolver uma combinação de cédulas/moedas que use o menor número possível de peças (mínimo número de notas/ moedas).
O que o enunciado pergunta explicitamente:
- Implementar um programa em Python que, dados preço e pagamento (inteiros), calcule o troco e retorne a decomposição nesse conjunto de cédulas/moeda usando o menor número de peças possível.
Passo 2
Que método escolher e por quê (explicação didática do método):
- Aqui o objetivo é minimizar o número de peças para representar um inteiro não negativo (o troco) usando um conjunto fixo de valores. Uma estratégia natural é o algoritmo guloso: sempre pegar a maior cédula/ moeda possível enquanto ainda couber no troco restante, e repetir com o restante.
- O algoritmo guloso funciona assim, em palavras simples:
- Ordene as cédulas da maior para a menor: por exemplo,
. - Para cada cédula
nessa ordem, pegue o máximo número inteiro de cédulas de valor que caibam no troco restante, subtraia esse total do troco e passe para a próxima cédula.
- Ordene as cédulas da maior para a menor: por exemplo,
- Por que usar essa abordagem? Porque para o sistema de cédulas dado (o conjunto clássico usado no enunciado) o algoritmo guloso produz sempre uma solução com o menor número de peças. Vou explicar porquê com um argumento por troca simples e intuitivo:
- Pense na maior cédula,
. Se o troco tem pelo menos , pegar o máximo possível de notas de não pode aumentar o número de peças em comparação a qualquer solução que não pegue essas notas: para substituir uma nota de seriam necessárias várias notas menores (pelo menos duas ou mais), logo trocar uma nota de por notas menores só aumentaria o número de peças. Assim, tomar o máximo de é seguro. - Mesmo raciocínio vale para
: para formar com valores menores precisa-se de pelo menos 2 ou 3 peças (por exemplo, duas e uma = 3 peças), então usar uma é sempre tão bom ou melhor do ponto de vista do número de peças. - Para
e : substituir uma por duas mantém o mesmo número de peças; substituições que usariam apenas moedas menores resultariam em mais peças. Para manter o número mínimo não há ganho em evitar usar uma quando ela cabe. - Para
e : substituir uma precisa de pelo menos 3 peças com e (por exemplo, ), então usar uma é melhor. Substituir uma por duas mantém o número de peças. - Em resumo: cada cédula maior não pode ser substituída por uma combinação de menores que use menos peças; no pior caso a substituição usa o mesmo número, na maioria dos casos usa mais. Portanto o método guloso é seguro para esse conjunto de cédulas e garante o mínimo global de peças.
- Pense na maior cédula,
- Observação prática: esse é o método usado por caixas em lojas e é rápido de aplicar à mão (útil na prova) e trivial de implementar em Python.
Passo 3
Desenvolvendo o algoritmo passo a passo (aula prática de como fazer na prova):
- Passo 3.1: Calcule o troco:
- Seja o preço
e o pagamento . O troco é . - Se
, não há troco; fim. - Se
, erro: pagamento insuficiente.
- Seja o preço
- Passo 3.2: Organize as cédulas em ordem decrescente:
- Vetor
.
- Vetor
- Passo 3.3: Para cada denominação
em : - Calcule quantas cédulas de
cabem no troco atual: (divisão inteira). - Registre
como número de peças de valor . - Atualize o troco:
. - Passe para a próxima denominação.
- Calcule quantas cédulas de
- Depois de passar por todas as denominações, o troco restante será zero e a lista de contagens dará a solução com o menor número de peças.
- Dica para a prova: faça a divisão inteira e o resto à mão — por exemplo, para troco
: , (resto ), (resto ), (resto ), (resto ), (resto ). Resultado: peças.
Passo 4
Exemplo concreto (o exemplo do enunciado) e execução manual passo a passo:
- Exemplo: preço
e pagamento . - Troco:
. - Aplico o algoritmo guloso com
: -
→ resto . -
→ resto . -
→ resto . -
→ uso uma nota de , resto . -
→ uso uma nota de , resto .
-
- Resultado: uma nota de
e uma nota de → total de peças. Isso é melhor que usar quinze moedas de ou sete de + uma de , etc.
Passo 5
Complexidade e casos especiais:
- Complexidade: o algoritmo percorre um vetor fixo de 7 denominações, logo tempo O(1) (na prática linear no número de denominações). Memória O(1).
- Casos especiais:
- Se pagamento < preço: informe erro.
- Se preço ou pagamento não forem inteiros: o enunciado diz inteiros; o programa aqui assume inteiros. Em situações reais com centavos, transformar tudo para centavos (inteiro) antes de aplicar o mesmo algoritmo funciona.
- Boa prática: no código, trate entradas inválidas e imprima a decomposição apenas das denominações com contagem positiva para ficar legível.
Passo 6
Programa em Python (implementação fiel ao algoritmo explicado). O código abaixo lê preço e pagamento (inteiros), calcula o troco e imprime a decomposição com o menor número de peças:
def make_change(preco, pagamento):
"""
Retorna um dicionário {denominacao: qtd} representando a decomposição
do troco (pagamento - preco) usando o menor número de cédulas/moedas.
Supõe que preco e pagamento são inteiros (valores em reais, sem centavos).
"""
if pagamento < preco:
raise ValueError("Pagamento insuficiente: pagamento < preço.")
troco = pagamento - preco
denominacoes = [100, 50, 20, 10, 5, 2, 1]
contagens = {}
restante = troco
for d in denominacoes:
qtd = restante // d
contagens[d] = qtd
restante = restante - qtd * d
return troco, contagens
def imprime_troco(preco, pagamento):
try:
troco, contagens = make_change(preco, pagamento)
except ValueError as e:
print("Erro:", e)
return
print(f"Preço: R\({preco}, Pagamento: R\) {pagamento}, Troco: R$ {troco}")
total_pecas = 0
for d in [100, 50, 20, 10, 5, 2, 1]:
qtd = contagens[d]
if qtd:
print(f"{qtd} x R$ {d}")
total_pecas += qtd
print(f"Total de peças (cédulas/moedas): {total_pecas}")
# Exemplo de uso:
if __name__ == "__main__":
# Exemplo do enunciado:
preco = 35
pagamento = 50
imprime_troco(preco, pagamento)
# Para usar interativamente, descomente as linhas abaixo:
# preco = int(input("Preço (inteiro, R$): "))
# pagamento = int(input("Pagamento (inteiro, R$): "))
# imprime_troco(preco, pagamento)
Passo 7
Teste rápido e interpretação do resultado:
- Com o exemplo do enunciado (
, ), o programa imprime: - Troco:
-
x -
x - Total de peças:
- Troco:
- Outros testes:
-
, → troco → decomposição (total 5 peças), conforme o cálculo manual do Passo 3.
-
Resposta
def make_change(preco, pagamento):
"""
Retorna um dicionário {denominacao: qtd} representando a decomposição
do troco (pagamento - preco) usando o menor número de cédulas/moedas.
Supõe que preco e pagamento são inteiros (valores em reais, sem centavos).
"""
if pagamento < preco:
raise ValueError("Pagamento insuficiente: pagamento < preço.")
troco = pagamento - preco
denominacoes = [100, 50, 20, 10, 5, 2, 1]
contagens = {}
restante = troco
for d in denominacoes:
qtd = restante // d
contagens[d] = qtd
restante = restante - qtd * d
return troco, contagens
def imprime_troco(preco, pagamento):
try:
troco, contagens = make_change(preco, pagamento)
except ValueError as e:
print("Erro:", e)
return
print(f"Preço: R\({preco}, Pagamento: R\) {pagamento}, Troco: R$ {troco}")
total_pecas = 0
for d in [100, 50, 20, 10, 5, 2, 1]:
qtd = contagens[d]
if qtd:
print(f"{qtd} x R$ {d}")
total_pecas += qtd
print(f"Total de peças (cédulas/moedas): {total_pecas}")
# Exemplo de uso:
if __name__ == "__main__":
preco = 35
pagamento = 50
imprime_troco(preco, pagamento)