(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:
-
99,49 \rightarrow
\mathrm{R} $50,00
\mathrm{R} $ 50,00
\mathrm{R} $49,49$
- R
49,49 \rightarrow
\mathrm{R} $20,00
\mathrm{R} $ 50,00
\mathrm{R} $20,00
\mathrm{R} $ 29,49$
-
29,49 \rightarrow
\mathrm{R} $20,00
\mathrm{R} $ 50,00
\mathrm{R} $20,00
\mathrm{R} $ 9,49$
- R
9,49 \rightarrow
\mathrm{R} $5,00
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00
\mathrm{R} $ 5,00
\mathrm{R} $4,49$
-
4,49 \rightarrow
\mathrm{R} $2,00
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00,1
\mathrm{R} $ 5,00
\mathrm{R} $2,00
\mathrm{R} $ 2,49$
-
2,49 \rightarrow
\mathrm{R} $2,00
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00,1
\mathrm{R} $ 5,00
\mathrm{R} $2,00
\mathrm{R} $ 0,49$
-
0,49 \rightarrow
\mathrm{R} $0,25
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00,1
\mathrm{R} $ 5,00,2
\mathrm{R} $2,00
\mathrm{R} $ 0,25
\mathrm{R} $0,24$
-
0,24 \rightarrow
\mathrm{R} $0,10
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00,1
\mathrm{R} $ 5,00,2
\mathrm{R} $2,00,1
\mathrm{R} $ 0,25
\mathrm{R} $0,10
\mathrm{R} $ 0,14$
-
0,14 \rightarrow
\mathrm{R} $0,10
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00,1
\mathrm{R} $ 5,00,2
\mathrm{R} $2,00,1
\mathrm{R} $ 0,25
\mathrm{R} $0,10
\mathrm{R} $ 0,04$
-
0,04 \rightarrow
\mathrm{R} $0,01
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00,1
\mathrm{R} $ 5,00,2
\mathrm{R} $2,00,1
\mathrm{R} $ 0,25,2
\mathrm{R} $0,10
\mathrm{R} $ 0,01
\mathrm{R} $0,03$
-
0,03 \rightarrow
\mathrm{R} $0,01
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00,1
\mathrm{R} $ 5,00,2
\mathrm{R} $2,00,1
\mathrm{R} $ 0,25,2
\mathrm{R} $0,10
\mathrm{R} $ 0,01
\mathrm{R} $0,02$
-
0,02 \rightarrow
\mathrm{R} $0,01
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00,1
\mathrm{R} $ 5,00,2
\mathrm{R} $2,00,1
\mathrm{R} $ 0,25,2
\mathrm{R} $0,10
\mathrm{R} $ 0,01
\mathrm{R} $0,01$
-
0,01 \rightarrow
\mathrm{R} $0,01
\mathrm{R} $ 50,00,2
\mathrm{R} $20,00,1
\mathrm{R} $ 5,00,2
\mathrm{R} $2,00,1
\mathrm{R} $ 0,25,2
\mathrm{R} $0,10
\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.
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:
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
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,
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
(p.ex. ), representa-se como centavos . 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 é
, em centavos isso é centavos.
Passo 3
Quais denominações usar (ordem decrescente) e como representá‑las em centavos:
- Notas (em centavos):
, , , , , . - Moedas (em centavos):
, , , , , .
Como vetor em centavos (descendente):
Cada posição corresponde, respectivamente, a
.
Passo 4
Descrição do algoritmo guloso (passo a passo matemático):
- Seja
o troco em centavos (inteiro). - Para cada denominação
em (da maior para a menor): - calcular o número de unidades dessa denominação por divisão inteira:
(em programação: q = C // d). - reduzir o restante:
- calcular o número de unidades dessa denominação por divisão inteira:
- Repetir até terminar todas as denominações. Ao final
deve ser 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
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
e atualizando o restante . - 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):
-
: valor da compra como Decimal. -
: valor pago como Decimal. -
: troco em Decimal (pode ser zero ou negativo). -
: inteiro representando o troco em centavos (positivo ou zero). -
: lista de denominações em centavos (inteiros). - Para cada denominação
: , depois atualizar .
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
. Em centavos: -
Aplicando as denominações uma a uma:
-
( ): . Restante . -
( ): . Restante . -
( ): . Restante . -
( ): . Restante . -
( ): . Restante . -
( ): . Restante . -
( ): . Restante . -
( ): . Restante . -
( ): . Restante . -
( ): . Restante . -
( ): . Restante . -
( ): . Restante .
-
-
Resultado da decomposição (ordem das denominações mostradas acima):
-
: 0 -
: 1 -
: 2 -
: 0 -
: 1 -
: 2 -
: 0 -
: 0 -
: 1 -
: 2 -
: 0 -
: 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 (
), 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}")