6)Faça um programa que,dado um valor em reais(sem centavos),mostre a menor combinação existente de notas(
200,100,50,20,10,5$ e 2 )para esse valor.
Passo 1
O problema pede um programa que, dado um valor inteiro em reais (sem centavos), determine a forma de pagar esse valor usando o menor número possível de notas, dentre as denominações
.
Conteúdo: técnica de algoritmo gulosos (“greedy”) aplicada ao problema de troco com notas.
Conteúdo: técnica de algoritmo gulosos (“greedy”) aplicada ao problema de troco com notas.
Passo 2
A ideia central do algoritmo guloso é sempre usar o maior valor de nota possível antes de passar para as menores. Como o sistema de notas brasileiro é canônico (cada nota divide perfeitamente os valores maiores, exceto pelos casos de resto 1 ou 3, que vamos tratar), essa estratégia produz sempre a combinação mínima de notas.
Passo 3
Descrição do algoritmo:
- Defina a lista de notas em ordem decrescente:
. - Leia o valor inteiro
. - Para cada nota
na lista:
3.1. Calcule a quantidade de notas de valorcomo
3.2. Subtraia do valor restante:
- No fim, se o valor restante
, significa que é igual a ou , e não pode ser pago usando apenas . Nesse caso, informe que não há combinação possível.
Passo 4
Justificativa de completude:
- Se
for par, sobra sempre 0 depois de distribuir as notas até a de , pois divide qualquer par. - Se
for ímpar e , a nota de resolve o “resto 1” ou “resto 3” antes de usar os pares. - Se
for ou , não há solução.
Passo 5
Pseudocódigo em Python para ilustrar:
notas = [200, 100, 50, 20, 10, 5, 2]
V = int(input()) # lê o valor em reais (sem centavos)
troco = {}
for n in notas:
q = V // n # número de notas de valor n
troco[n] = q
V -= q * n
if V !\(=0\):
print("Não existe combinação possível.")
else:
for n in notas:
print(f"{troco[n]} nota(s) de R$ {n}")
Resposta
Acima está um exemplo de programa (em Python) que, dado um inteiro, imprime a menor combinação de notas de
R$ 200, 100, 50, 20, 10, 5 e 2.
R$ 200, 100, 50, 20, 10, 5 e 2.