CS50-MCZ

Uma introdução aos empreendimentos intelectuais da Ciência da Computação e da arte da programação.


Cash

Problema a Resolver

Suponha que você trabalhe em uma loja e um cliente lhe dê R$ 1,00 (100 centavos) por um doce que custa R$ 0,50 (50 centavos). Você precisará pagar a eles o “troco”, o valor que sobra depois de pagar o custo do doce. Ao fazer o troco, é provável que você queira minimizar o número de moedas que está distribuindo para cada cliente, para não acabar (ou irritar o cliente!). Em um arquivo chamado cash.c em uma pasta chamada cash, implemente um programa em C que imprima as moedas mínimas necessárias para fazer um determinado valor de troco, em centavos.

Começando

Algoritmos Gananciosos

Moedas dos Estados Unidos

Ao fazer troco, você provavelmente deseja minimizar o número de moedas que está dispensando para cada cliente, para não ficar sem moedas (ou incomodar o cliente!). Felizmente, a ciência da computação oferece aos caixas maneiras de minimizar o número de moedas devidas: algoritmos gananciosos.

De acordo com o Instituto Nacional de Padrões e Tecnologia (NIST), um algoritmo ganancioso é aquele "que sempre escolhe a melhor solução imediata ou local enquanto encontra uma resposta. Algoritmos gananciosos encontram a solução ótima global para alguns problemas de otimização, mas podem encontrar soluções menos do que ótimas para algumas instâncias de outros problemas."

O que tudo isso significa? Bem, suponha que um caixa deva troco para um cliente e na gaveta do caixa haja moedas de vinte e cinco centavos (25¢), dez centavos (10¢), cinco centavos (5¢) e um centavo (1¢). O problema a ser resolvido é decidir quais moedas e quantas de cada uma entregar ao cliente. Pense em um caixa "ganancioso" como aquele que quer tirar a maior porção possível deste problema com cada moeda que ele pega da gaveta. Por exemplo, se um cliente deve 41¢, a maior porção (ou melhor, a melhor porção imediata ou local) que pode ser retirada é de 25¢. (Essa porção é "melhor" porque nos leva mais rapidamente a 0¢ do que qualquer outra moeda.) Observe que uma porção desse tamanho reduziria o problema de 41¢ para 16¢, já que 41 - 25 = 16. Ou seja, o resto é um problema semelhante, mas menor. É desnecessário dizer que outra porção de 25¢ seria grande demais (supondo que o caixa prefira não perder dinheiro), então nosso caixa ganancioso passaria para uma porção de 10¢, deixando-o com um problema de 6¢. Nesse ponto, a ganância pede uma porção de 5¢ seguida de uma porção de 1¢, momento em que o problema é resolvido. O cliente recebe uma moeda de vinte e cinco centavos, uma de dez centavos, uma de cinco centavos e uma de um centavo: quatro moedas no total.

Acontece que essa abordagem gananciosa (ou seja, algoritmo) não é apenas localmente ótima, mas também globalmente para a moeda dos Estados Unidos (e também do Brasil). Ou seja, desde que um caixa tenha moedas suficientes de cada tipo, essa abordagem do maior para o menor resultará no menor número possível de moedas. Quantas? Bem, você nos diz!

Detalhes da Implementação

No arquivo cash.c, implementamos a maior parte (mas não tudo!) de um programa que solicita ao usuário o número de centavos que um cliente deve e, em seguida, imprime o menor número de moedas com o qual o troco pode ser feito. De fato, main já está implementado para você. Mas observe como main chama várias funções que ainda não estão implementadas! Uma dessas funções, get_cents, não recebe argumentos (conforme indicado por void) e retorna um int. O restante das funções todas recebe um argumento, um int, e também retorna um int. Todas elas atualmente retornam 0 para que o código compile. Mas você precisará substituir todos os TODO e return 0; com o seu próprio código. Especificamente, conclua a implementação dessas funções da seguinte forma:

Observe que, ao contrário das funções que possuem apenas efeitos colaterais, as funções que retornam um valor devem fazê-lo explicitamente com return! Tenha cuidado para não modificar o código de distribuição em si, apenas substitua os TODOs fornecidos e o valor de retorno subsequente! Lembre-se também da ideia de abstração: cada uma de suas funções de cálculo deve aceitar qualquer valor de cents, não apenas aqueles valores que o algoritmo guloso possa sugerir. Se cents for 85, por exemplo, calculate_dimes deve retornar 8.

Dica
  • Lembre-se de que há vários programas de exemplo no Código Fonte da Semana 1 que ilustram como as funções podem retornar um valor.

Seu programa deve se comportar conforme os exemplos abaixo.

$ ./cash
Quanto devido: 41
4

$ ./cash
Quanto devido: -41
Quanto devido: foo
Quanto devido: 41
4

Como testar seu código

Para este programa, tente testar seu código manualmente - é uma boa prática:

Execute o abaixo para avaliar a correção do seu código usando check50. Mas certifique-se de compilá-lo e testá-lo você mesmo também!

check50 cs50/problems/2024/x/cash

Execute abaixo para avaliar o estilo do seu código usando style50.

style50 cash.c

Como Enviar

No seu terminal, execute abaixo para enviar seu trabalho.

submit50 cs50/problems/2024/x/cash