(2 pontos) Faça um programa que receba o valor de uma compra e o valor em dinheiro pago, nessa ordem. O programa deve escrever o valor do troco na primeira linha seguido da forma de dar o troco que gaste o menor número possível total de notas e moedas, descrevendo através de 13 linhas onde cada linha indica o número de unidades daquela cédula ou moeda.
A forma que gasta sempre o menor número total de notas e moedas, no caso do Brasil, é sempre usar a maior nota ou moeda disponível para o valor. Vejamos o exemplo dado:
  • \mathrm{R} \ 99,49 \rightarrow maior nota menor ou igual a esse valor éé\mathrm{R} $50,00 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00 restando mais\mathrm{R} $49,49$
  • R \ 49,49 \rightarrow maior nota menor ou igual a esse valor éé\mathrm{R} $20,00 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00 e 1 nota de\mathrm{R} $20,00 restando mais\mathrm{R} $ 29,49$
  • \mathrm{R} \ 29,49 \rightarrow maior nota menor ou igual a esse valor éé\mathrm{R} $20,00 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00 e 2 notas de\mathrm{R} $20,00 restando mais\mathrm{R} $ 9,49$
  • R \ 9,49 \rightarrow maior nota menor ou igual a esse valor éé\mathrm{R} $5,00 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00 e 1 nota de\mathrm{R} $ 5,00 restando mais\mathrm{R} $4,49$
  • \mathrm{R} \ 4,49 \rightarrow maior nota menor ou igual a esse valor éé\mathrm{R} $2,00 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00,1 nota de\mathrm{R} $ 5,00 e 1 nota de\mathrm{R} $2,00 restando mais\mathrm{R} $ 2,49$
  • \mathrm{R} \ 2,49 \rightarrow maior nota menor ou igual a esse valor éé\mathrm{R} $2,00 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00,1 nota de\mathrm{R} $ 5,00 e 2 notas de\mathrm{R} $2,00 restando mais\mathrm{R} $ 0,49$
  • \mathrm{R} \ 0,49 \rightarrow maior moeda menor ou igual a esse valor éé\mathrm{R} $0,25 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00,1 nota de\mathrm{R} $ 5,00,2 notas de\mathrm{R} $2,00 e 1 moeda de\mathrm{R} $ 0,25 restando mais\mathrm{R} $0,24$
  • \mathrm{R} \ 0,24 \rightarrow maior moeda menor ou igual a esse valor éé\mathrm{R} $0,10 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00,1 nota de\mathrm{R} $ 5,00,2 notas de\mathrm{R} $2,00,1 moeda de\mathrm{R} $ 0,25 e 1 moeda de\mathrm{R} $0,10 restando mais\mathrm{R} $ 0,14$
  • \mathrm{R} \ 0,14 \rightarrow maior moeda menor ou igual a esse valor éé\mathrm{R} $0,10 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00,1 nota de\mathrm{R} $ 5,00,2 notas de\mathrm{R} $2,00,1 moeda de\mathrm{R} $ 0,25 e 2 moedas de\mathrm{R} $0,10 restando mais\mathrm{R} $ 0,04$
  • \mathrm{R} \ 0,04 \rightarrow maior moeda menor ou igual a esse valor éé\mathrm{R} $0,01 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00,1 nota de\mathrm{R} $ 5,00,2 notas de\mathrm{R} $2,00,1 moeda de\mathrm{R} $ 0,25,2 moedas de\mathrm{R} $0,10 e 1 moeda de\mathrm{R} $ 0,01 restando mais\mathrm{R} $0,03$
  • \mathrm{R} \ 0,03 \rightarrow maior moeda menor ou igual a esse valor éé\mathrm{R} $0,01 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00,1 nota de\mathrm{R} $ 5,00,2 notas de\mathrm{R} $2,00,1 moeda de\mathrm{R} $ 0,25,2 moedas de\mathrm{R} $0,10 e 2 moedas de\mathrm{R} $ 0,01 restando mais\mathrm{R} $0,02$
  • \mathrm{R} \ 0,02 \rightarrow maior moeda menor ou igual a esse valor éé\mathrm{R} $0,01 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00,1 nota de\mathrm{R} $ 5,00,2 notas de\mathrm{R} $2,00,1 moeda de\mathrm{R} $ 0,25,2 moedas de\mathrm{R} $0,10 e 3 moedas de\mathrm{R} $ 0,01 restando mais\mathrm{R} $0,01$
  • \mathrm{R} \ 0,01 \rightarrow maior moeda menor ou igual a esse valor éé\mathrm{R} $0,01 , então até agora vamos usar 1 nota deãé\mathrm{R} $ 50,00,2 notas de\mathrm{R} $20,00,1 nota de\mathrm{R} $ 5,00,2 notas de\mathrm{R} $2,00,1 moeda de\mathrm{R} $ 0,25,2 moedas de\mathrm{R} $0,10 e 4 moedas de\mathrm{R} $ 0,01$ finalizando o cálculo do troco
