Desafio (não-obrigatório): Considere agora que o caixa eletrônico dispõe apenas de cédulas de \mathrm{R} \ 50 e de\mathrm{R} $20 . Se você aplicar o algoritmo visto em sala de aula, verá que ele não funciona, por exemplo, para saques deêáã\mathrm{R} $ 110 , apesar de serem possíveis (uma cédula deíé\mathrm{R} $50 e três deê\mathrm{R} $ 20$ ). Modifique tal algoritmo.

Passo 1

O enunciado pede que eu modifique o algoritmo guloso (que sempre tenta usar o maior número possível de cédulas de \mathrm{R}\$\;50) para o caixa que só tem cédulas de \mathrm{R}\$\;50 e \mathrm{R}\$\;20, porque esse guloso falha para saques como \mathrm{R}\$\;110. Informações relevantes que o enunciado dá:
  • Denominações disponíveis: \mathrm{R}\$\;50 e \mathrm{R}\$\;20.
  • Exemplo que mostra a falha do guloso: saque de \mathrm{R}\$\;110 (uma solução válida é 1 cédula de 50 e 3 cédulas de 20).
  • A tarefa é modificar o algoritmo de forma que ele sempre encontre uma solução (quando existir) ou reporte que não é possível.

Passo 2

Primeira ideia matemática (condição de existência). Para um valor A (o montante do saque) devemos encontrar inteiros não-negativos x e y tais que
50x + 20y = A.
Uma regra geral: uma solução inteira existe somente se o máximo divisor comum das notas divide A. Calculemos o \gcd:
\gcd(50,20) = 10.
Logo, uma condição necessária é que 10 divida A, ou seja, A deve ser múltiplo de 10. Se A não for múltiplo de 10, já sabemos que é impossível montar o saque com essas notas.

Passo 3

Redução do problema (dividir por 10) e análise das soluções inteiras. Se 10 divide A, escreva A = 10k. Dividindo a equação por 10 obtemos
5x + 2y = k.
Isolando y:
y = \frac{k - 5x}{2}.
Para y ser inteiro precisamos que k - 5x seja par. Observação sobre paridade: 5x \equiv x \pmod{2}, então a condição é
x \equiv k \pmod{2},
ou seja, x tem que ter a mesma paridade que k. Além disso x deve satisfazer 0 \le x \le \left\lfloor \dfrac{k}{5} \right\rfloor para que y\ge 0. Isso nos dá uma descrição completa de quando soluções existem: existe solução não-negativa se e somente se existir um x inteiro dentro desse intervalo com a paridade correta.

Passo 4

Construindo o algoritmo modificado (intuição e forma simples). Uma forma prática, simples e rápida de implementar é:
  • Começar usando o maior número possível de cédulas de \mathrm{R}\$\;50, ou seja x \leftarrow \left\lfloor \dfrac{A}{50} \right\rfloor.
  • Calcular o resto r \leftarrow A - 50x.
  • Se r for divisível por 20, então y \leftarrow \dfrac{r}{20} é solução e terminamos.
  • Se não, diminuir x em 1 e repetir (recalcular r e testar divisibilidade por 20) até x<0.
  • Se chegarmos a x<0 sem encontrar solução, concluímos que não é possível com essas notas.
Esse algoritmo é só uma variação do guloso que, ao falhar, tenta reduzir uma cédula de 50 e testar novamente, e assim por diante. É fácil de implementar e, para nosso caso com duas denominações, rápido o bastante.

Passo 5

Por que esse ajuste resolve o problema do exemplo e por que é eficiente. Observe que os restos possíveis ao dividir por 50 são múltiplos de 10: 0,10,20,30,40. Se o resto for 0,20,40 então é imediatamente múltiplo de 20 e o guloso já acerta. Se o resto for 10 ou 30, então subtrair uma cédula de 50 (ou seja, diminuir x em 1) acrescenta 50 ao resto e transforma 10 em 60 ou 30 em 80, ambos divisíveis por 20. Assim, sempre que x\ge 1 basta testar no máximo mais uma redução para obter resto divisível por 20. Se x=0 (ou seja A<50), o algoritmo faz apenas a verificação se A é múltiplo de 20. Portanto, na prática o número de iterações é muito pequeno (0 ou 1 tentativa extra quando A\ge 50), e o algoritmo é eficiente.

Passo 6

Pseudocódigo claro do algoritmo (passo a passo implementável):
  1. Se A \bmod 10 \neq 0 então reportar “impossível” (não dá para formar A com notas de 50 e 20).
  2. x \leftarrow \left\lfloor \dfrac{A}{50} \right\rfloor.
  3. Enquanto x \ge 0 faça:
    • r \leftarrow A - 50x.
    • Se r \bmod 20 = 0 então y \leftarrow \dfrac{r}{20} e retornar "usar x notas de 50 e y notas de 20".
    • Senão x \leftarrow x - 1.
  4. Se sair do laço sem retornar, então retornar “impossível”.
Esse pseudocódigo é direto, fácil de provar correto pela análise das equações e termina em tempo muito pequeno.

Passo 7

Aplicação no exemplo A=\mathrm{R}\$\;110 (passo a passo para ganhar confiança):
  • Teste inicial: 110 \bmod 10 = 0, ok.
  • x \leftarrow \left\lfloor \dfrac{110}{50} \right\rfloor = 2.
  • Primeiro teste: r = 110 - 50\cdot 2 = 10. 10 \bmod 20 \neq 0 → não serve.
  • Reduzir x para 1. Novo r = 110 - 50\cdot 1 = 60. 60 \bmod 20 = 0 y = 60/20 = 3.
  • Solução encontrada: x=1 cédula de 50 e y=3 cédulas de 20. Isso resolve o caso problema que o algoritmo guloso puro não resolvia.

Resposta

1 cédula de 50 e 3 cédulas de 20.

Exercícios relacionados