6)Faça um programa que,dado um valor em reais(sem centavos),mostre a menor combinação existente de notas( R \ 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 \{200,100,50,20,10,5,2\}.
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:
  1. Defina a lista de notas em ordem decrescente:
    \{200,\,100,\,50,\,20,\,10,\,5,\,2\}.
  2. Leia o valor inteiro V.
  3. Para cada nota n na lista:
    3.1. Calcule a quantidade de notas de valor n como
q_n \;=\;\left\lfloor\frac{V}{n}\right\rfloor.
3.2. Subtraia do valor restante:
V \;\leftarrow\; V - q_n \times n.
  1. No fim, se o valor restante V\neq 0, significa que V é igual a 1 ou 3, e não pode ser pago usando apenas \{5,2\}. Nesse caso, informe que não há combinação possível.

Passo 4

Justificativa de completude:
  • Se V for par, sobra sempre 0 depois de distribuir as notas até a de 2, pois 2 divide qualquer par.
  • Se V for ímpar e \ge5, a nota de 5 resolve o “resto 1” ou “resto 3” antes de usar os pares.
  • Se V for 1 ou 3, 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.

Exercícios relacionados