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 (
até
). Calcule e imprima seu equivalente em moedas. Encontre a solução que utilize o menor número possível de moedas.
Escreva um programa em C que leia qualquer valor em centavos (
Passo 1
O que o enunciado pede:
- Ler um valor em centavos, ou seja um inteiro entre
e (correspondente a até ). - Calcular e imprimir a decomposição desse valor em moedas com os menores número de moedas possível, usando as moedas disponíveis:
; ; ; ; ; .
Informações relevantes dadas:
- O valor de entrada está em centavos e é inteiro.
- As denominações de moedas são, em centavos, respectivamente:
, , , , , . - 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
com . Aplicamos a sequência de moedas .
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
centavos, podemos trocá-las por uma moeda de 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:
. - Valor restante
(inteiro).
- Vetor de moedas em centavos:
- Para cada moeda
em (do maior para o menor): - Calcular quantas moedas dessa denominação cabem:
. - Subtrair:
. - Guardar
como quantidade usada da moeda .
- Calcular quantas moedas dessa denominação cabem:
- Quando terminar,
será e teremos as quantidades de cada moeda. - Observação: a divisão inteira
é simplesmente a operação inteira na linguagem C quando e são inteiros.
Passo 5
Como representar isso em C (escolhas de implementação e explicações de variáveis):
- Variáveis principais:
-
// valor em centavos lido do usuário -
// denominações em centavos -
// armazenará a quantidade usada de cada moeda
-
- Leitura e validação:
- Usar scanf("%d", &v); para ler um inteiro.
- Verificar se
está no intervalo até . 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
e atualizar
- Um laço for que percorre o vetor de moedas; em cada iteração calcular
Passo 6
Detalhamento linha a linha do que o programa deve fazer (como se fosse uma “aula prática”):
- Incluir cabeçalhos necessários: — fornece scanf e printf.
- Na função main:
- Declarar variáveis
, , , . - Ler o valor em centavos com scanf.
- Fazer validação simples:
- Se
ou , imprimir uma mensagem explicando o intervalo e retornar com código de erro (por exemplo, return 1;).
- Se
- Inicializar
com zeros (pode-se atribuir zero explicitamente ou usar laço). - Percorrer o vetor
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”).
- Declarar variáveis
- Finalizar retornando
.
Explicação dos operadores usados:
- Operador de divisão inteira
com inteiros descarta a parte fracionária, equivalente a . - Operador de módulo
dá o resto da divisão; podemos usar como alternativa a .
Passo 7
Exemplo prático (walkthrough) com um valor para fixar:
- Suponha que a entrada seja
centavos. - Moedas
. - Para
: . Resto . - Para
: . Resto . - Para
: . Resto . - Para
: . Resto . - Para
: . Resto . - Para
: . Resto .
- Para
- Quantidades obtidas: para
= , = , = , = , = , = . - Isso usa no total
moedas, que é mínimo.
Passo 8
Complexidade e observações finais:
- Complexidade: o algoritmo percorre um vetor fixo de
denominações, então é tempo constante na prática. Em termos algorítmicos, com . - 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;
}