domingo, 5 de setembro de 2010

Ciclos à toa

Ontem escutei que a "natureza é sábia" e imediatamente retruquei que não é, porque faz tudo por tentativa e erro. Só vemos os sucessos; os erros não sobrevivem por muito tempo.

Resolvi procurar algum problema simples que possa ser resolvido por força bruta, mas nada tão sofisticado como programação genética. Então, montei um pequeno programa em Perl para procurar as melhores frações para determinado número. Para tornar o exercício um pouco mais interessante, o programa produz as melhores frações de até n dígitos.

my $n=$ARGV[0];

for my $d (1..5) {
my $v=0;
my $vx, $vy;

for my $x (1..(10**$d-1)) {
for my $y (1..(10**$d-1)) {
my $t=$x/$y;
($v,$vx,$vy)=($t,$x,$y) if abs($n-$t)<abs($n-$v);
print "$x/$y ($v)\r";
last if $t<$n-0.1;
}
}
print "Melhor opção de $d dígitos: $vx/$vy ($v)\n";
}

O programa recebe um número $n pela linha de comando e compara cada tentativa $t com o vitorioso $v. Para otimizar um pouco a busca, o laço do $y termina quando o número estiver ficando menor que o alvo.

Não procurei otimizar mais, porque preciso de tempo para o café e o computador não reclama mesmo.

Para cada tentativa, o programa imprime os valores de $x e $y testados e a melhor fração até o momento.

Com o número e obtive o seguinte:

>fracoes.pl 2.71828183
Melhor opção de 1 dígitos: 8/3 (2.66666666666667)
Melhor opção de 2 dígitos: 87/32 (2.71875)
Melhor opção de 3 dígitos: 878/323 (2.71826625386997)
Melhor opção de 4 dígitos: 2721/1001 (2.71828171828172)
Melhor opção de 5 dígitos: 72396/26633 (2.7182818308114)

E com pi, antes de terminar a execução:

>fracoes.pl 3.1415926535
Melhor opção de 1 dígitos: 3/1 (3)
Melhor opção de 2 dígitos: 22/7 (3.14285714285714)
Melhor opção de 3 dígitos: 355/113 (3.14159292035398)
Melhor opção de 4 dígitos: 355/113 (3.14159292035398)
18425/1295 (3.14159292035398)

Nenhuma opção de 4 dígitos é melhor que a de 3, então o 355/113 saiu repetido.

Buscar os 5 dígitos é um pouco demorado, mas ainda é melhor do que procurá-los com nanquim e papel. E uma fração de 6 dígitos seria difícil de memorizar, logo teria pouca utilidade prática.

Nenhum comentário: