Desafio (não-obrigatório): Considere agora que o caixa eletrônico dispõe apenas de cédulas de
50
\mathrm{R} $20
\mathrm{R} $ 110
\mathrm{R} $50
\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
) para o caixa que só tem cédulas de
e
, porque esse guloso falha para saques como
. Informações relevantes que o enunciado dá:
- Denominações disponíveis:
e . - Exemplo que mostra a falha do guloso: saque de
(uma solução válida é cédula de e cédulas de ). - 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
(o montante do saque) devemos encontrar inteiros não-negativos
e
tais que
Uma regra geral: uma solução inteira existe somente se o máximo divisor comum das notas divide
. Calculemos o
:
Logo, uma condição necessária é que
divida
, ou seja,
deve ser múltiplo de
. Se
não for múltiplo de
, 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
divide
, escreva
. Dividindo a equação por
obtemos
Isolando
:
Para
ser inteiro precisamos que
seja par. Observação sobre paridade:
, então a condição é
ou seja,
tem que ter a mesma paridade que
. Além disso
deve satisfazer
para que
. Isso nos dá uma descrição completa de quando soluções existem: existe solução não-negativa se e somente se existir um
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
, ou seja . - Calcular o resto
. - Se
for divisível por , então é solução e terminamos. - Se não, diminuir
em e repetir (recalcular e testar divisibilidade por ) até . - Se chegarmos a
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
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
são múltiplos de
:
. Se o resto for
então é imediatamente múltiplo de
e o guloso já acerta. Se o resto for
ou
, então subtrair uma cédula de
(ou seja, diminuir
em
) acrescenta
ao resto e transforma
em
ou
em
, ambos divisíveis por
. Assim, sempre que
basta testar no máximo mais uma redução para obter resto divisível por
. Se
(ou seja
), o algoritmo faz apenas a verificação se
é múltiplo de
. Portanto, na prática o número de iterações é muito pequeno (0 ou 1 tentativa extra quando
), e o algoritmo é eficiente.
Passo 6
Pseudocódigo claro do algoritmo (passo a passo implementável):
- Se
então reportar “impossível” (não dá para formar com notas de e ). -
. - Enquanto
faça: -
. - Se
então e retornar "usar notas de e notas de ". - Senão
.
-
- 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
(passo a passo para ganhar confiança):
- Teste inicial:
, ok. -
. - Primeiro teste:
. → não serve. - Reduzir
para . Novo . → . - Solução encontrada:
cédula de e cédulas de . Isso resolve o caso problema que o algoritmo guloso puro não resolvia.
Resposta
1 cédula de
e 3 cédulas de
.