O troco em moedas é uma combinação de moedas com os seguintes valores :
R$ 1,00; 0,50; 0,25; 0,10; 0,05; 0,01
Escreva um programa em C que leia qualquer valor em centavos ( \mathrm{R} \$0,01 até \mathrm{R} \$ 1,00 ). Calcule e imprima seu equivalente em moedas. Encontre a solução que utilize o menor número possível de moedas.

Passo 1

O que o enunciado pede:
  • Ler um valor em centavos, ou seja um inteiro entre 1 e 100 (correspondente a \mathrm{R}\$0,01 até \mathrm{R}\$1,00).
  • Calcular e imprimir a decomposição desse valor em moedas com os menores número de moedas possível, usando as moedas disponíveis: \mathrm{R}\$1,00; \mathrm{R}\$0,50; \mathrm{R}\$0,25; \mathrm{R}\$0,10; \mathrm{R}\$0,05; \mathrm{R}\$0,01.
Informações relevantes dadas:
  • O valor de entrada está em centavos e é inteiro.
  • As denominações de moedas são, em centavos, respectivamente: 100, 50, 25, 10, 5, 1.
  • Queremos a solução com o menor número possível de moedas (óptimo em número total de moedas).
Não foi pedido um formato específico de saída, apenas que calcule e imprima o equivalente em moedas; portanto vou apresentar um formato claro com a quantidade de cada moeda.

Passo 2

Escolha do método de resolução (explicação simples e direta):
  • Como temos um conjunto fixo de denominações de moeda e queremos minimizar o número de moedas, a abordagem natural é o algoritmo ganancioso (greedy): sempre usar o máximo possível da maior moeda disponível, depois seguir para a próxima maior, e assim por diante.
  • Para essas denominações (moedas reais do Brasil), o algoritmo ganancioso produz sempre uma solução ótima (ou seja, minimiza o número de moedas). Isso é verdade para sistemas de moedas “canônicos” como esse — vou justificar resumidamente o porquê no próximo passo.
  • Implementação prática: trabalhar somente com inteiros (centavos) evita problemas de ponto flutuante. Então o valor lido será um inteiro v com 1 \le v \le 100. Aplicamos a sequência de moedas 100,50,25,10,5,1.

Passo 3

Por que o algoritmo ganancioso funciona aqui (intuição e pequena prova por troca):
  • Ideia: suponha que existe uma solução ótima (mínimo de moedas) diferente da que o ganancioso obtém. Mostra-se que podemos trocar e transformar essa solução em uma que usa a maior moeda possível sem aumentar o número total de moedas — e repetindo o argumento chegamos ao resultado do ganancioso, logo o ganancioso é ótimo.
  • Mais concreto: se tivermos pelo menos duas moedas de 50 centavos, podemos trocá-las por uma moeda de 100 centavos (reduz número de moedas). Se tivermos várias moedas inferiores que somam para formar uma moeda maior, trocar reduz ou mantém o número de moedas. Com as denominações dadas, nenhuma combinação de moedas menores permite substituir uma moeda maior com menos moedas no processo inverso sem aumentar o total. Esse argumento de troca é o que garante a optimalidade no sistema canônico real.
  • Conclusão prática: usar sempre a maior moeda possível é seguro e produz mínimo número de moedas.

Passo 4

Descrição passo a passo do algoritmo (pseudocódigo simples):
  • Dados:
    • Vetor de moedas em centavos: C = [100,50,25,10,5,1].
    • Valor restante v (inteiro).
  • Para cada moeda c em C (do maior para o menor):
    • Calcular quantas moedas dessa denominação cabem: q = \left\lfloor \dfrac{v}{c} \right\rfloor.
    • Subtrair: v = v - q \cdot c.
    • Guardar q como quantidade usada da moeda c.
  • Quando terminar, v será 0 e teremos as quantidades de cada moeda.
  • Observação: a divisão inteira \left\lfloor v/c \right\rfloor é simplesmente a operação inteira v / c na linguagem C quando v e c são inteiros.

Passo 5

Como representar isso em C (escolhas de implementação e explicações de variáveis):
  • Variáveis principais:
    • int\;v; // valor em centavos lido do usuário
    • int\;coins[] = \{100,50,25,10,5,1\}; // denominações em centavos
    • int\;count[6]; // armazenará a quantidade usada de cada moeda
  • Leitura e validação:
    • Usar scanf("%d", &v); para ler um inteiro.
    • Verificar se v está no intervalo 1 até 100. Se não, podemos imprimir mensagem de erro ou ajustar conforme desejado.
  • Laços:
    • Um laço for que percorre o vetor de moedas; em cada iteração calcular q = v / coins[i]; e atualizar v -= q * coins[i];

