quinta-feira, 16 de setembro de 2010

Otimizando a niqueleira

Sinto falta de uma nota de R$3 e de uma moeda de 15 centavos. Uma tarifa de lotação custa R$3,65 e a melhor combinação de valores é R$2+R$1+R$0,50+R$0,10+R$0,05.

Reparei que a seqüência de valores das moedas é diferente da de notas. Vou fazer de conta que a moeda de R$1 é uma nota.

Então, temos as seguintes moedas: 1, 5, 10, 25, 50. Mas as notas são 1, 2, 5, 10, 20, 50 e 100. Se existe uma combinação ótima, ela deveria ser usada nas duas seqüências, não?

Resolvi descobrir qual seqüência produz a menor contagem agregada para todos os valores entre 1 e 99. Para as moedas, seriam os valores entre 1 centavo e 99 centavos. Para as cédulas, seriam os valores entre R$1 e R$99.


my @moedas=(50,25,10,5,1);

my $total=0;
for my $valor (1..99) {
print "\n";
my $soma=$valor;
print "$valor =>";
for my $moeda (@moedas) {
if($soma>=$moeda) {
$n=int($soma/$moeda);
$total+=$n;
$soma-=$n*$moeda;
print "$n*$moeda; ";
}
}
}

print "\n$total\n";

O programa imprime na tela as melhores combinações para cada valor. O algoritmo é simples: ele vai da maior moeda para a menor, tentado maximimar o uso de cada uma.

Encontrei que a seqüência das notas tem uma contagem agregada de 340 (em média, são necessárias 3,43 notas) e a das moedas precisa de 420 (em média são necessárias 4,24 moedas). No entanto, a seqüência das notas tem a vantagem de ter um elemento a mais. A nota de R$2 faz toda a diferença e trocar 25 por 20 não altera em nada a contagem.

Então, sugiro que o Banco Central comece a emitir moedas de 2 centavos.

Brincando um pouco com os valores, descobri que uma nota de R$35 (ou R$30) e outra de R$15 baixariam a contagem agregada das notas para 300. Será que há uma combinação que tenha uma contagem menor que 300?

2 comentários:

Marcus Aurelius disse...

Eu sempre achei que devia ser feita a moeda de 2 centavos. É quase impossível juntar 4 moedas de 1 centavo pra pagar os 9 centavos de tantos preços que a gente vê por aí.

Ou então o jeito é continuar doando o troco pra alguma instituição mesmo.

forinti disse...

Talvez uma sistema binário seja ainda melhor. Um real poderia ter 128 centavos e poderíamos ter moedas de 1, 2, 4, 8, 16, 32 e 64 centavos.

9 centavos seriam 1+8. 65 centavos seriam 64+1.

Acho que base 10 é um atraso.