IF672 -
Algoritmos e Estruturas de Dados
novembro 2002
a março 2003
1 - Função Hashing trivial
Considere uma seqüência
binária b0b1b2...bn (0's e
1's).
Essa questão tem como objetivo principal a indexação direta dessas seqüências.
O problema é encontrar um função Hashing para essas seqüências de tal forma
que:
Se duas string s1 e s2, forem tais que s1 < s2, então f(s1) < f(s2).
Ou seja f(0000) = 0, f(0001) = 1, f(0010) = 2, etc...
Entrada e Saída de dados
A entrada consiste em várias linhas.
Para cada linha teremos
um
inteiro N e uma
seqüência Bi com
N dígitos (0's e 1's).
O fim do arquivo corresponde ao final da entrada.
A saída consiste
de
um valor K correspondente ao F(Bi) (< Maior Inteiro) para cada
linha da entrada.
Entrada exemplo
7 0000101
4 1100
4 1110
4 0010
5 11111
6 111111
6 001101
1 0
1 1
Saída correspondente
5
12
14
2
31
63
13
0
1