Passo 6

Detalhamento linha a linha do que o programa deve fazer (como se fosse uma “aula prática”):
  1. Incluir cabeçalhos necessários: #include <stdio.h> — fornece scanf e printf.
  2. Na função main:
    • Declarar variáveis v, coins[], count[], i.
    • Ler o valor em centavos com scanf.
    • Fazer validação simples:
      • Se v < 1 ou v > 100, imprimir uma mensagem explicando o intervalo e retornar com código de erro (por exemplo, return 1;).
    • Inicializar count com zeros (pode-se atribuir zero explicitamente ou usar laço).
    • Percorrer o vetor coins e aplicar a divisão inteira para obter quantidades.
    • Após o laço, imprimir cada quantidade de moeda de forma legível (por exemplo: “Moedas de R$ 0,50: 1”).
  3. Finalizar retornando 0.
Explicação dos operadores usados:
  • Operador de divisão inteira a / b com inteiros descarta a parte fracionária, equivalente a \left\lfloor a/b \right\rfloor.
  • Operador de módulo a \% b dá o resto da divisão; podemos usar v = v \% c como alternativa a v -= q * c.

Passo 7

Exemplo prático (walkthrough) com um valor para fixar:
  • Suponha que a entrada seja v = 87 centavos.
  • Moedas C = [100,50,25,10,5,1].
    • Para c=100: q = 87 / 100 = 0. Resto v = 87.
    • Para c=50: q = 87 / 50 = 1. Resto v = 87 - 1\cdot50 = 37.
    • Para c=25: q = 37 / 25 = 1. Resto v = 37 - 1\cdot25 = 12.
    • Para c=10: q = 12 / 10 = 1. Resto v = 12 - 1\cdot10 = 2.
    • Para c=5: q = 2 / 5 = 0. Resto v = 2.
    • Para c=1: q = 2 / 1 = 2. Resto v = 0.
  • Quantidades obtidas: para \mathrm{R}\$1,00 = 0, \mathrm{R}\$0,50 = 1, \mathrm{R}\$0,25 = 1, \mathrm{R}\$0,10 = 1, \mathrm{R}\$0,05 = 0, \mathrm{R}\$0,01 = 2.
  • Isso usa no total 0+1+1+1+0+2 = 5 moedas, que é mínimo.

Passo 8

Complexidade e observações finais:
  • Complexidade: o algoritmo percorre um vetor fixo de 6 denominações, então é tempo constante O(1) na prática. Em termos algorítmicos, O(k) com k=6.
  • Trabalhar com inteiros evita erros de precisão. Não usei números em ponto flutuante.
  • Trate entradas inválidas de forma clara (p.ex. imprimir mensagem e encerrar).
  • Saída: eu vou apresentar o programa que imprime a quantidade de cada moeda, uma linha por denominação, em ordem decrescente.

Resposta

#include <stdio.h>

int main(void) {
    int v; /* valor em centavos, 1..100 */
    int coins[] = {100, 50, 25, 10, 5, 1};
    int count[6] = {0, 0, 0, 0, 0, 0};
    int i;

    /* Ler valor em centavos */
    if (scanf("%d", &v) != 1) {
        /* leitura falhou */
        fprintf(stderr, "Erro na leitura do valor.\n");
        return 1;
    }

    /* Validação simples: deve ser entre 1 e 100 centavos */
    if (v < 1 || v > 100) {
        fprintf(stderr, "Valor fora do intervalo. Informe um inteiro entre 1 e 100 (centavos).\n");
        return 1;
    }

    /* Aplicar algoritmo ganancioso */
    for (i = 0; i < 6; ++i) {
        count[i] = v / coins[i]; /* número de moedas da denominação coins[i] */
        v = v - count[i] * coins[i]; /* atualizar resto */
    }

    /* Imprimir resultado: uma linha por denominação */
    printf("Moedas de R$ 1,00: %d\n", count[0]);
    printf("Moedas de R$ 0,50: %d\n", count[1]);
    printf("Moedas de R$ 0,25: %d\n", count[2]);
    printf("Moedas de R$ 0,10: %d\n", count[3]);
    printf("Moedas de R$ 0,05: %d\n", count[4]);
    printf("Moedas de R$ 0,01: %d\n", count[5]);

    return 0;
}

Exercícios relacionados