quarta-feira, 27 de maio de 2015

Conversão de base sem ifs

Já perdi a conta do número de vezes que tive que enfrentar pequenas séries durante entrevistas de emprego. E sempre tive medo de que minha solução, mesmo sendo verdadeira, não fosse considerada pelo entrevistador.
Por exemplo, se um candidato fosse apresentado a "2,3,4", 82000 seria uma resposta perfeitamente razoável para o próximo elemento da série. Essa é a série de números que podem ser escritos usando apenas os dígitos 1 e 0 na enésima base e também em todas as anteriores.
Por exemplo, 4 na base 4 é 10, na base 3 é 11, na base 2 é 100.
O número 82000 até a base 5 tem as seguintes formas:
    • Em base 2 = 10100000001010000;
    • Em base 3 = 11011111001;
    • Em base 4 = 110001100;
    • Em base 5 = 10111000;
Por essas, nunca gostei desses exercícios como prova, embora os curta como diversão.
Em Perl, escrevi uma pequena função para converter para uma base até 32:

{
  use integer;
  my @digits=split(//,'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ');
  sub to_base {
    my $n=shift;
    my $base=shift;
    if($n<$base) {
      return $digits[$n];
    } else {
      return to_base($n/$base, $base) . $digits[$n%$base];
    }
  }
 }
Para ir além da base 32, bastaria adicionar novos símbolos. De qualquer forma, achei que seria mais interessante retirar a recursão e também o if.

{
  my @digits=split(//,'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ');
  sub to_base {
    my $n=shift;
    my $base=shift;
    join '', 
      reverse 
        map { $digits[int(($n%($base**($_+1)))/($base**$_))] }
          0..int(log($n)/log($base));
  }
}
A solução advém do fato de que podemos calcular qualquer dígito sem olhar os demais e que podemos calcular quantas casas serão necessárias para uma determinada base (com log(n)/log(b), sendo n o número e b a base).

Então, temos dígitos até log(n)/log(b): de b0 até blog(n)/log(b). Para saber o valor de um dígito, tiramos o resto da divisão de n por b na potência da casa subsequente (eliminando assim, todos os dígitos à esquerda). Depois dividimos por b na potência da respectiva casa e eliminamos a parte fracionária (eliminando assim, os dígitos à direita).

A função log(), vale lembrar, produz o logaritmo natural.

Por exemplo, 167 em base 10, requer log(167)/log(10)+1 dígitos (2,222+1=3). O valor dos dígitos em base 10, obtemos assim:
  1. 167 mod 1000 = 167 => 167/100 = 1;
  2. 167 mod 100 = 67 => 67/10 = 6;
  3. 167 mod 10 = 7 => 7/1 = 7.
E para base 8:
  1. 167 mod 512 (8*8*8) = 167 => 167/64 (8*8) = 2;
  2. 167 mod 64 = 39 => 39/8 = 4;
  3. 167 mod 8 = 7 => 7/1 = 7.
Mais um triunfo para a programação ifless.

Nenhum comentário:

Postar um comentário