DICA: Nesse exercício, lembre-se de que cálculos com números inteiros são mais precisos, de forma que usar float para muitos cálculos consecutivos pode levar a erros de precisão.

Passo 1

O enunciado pede que se faça um programa que:
  • receba dois valores em reais, na ordem: o valor da compra e o valor pago;
  • calcule o troco como a diferença entre o pago e a compra;
  • escreva, na primeira linha, o valor do troco;
  • em seguida, escreva a forma de pagar esse troco que use o menor número total possível de notas e moedas, descrevendo isso através de linhas onde cada linha indica o número de unidades daquela cédula ou moeda.
Informações relevantes dadas pelo enunciado:
  • O critério de otimização é usar o menor número total de notas e moedas; o enunciado instrui que isso se obtém sempre escolhendo, a cada passo, a maior nota/moeda possível menor ou igual ao valor restante (algoritmo guloso).
  • É sugerido que se evite erro de precisão usando inteiros em cálculos (por exemplo, trabalhar em centavos em vez de reais com ponto flutuante).
  • O exemplo de decomposição do troco \mathrm{R}\$\,99{,}49 mostrou um processo guloso, reduzindo o restante sempre pela maior cédula/moeda possível.
O que o programa precisa receber e produzir:
  • Entrada: dois valores (compra, pago).
  • Saída: primeira linha com o valor do troco e, em seguida, uma sequência de linhas (uma por denominação) com o número de unidades dessa denominação para compor o troco gastando o menor número de notas/ moedas.

Passo 2

Por que trabalhar com centavos (inteiros) e como fazer isso:
  • Números de ponto flutuante (float) podem introduzir erros de precisão em operações sucessivas (por exemplo, 0{,}1 não é exatamente representável em binário).
  • Estratégia segura: converter reais para centavos inteiros e fazer todas as operações com inteiros. Depois, ao imprimir o troco, voltar para formato com duas casas decimais.
  • Como converter: dado um valor em reais V (p.ex. V = 99{,}49), representa-se como centavos \mathrm{C} = \mathrm{round}(V \times 100). Em implementação robusta é melhor usar o tipo Decimal (Python) ou parsear a string para evitar problemas de arredondamento ao multiplicar floats.
Exemplo ilustrativo:
  • Se o troco em reais é \mathrm{R}\$\,99{,}49, em centavos isso é 9949 centavos.

Passo 3

Quais denominações usar (ordem decrescente) e como representá‑las em centavos:
  • Notas (em centavos): 100{,}00 \to 10000, 50{,}00 \to 5000, 20{,}00 \to 2000, 10{,}00 \to 1000, 5{,}00 \to 500, 2{,}00 \to 200.
  • Moedas (em centavos): 1{,}00 \to 100, 0{,}50 \to 50, 0{,}25 \to 25, 0{,}10 \to 10, 0{,}05 \to 5, 0{,}01 \to 1.
Como vetor em centavos (descendente):
\text{denoms} = [10000,\,5000,\,2000,\,1000,\,500,\,200,\,100,\,50,\,25,\,10,\,5,\,1].
Cada posição corresponde, respectivamente, a R\$100{,}00,\;R\$50{,}00,\;R\$20{,}00,\;\ldots,\;R\$0{,}01.

Passo 4

Descrição do algoritmo guloso (passo a passo matemático):
  • Seja C o troco em centavos (inteiro).
  • Para cada denominação d em \text{denoms} (da maior para a menor):
    • calcular o número de unidades dessa denominação por divisão inteira: q \;=\; \left\lfloor \dfrac{C}{d} \right\rfloor(em programação: q = C // d).
    • reduzir o restante: C \leftarrow C - q\cdot d.
  • Repetir até terminar todas as denominações. Ao final C deve ser 0 se o troco era um número que pode ser representado com as denominações (o que é verdade trabalhando em centavos).
Por que o guloso funciona aqui (intuição):
  • Para as denominações usuais de uma moeda moderna (como as listadas), pegar sempre a maior denominação possível não “bloqueia” soluções melhores posteriores — isto é, o sistema de denominações é canônico para o algoritmo guloso. Intuitivamente, usar uma nota maior substitui várias menores e reduz o número total de peças; em sistemas de moeda bem projetados isso leva ao mínimo de peças.

Passo 5

Como implementar de forma robusta em Python (explicando cada parte):
  • Ler as duas entradas como strings: entrada pode usar ponto ou vírgula decimal, então normalizar substituindo vírgula por ponto.
  • Usar Decimal para evitar problemas de precisão: multiplicar por 100 e arredondar para o inteiro mais próximo usando arredondamento half up.
  • Montar a lista de denominações em centavos (inteiros).
  • Aplicar o laço guloso para cada denominação, guardando o quociente q e atualizando o restante C.
  • Imprimir o troco formatado com duas casas decimais e as linhas com o número de unidades por denominação.
Explicação de variáveis (nome sugerido no código):
  • \text{compra\_dec}: valor da compra como Decimal.
  • \text{pago\_dec}: valor pago como Decimal.
  • \text{troco\_dec} = \text{pago\_dec} - \text{compra\_dec}: troco em Decimal (pode ser zero ou negativo).
  • \text{troco\_centavos}: inteiro representando o troco em centavos (positivo ou zero).
  • \text{denoms}: lista de denominações em centavos (inteiros).
  • Para cada denominação d: q = \text{troco\_centavos} // d, depois atualizar \text{troco\_centavos} -= q * d.

Passo 6

Exemplo prático (usando o troco do enunciado) — simulação detalhada:
  • Suponha que, após ler compra e pago, o troco calculado seja \mathrm{R}\$\,99{,}49. Em centavos:
    \text{troco\_centavos} = 9949.
  • Aplicando as denominações uma a uma:
    1. d=10000 ( R\$100{,}00): q=\lfloor 9949/10000\rfloor=0. Restante =9949.
    2. d=5000 ( R\$50{,}00): q=\lfloor 9949/5000\rfloor=1. Restante =9949-1\cdot5000=4949.
    3. d=2000 ( R\$20{,}00): q=\lfloor 4949/2000\rfloor=2. Restante =4949-2\cdot2000=949.
    4. d=1000 ( R\$10{,}00): q=\lfloor 949/1000\rfloor=0. Restante =949.
    5. d=500 ( R\$5{,}00): q=\lfloor 949/500\rfloor=1. Restante =949-1\cdot500=449.
    6. d=200 ( R\$2{,}00): q=\lfloor 449/200\rfloor=2. Restante =449-2\cdot200=49.
    7. d=100 ( R\$1{,}00): q=\lfloor 49/100\rfloor=0. Restante =49.
    8. d=50 ( R\$0{,}50): q=\lfloor 49/50\rfloor=0. Restante =49.
    9. d=25 ( R\$0{,}25): q=\lfloor 49/25\rfloor=1. Restante =49-1\cdot25=24.
    10. d=10 ( R\$0{,}10): q=\lfloor 24/10\rfloor=2. Restante =24-2\cdot10=4.
    11. d=5 ( R\$0{,}05): q=\lfloor 4/5\rfloor=0. Restante =4.
    12. d=1 ( R\$0{,}01): q=\lfloor 4/1\rfloor=4. Restante =0.
  • Resultado da decomposição (ordem das denominações mostradas acima):
    • R\$100{,}00: 0
    • R\$50{,}00: 1
    • R\$20{,}00: 2
    • R\$10{,}00: 0
    • R\$5{,}00: 1
    • R\$2{,}00: 2
    • R\$1{,}00: 0
    • R\$0{,}50: 0
    • R\$0{,}25: 1
    • R\$0{,}10: 2
    • R\$0{,}05: 0
    • R\$0{,}01: 4
Isto é exatamente o resultado explicado passo a passo no enunciado.

Passo 7

Tratamento de casos limites e observações práticas:
  • Se o valor pago for menor que o valor da compra ( \text{troco\_dec} < 0), o programa pode:
    • imprimir o valor negativo do troco na primeira linha (ou uma mensagem de “valor insuficiente”), e então imprimir zeros para todas as denominações, ou
    • sinalizar erro. Escolher uma política e documentá‑la. No exemplo de código a seguir eu mostro tratamento que aceita troco negativo imprimindo o valor (com sinal) e imprimindo zeros nas denominações (pode ajustar conforme necessidade da prova/julgar).
  • Sempre trabalhar com centavos inteiros evita problemas com somas sucessivas e arredondamentos.
  • Complexidade: algoritmo linear no número de denominações (constante: 12), portanto muito eficiente.

Passo 8

Código implementando tudo explicado (exemplo em Python, com comentários mínimos para leitura):
  • O código lê dois valores, converte para Decimal e centavos, aplica o algoritmo guloso e imprime o troco e a decomposição.

Resposta

from decimal import Decimal, ROUND_HALF_UP

# Leitura (substitui ',' por '.' para aceitar vírgula como separador decimal)
compra_str = input().strip().replace(',', '.')
pago_str = input().strip().replace(',', '.')

compra_dec = Decimal(compra_str)
pago_dec = Decimal(pago_str)

troco_dec = pago_dec - compra_dec

# Converter para centavos (inteiro) com arredondamento half up
troco_centavos = int((troco_dec * 100).quantize(Decimal('1'), rounding=ROUND_HALF_UP))

# Se troco_centavos negativo, manter o sinal e trabalhar com valor absoluto para a decomposição
sinal_negativo = troco_centavos < 0
if sinal_negativo:
    troco_centavos = -troco_centavos

# Denominações em centavos (descrescente)
denoms = [10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1]
labels = [
    "R\(100,00", "R\) 50,00", "R\(20,00", "R\) 10,00", "R\(5,00", "R\) 2,00",
    "R\(1,00", "R\) 0,50", "R\(0,25", "R\) 0,10", "R\(0,05", "R\) 0,01"
]

# Decomposição
counts = []
rest = troco_centavos
for d in denoms:
    q = rest // d
    counts.append(q)
    rest -= q * d

# Imprimir o troco na primeira linha (com sinal, duas casas decimais)
troco_print = Decimal(troco_centavos) / Decimal(100)
if sinal_negativo:
    troco_print = -troco_print
print(f"{troco_print:.2f}")

# Imprimir a sequência de linhas, uma por denominação
for label, cnt in zip(labels, counts):
    print(f"{cnt} unidade(s) de {label}")

Exercícios relacionados