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 50,10,5 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 \,50, \,20, \,10 reais;
    • nota ou moeda de \,1 real;
    • moedas de \,0{,}50, \,0{,}10, \,0{,}05 e \,0{,}01 real.
  • 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 \,72{,}63 reais, eu tento tirar quantas notas de \,50 cabem; depois, com o restante, quantas de \,20; 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 \,1 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 \,50 vale muito mais que qualquer combinação de notas menores sem usar pelo menos duas ou três itens; trocar uma nota de \,50 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 \,1 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 \,0{,}1 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 é x, o valor em centavos é 100 \cdot x.
  • Assim, as denominações (em centavos) serão: \text{denominações} = [5000,\,2000,\,1000,\,100,\,50,\,10,\,5,\,1].çõAqui, por exemplo, \,50 reais = 5000 centavos, \,0{,}50 real = 50 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 100.

Passo 4

Algoritmo detalhado passo a passo (pseudo-ação que você pode executar na prova mentalmente):
  1. Ler as duas entradas: \text{preco} e \text{pago}.
  2. Converter ambas para centavos inteiros: \text{preco\_cent} = \text{arredonda2}(\text{preco}) \times 100,
\text{pago\_cent} = \text{arredonda2}(\text{pago}) \times 100,
onde \text{arredonda2} significa arredondar para duas casas decimais (usando arredondamento bancário ou half-up).
3. Calcular o troco em centavos:
\text{troco\_cent} = \text{pago\_cent} - \text{preco\_cent}.
  • Se \text{troco\_cent} < 0: pagamento insuficiente (não há troco — você pode sinalizar erro).
  • Se \text{troco\_cent} = 0: sem troco.
  1. Aplicar o método guloso: para cada denominação d na lista [5000,\,2000,\,1000,\,100,\,50,\,10,\,5,\,1],calcular \text{quantidade} = \left\lfloor\frac{\text{troco\_cent}}{d}\right\rfloore atualizar \text{troco\_cent} \leftarrow \text{troco\_cent} - \text{quantidade}\cdot d.
  2. 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 \text{preco} = 27{,}37 e \text{pago} = 100{,}00.
  1. Converter para centavos: \text{preco\_cent} = 27{,}37 \times 100 = 2737
\text{pago\_cent} = 100{,}00 \times 100 = 10000
  1. Troco: \text{troco\_cent} = 10000 - 2737 = 7263ou seja, \,72{,}63 reais.
  2. Aplicando as denominações:
    • 5000: \lfloor 7263/5000\rfloor = 1 nota de \,50. Resto 7263-1\cdot5000=2263.
    • 2000: \lfloor 2263/2000\rfloor = 1 nota de \,20. Resto 2263-2000=263.
    • 1000: \lfloor 263/1000\rfloor = 0 notas de \,10. Resto 263.
    • 100: \lfloor 263/100\rfloor = 2 de \,1 real. Resto 263-2\cdot100=63.
    • 50: \lfloor 63/50\rfloor = 1 moeda de \,0{,}50. Resto 63-50=13.
    • 10: \lfloor 13/10\rfloor = 1 moeda de \,0{,}10. Resto 13-10=3.
    • 5: \lfloor 3/5\rfloor = 0. Resto 3.
    • 1: \lfloor 3/1\rfloor = 3 moedas de \,0{,}01. Resto 0.
  3. Resultado: 1 nota de \,50, 1 de \,20, 0 de \,10, 2 de \,1, 1 de \,0{,}50, 1 de \,0{,}10, 0 de \,0{,}05 e 3 de \,0{,}01.
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 \text{troco\_cent} < 0 (pagamento insuficiente) e \text{troco\_cent} = 0 (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()

Exercícios relacionados