Escreva um programa que calcule o menor número de notas e de moedas que deve ser dado de troco para um pagamento efetuado. O programa deve ler o valor a ser pago e o valor efetivamente pago. Supor que o troco seja dado em notas de 50,20 e 10 reais, nota ou moeda de 1 real, e em moedas de
e 1 centavos.
Passo 1
O enunciado pede que a gente escreva um programa que calcule o menor número de notas e moedas que deve ser entregue como troco quando alguém paga um valor maior que o preço. As informações relevantes estão todas aqui:
- O programa deve ler dois valores: o valor a ser pago e o valor efetivamente pago.
- O troco deve ser dado usando apenas as denominações abaixo:
- notas de
, , reais; - nota ou moeda de
real; - moedas de
, , e real.
- notas de
- A saída do programa deve indicar quantas notas/moedas de cada denominação serão entregues, usando o menor número total possível de itens (notas+moedas).
Isso é tudo que o enunciado dá e pede. Agora vamos ver como implementar isso passo a passo.
Passo 2
Escolha do método (ideia principal).
Vou usar o método guloso (greedy): sempre pegar o maior número possível da maior denominação que não exceda o troco restante, depois passar para a próxima menor denominação, e assim por diante.
Por exemplo, se o troco for
reais, eu tento tirar quantas notas de
cabem; depois, com o restante, quantas de
; e assim por diante.
Por que o método guloso funciona aqui?
- Essas denominações formam o conjunto típico de cédulas e moedas de uma moeda corrente: existe uma denominação de
real (ou seja, a unidade), e as notas/coins maiores são múltiplos compatíveis de valores menores de forma que trocar uma nota grande por várias menores nunca reduz o número total de itens. Intuitivamente: uma nota de vale muito mais que qualquer combinação de notas menores sem usar pelo menos duas ou três itens; trocar uma nota de por várias notas menores aumenta o número de itens. Para esse conjunto específico de denominações a estratégia gulosa é ótima (é o comportamento esperado para sistemas monetários “canônicos” como esse). - Na prática, para moedas e notas correntes (com
presente e denominações bem escolhidas) a solução gulosa é a ótima, então usamos essa estratégia — ela é simples e eficiente.
Passo 3
Tratamento de valores decimais e precisão (ponto crucial).
Problema clássico: usar números de ponto flutuante (float) pode levar a erros de precisão (por exemplo
em ponto flutuante não é exato). Para evitar qualquer erro com centavos, convertemos tudo para centavos e trabalhamos com inteiros. Ou seja:
- Representamos quaisquer valores em reais como uma quantidade inteira de centavos.
- Se o valor em reais é
, o valor em centavos é . - Assim, as denominações (em centavos) serão:
Aqui, por exemplo, reais = centavos, real = centavos, e assim por diante.
Para transformar a entrada textual (que pode vir com ponto ou vírgula decimal) em centavos sem erro, usaremos aritmética decimal exata (por exemplo a classe Decimal em Python), arredondando para dois dígitos depois da vírgula antes de multiplicar por
.
Passo 4
Algoritmo detalhado passo a passo (pseudo-ação que você pode executar na prova mentalmente):
- Ler as duas entradas:
e . - Converter ambas para centavos inteiros:
onde
significa arredondar para duas casas decimais (usando arredondamento bancário ou half-up).
3. Calcular o troco em centavos:
3. Calcular o troco em centavos:
- Se
: pagamento insuficiente (não há troco — você pode sinalizar erro). - Se
: sem troco.
- Aplicar o método guloso: para cada denominação
na lista calcular e atualizar - Ao final, você terá as quantidades mínimas para cada denominação.
Passo 5
Exemplo numérico manual (para fixar e saber fazer rápido na prova):
Suponha
e
.
- Converter para centavos:
- Troco:
ou seja, reais. - Aplicando as denominações:
-
: nota de . Resto . -
: nota de . Resto . -
: notas de . Resto . -
: de real. Resto . -
: moeda de . Resto . -
: moeda de . Resto . -
: . Resto . -
: moedas de . Resto .
-
- Resultado: 1 nota de
, 1 de , 0 de , 2 de , 1 de , 1 de , 0 de e 3 de .
Esse exemplo mostra passo a passo como executar as divisões e restos, operação por operação — exatamente o que você fará no programa.
Passo 6
Como implementar no computador (detalhes práticos e robustez).
- Use leitura tolerante (aceita ponto ou vírgula decimal).
- Use aritmética decimal exata para não ter problemas de precisão (por exemplo, a classe Decimal em Python).
- Converta para centavos inteiros e aplique o algoritmo guloso com divisão inteira e resto.
- Trate os casos
(pagamento insuficiente) e (sem troco) se desejar — ou apenas imprimir zeros para cada denominação se preferir.
Abaixo eu forneço um programa em Python que faz tudo isso de forma clara e imprimível. Você pode copiar e rodar em qualquer ambiente que suporte Python 3.
Resposta
from decimal import Decimal, ROUND_HALF_UP, getcontext
import sys
# Precisão suficiente para operações com duas casas
getcontext().prec = 28
def str_to_cents(s):
# aceita vírgula ou ponto como separador decimal
s = s.strip().replace(',', '.')
d = Decimal(s)
# arredonda para 2 casas (meio para cima) e converte para centavos inteiros
d = d.quantize(Decimal('0.01'), rounding=ROUND_HALF_UP)
cents = int((d * 100).to_integral_value(rounding=ROUND_HALF_UP))
return cents
def main():
data = sys.stdin.read().strip().split()
if len(data) < 2:
# se não vier dois valores, tentar pedir por input (modo interativo)
try:
preco_s = input("Valor a ser pago: ").strip()
pago_s = input("Valor pago: ").strip()
except EOFError:
print("Erro: entrada insuficiente.")
return
else:
preco_s = data[0]
pago_s = data[1]
try:
preco_cent = str_to_cents(preco_s)
pago_cent = str_to_cents(pago_s)
except Exception as e:
print("Erro ao ler valores:", e)
return
troco = pago_cent - preco_cent
if troco < 0:
print("Pagamento insuficiente")
return
# denominações em centavos, em ordem decrescente
denoms = [
(5000, "nota(s) de R$50,00"),
(2000, "nota(s) de R$20,00"),
(1000, "nota(s) de R$10,00"),
(100, "nota(s)/moeda(s) de R$1,00"),
(50, "moeda(s) de R$0,50"),
(10, "moeda(s) de R$0,10"),
(5, "moeda(s) de R$0,05"),
(1, "moeda(s) de R$0,01"),
]
results = []
restante = troco
for value, label in denoms:
qtd = restante // value
restante -= qtd * value
results.append((qtd, label))
# Impressão dos resultados
for qtd, label in results:
print(f"{qtd} {label}")
if __name__ == "__main__":
main()