(0.5) Você sabe que existem notas de R \ 2,00, R $5,00, R $ 10,00, R $20,00, R $ 50,00 e\mathrm{R} $100,00 , além da moeda deé\mathrm{R} $ 1,00 . Suponha, agora, que os preços da loja são valores inteiros entreçã\mathrm{R} $10,00 e\mathrm{R} $ 100,00 e que o pagamento feito pelo cliente também é um valor inteiro igual ou maior que ao valor gasto. O objetivo do programa (em Python), é calcular o troco e devolver o menor número de cédulas/moedas para o cliente. Por exemplo, se o valor da compra foiéééúé\mathrm{R} $35,00 e o cliente pagou com uma nota de\mathrm{R} $ 50,00 , então o programa poderia devolver 15 moedas deã\mathrm{R} $1,00 , ou 7 cédulas deé\mathrm{R} $ 2,00 e uma moeda de\mathrm{R} $1,00 ou ainda 3 cédulas deé\mathrm{R} $ 5,00 ou uma cédula deé\mathrm{R} $5,00 e uma cédula deé\mathrm{R} $ 10,00 , etc. A escolha do seu programa deveria ser a última combinação apresentada, pois devolve apenas 2 cédulas (úçãéR $10,00+R $ 5,00$ ).

Passo 1

O que o problema pede e os dados que temos:
  • Temos as cédulas/moeda disponíveis com valores: \mathrm{R}\$100,00, \mathrm{R}\$ 50,00, \mathrm{R}\$20,00, \mathrm{R}\$ 10,00, \mathrm{R}\$5,00, \mathrm{R}\$ 2,00 e a moeda de \mathrm{R}\$ 1,00.
  • O preço da compra é um inteiro entre \mathrm{R}\$10,00 e \mathrm{R}\$ 100,00 (mas vamos deixar o programa funcionando para qualquer inteiro não negativo).
  • O pagamento é um inteiro maior ou igual ao preço.
  • O objetivo: calcular o troco (pagamento menos preço) e devolver uma combinação de cédulas/moedas que use o menor número possível de peças (mínimo número de notas/ moedas).
O que o enunciado pergunta explicitamente:
  • Implementar um programa em Python que, dados preço e pagamento (inteiros), calcule o troco e retorne a decomposição nesse conjunto de cédulas/moeda usando o menor número de peças possível.

Passo 2

Que método escolher e por quê (explicação didática do método):
  • Aqui o objetivo é minimizar o número de peças para representar um inteiro não negativo (o troco) usando um conjunto fixo de valores. Uma estratégia natural é o algoritmo guloso: sempre pegar a maior cédula/ moeda possível enquanto ainda couber no troco restante, e repetir com o restante.
  • O algoritmo guloso funciona assim, em palavras simples:
    1. Ordene as cédulas da maior para a menor: por exemplo, \{100,50,20,10,5,2,1\}.
    2. Para cada cédula d nessa ordem, pegue o máximo número inteiro de cédulas de valor d que caibam no troco restante, subtraia esse total do troco e passe para a próxima cédula.
  • Por que usar essa abordagem? Porque para o sistema de cédulas dado (o conjunto clássico usado no enunciado) o algoritmo guloso produz sempre uma solução com o menor número de peças. Vou explicar porquê com um argumento por troca simples e intuitivo:
    • Pense na maior cédula, \,100. Se o troco tem pelo menos \,100, pegar o máximo possível de notas de \,100 não pode aumentar o número de peças em comparação a qualquer solução que não pegue essas notas: para substituir uma nota de \,100 seriam necessárias várias notas menores (pelo menos duas ou mais), logo trocar uma nota de \,100 por notas menores só aumentaria o número de peças. Assim, tomar o máximo de \,100 é seguro.
    • Mesmo raciocínio vale para \,50: para formar \,50 com valores menores precisa-se de pelo menos 2 ou 3 peças (por exemplo, duas \,20 e uma \,10 = 3 peças), então usar uma \,50 é sempre tão bom ou melhor do ponto de vista do número de peças.
    • Para \,20 e \,10: substituir uma \,20 por duas \,10 mantém o mesmo número de peças; substituições que usariam apenas moedas menores resultariam em mais peças. Para manter o número mínimo não há ganho em evitar usar uma \,20 quando ela cabe.
    • Para \,5 e \,2: substituir uma \,5 precisa de pelo menos 3 peças com \,2 e \,1 (por exemplo, 2+2+1), então usar uma \,5 é melhor. Substituir uma \,2 por duas \,1 mantém o número de peças.
    • Em resumo: cada cédula maior não pode ser substituída por uma combinação de menores que use menos peças; no pior caso a substituição usa o mesmo número, na maioria dos casos usa mais. Portanto o método guloso é seguro para esse conjunto de cédulas e garante o mínimo global de peças.
  • Observação prática: esse é o método usado por caixas em lojas e é rápido de aplicar à mão (útil na prova) e trivial de implementar em Python.

Passo 3

Desenvolvendo o algoritmo passo a passo (aula prática de como fazer na prova):
  • Passo 3.1: Calcule o troco:
    • Seja o preço \,p e o pagamento \,q. O troco é \,t = q - p.
    • Se \,t=0, não há troco; fim.
    • Se \,t<0, erro: pagamento insuficiente.
  • Passo 3.2: Organize as cédulas em ordem decrescente:
    • Vetor \,D = [100,50,20,10,5,2,1].
  • Passo 3.3: Para cada denominação d em D:
    • Calcule quantas cédulas de d cabem no troco atual: c = \lfloor t/d \rfloor (divisão inteira).
    • Registre c como número de peças de valor d.
    • Atualize o troco: t \leftarrow t - c\cdot d.
    • Passe para a próxima denominação.
  • Depois de passar por todas as denominações, o troco restante será zero e a lista de contagens dará a solução com o menor número de peças.
  • Dica para a prova: faça a divisão inteira e o resto à mão — por exemplo, para troco \,t=87: \,87//100=0, \,87//50=1 (resto \,37), \,37//20=1 (resto \,17), \,17//10=1 (resto \,7), \,7//5=1 (resto \,2), \,2//2=1 (resto \,0). Resultado: \,50+20+10+5+2 = 5 peças.

