CS50-MCZ

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


Cash

Começando

Abra o VS Code.

Comece clicando dentro da janela do seu terminal e execute o comando cd. Você deve ver que o "prompt" se assemelha ao abaixo.

$

Clique dentro da janela do terminal e execute

wget https://cdn.cs50.net/2022/fall/psets/1/cash.zip

seguido de Enter para baixar um arquivo ZIP chamado cash.zip em seu espaço de código. Certifique-se de não ignorar o espaço entre wget e a URL a seguir, ou qualquer outro caractere!

Agora execute

unzip cash.zip

para criar uma pasta chamada cash. Você não precisa mais do arquivo ZIP, então pode executar

rm cash.zip

e responda com "y" seguido de Enter no prompt para remover o arquivo ZIP que você baixou.

Agora digite

cd cash

seguido de Enter para mover-se para (ou seja, abrir) esse diretório. Sua linha de comando deve agora se parecer com a abaixo.

cash/ $

Se tudo foi bem sucedido, você deve executar

ls

e ver um arquivo chamado cash.c. Executar code cash.c deve abrir o arquivo onde você digitara seu código para esse problema. Caso contrário, refaça seus passos e veja se consegue determinar onde errou!

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:

Você também pode executar o código abaixo para avaliar a correção do seu programa usando check50. Mas certifique-se de compilar e testar por conta própria também!

check50 cs50/problems/2023/x/cash
O check50 está falhando ao compilar o seu código?

Certifique-se de ter modificado apenas as partes do programa marcadas como TODO. Se você modificar a função main ou adicionar quaisquer variáveis globais, por exemplo, seu código poderá falhar ao compilar. O check50 testará suas cinco funções independentemente, além de verificar apenas a resposta final.

E execute o código abaixo para avaliar o estilo do seu programa usando style50.

style50 cash.c

Como Enviar

No seu terminal, execute o código abaixo para enviar seu trabalho.

submit50 cs50/problems/2023/x/cash