Passo 4

Exemplo concreto (o exemplo do enunciado) e execução manual passo a passo:
  • Exemplo: preço \,p=\mathrm{R}\$35,00 e pagamento \,q=\mathrm{R}\$ 50,00.
  • Troco: \,t = 50 - 35 = 15.
  • Aplico o algoritmo guloso com D=[100,50,20,10,5,2,1]:
    • \,15//100=0 → resto \,15.
    • \,15//50=0 → resto \,15.
    • \,15//20=0 → resto \,15.
    • \,15//10=1 → uso uma nota de \,10, resto \,15-10=5.
    • \,5//5=1 → uso uma nota de \,5, resto \,0.
  • Resultado: uma nota de \,10 e uma nota de \,5 → total de 2 peças. Isso é melhor que usar quinze moedas de \,1 ou sete de \,2 + uma de \,1, etc.

Passo 5

Complexidade e casos especiais:
  • Complexidade: o algoritmo percorre um vetor fixo de 7 denominações, logo tempo O(1) (na prática linear no número de denominações). Memória O(1).
  • Casos especiais:
    • Se pagamento < preço: informe erro.
    • Se preço ou pagamento não forem inteiros: o enunciado diz inteiros; o programa aqui assume inteiros. Em situações reais com centavos, transformar tudo para centavos (inteiro) antes de aplicar o mesmo algoritmo funciona.
  • Boa prática: no código, trate entradas inválidas e imprima a decomposição apenas das denominações com contagem positiva para ficar legível.

Passo 6

Programa em Python (implementação fiel ao algoritmo explicado). O código abaixo lê preço e pagamento (inteiros), calcula o troco e imprime a decomposição com o menor número de peças:
def make_change(preco, pagamento):
    """
    Retorna um dicionário {denominacao: qtd} representando a decomposição
    do troco (pagamento - preco) usando o menor número de cédulas/moedas.
    Supõe que preco e pagamento são inteiros (valores em reais, sem centavos).
    """
    if pagamento < preco:
        raise ValueError("Pagamento insuficiente: pagamento < preço.")
    troco = pagamento - preco
    denominacoes = [100, 50, 20, 10, 5, 2, 1]
    contagens = {}
    restante = troco
    for d in denominacoes:
        qtd = restante // d
        contagens[d] = qtd
        restante = restante - qtd * d
    return troco, contagens

def imprime_troco(preco, pagamento):
    try:
        troco, contagens = make_change(preco, pagamento)
    except ValueError as e:
        print("Erro:", e)
        return
    print(f"Preço: R\({preco}, Pagamento: R\) {pagamento}, Troco: R$ {troco}")
    total_pecas = 0
    for d in [100, 50, 20, 10, 5, 2, 1]:
        qtd = contagens[d]
        if qtd:
            print(f"{qtd} x R$ {d}")
            total_pecas += qtd
    print(f"Total de peças (cédulas/moedas): {total_pecas}")

# Exemplo de uso:
if __name__ == "__main__":
    # Exemplo do enunciado:
    preco = 35
    pagamento = 50
    imprime_troco(preco, pagamento)

    # Para usar interativamente, descomente as linhas abaixo:
    # preco = int(input("Preço (inteiro, R$): "))
    # pagamento = int(input("Pagamento (inteiro, R$): "))
    # imprime_troco(preco, pagamento)

Passo 7

Teste rápido e interpretação do resultado:
  • Com o exemplo do enunciado ( \,p=35, \,q=50), o programa imprime:
    • Troco: \,15
    • \,1 x \mathrm{R}\$ 10,00
    • \,1 x \mathrm{R}\$ 5,00
    • Total de peças: \,2
  • Outros testes:
    • \,p=13, \,q=100 → troco \,87 → decomposição \,1\times50, 1\times20, 1\times10, 1\times5, 1\times2 (total 5 peças), conforme o cálculo manual do Passo 3.

Resposta

def make_change(preco, pagamento):
    """
    Retorna um dicionário {denominacao: qtd} representando a decomposição
    do troco (pagamento - preco) usando o menor número de cédulas/moedas.
    Supõe que preco e pagamento são inteiros (valores em reais, sem centavos).
    """
    if pagamento < preco:
        raise ValueError("Pagamento insuficiente: pagamento < preço.")
    troco = pagamento - preco
    denominacoes = [100, 50, 20, 10, 5, 2, 1]
    contagens = {}
    restante = troco
    for d in denominacoes:
        qtd = restante // d
        contagens[d] = qtd
        restante = restante - qtd * d
    return troco, contagens

def imprime_troco(preco, pagamento):
    try:
        troco, contagens = make_change(preco, pagamento)
    except ValueError as e:
        print("Erro:", e)
        return
    print(f"Preço: R\({preco}, Pagamento: R\) {pagamento}, Troco: R$ {troco}")
    total_pecas = 0
    for d in [100, 50, 20, 10, 5, 2, 1]:
        qtd = contagens[d]
        if qtd:
            print(f"{qtd} x R$ {d}")
            total_pecas += qtd
    print(f"Total de peças (cédulas/moedas): {total_pecas}")

# Exemplo de uso:
if __name__ == "__main__":
    preco = 35
    pagamento = 50
    imprime_troco(preco, pagamento)

Exercícios relacionados