Tarea 2 de Software de Base (2007 Invierno)
Fecha de entrega: 16 de febrero de 2007 a las 10pm
Una función de
dispersión es una función a la que se le da una
cadena y que a partir de ella calcula un número (llamado código de dispersión)
en cierto rango. Una tabla de
dispersión permite hacer búsquedas rápidas
a través del cálculo de una función de
dispersión. Supongamos que tenemos un rango del 0 al N-1 (para
un cierto valor de N) y una función de dispersión F que
produce valores en ese mismo rango. Hagamos un arreglo con N listas
(originalmente vacías). Cuando queramos insertar una cadena
S a
la tabla, calculamos su código de dispersión F(S) e
insertamos S a la lista que está en la posición F(S) del
arreglo. En este momento pueden ocurrir tres cosas: [caso 0] que esa
lista esté vacía (simplemente
insertamos a S en la lista), [caso 1] que S ya esté en la
lista (y entonces no la insertamos) y [caso 2] que la lista no
esté vacía pero que no contenga a S (insertamos a S
en la
lista y a esto lo llamamos una colisión).
Existen muchas formas de calcular códigos de dispersión y
aquí presentaremos una de ellas. Sea N un número
positivo
y S una cadena de longitud L (vamos a suponer que S está en un
arreglo de caracteres escritos en ASCII). Sean S[0], S[1], ..., S[L-1]
los códigos ASCII de todos los
caracteres de la cadena y calcule el valor de 256L-1*S[0] +
256L-2*S[1]
+ 256L-3*S[2] + ... + 2561*S[L-2] + 2560*S[L-1].
Al resultado
sáquele módulo N y
ese es el código de S. Observe
que esto es distinto a lo que hicimos en clase. También
observe que ese número también se puede calcular como
S[L-1] + 256*(S[L-2] + 256*(S[L-3] + ... + 256*(S[1] + 256*S[0]) ... ))
y
que el módulo N se puede calcular a cada paso de esta
expresión.
Escriba un programa de nombre codigo.c,
codigo.cpp, codigo.java o codigo.f77 que lea de la
entrada estándar dos números N y M separados por un
espacio y luego M líneas con una cadena formada por entre 1 y 8 letras
mayúsculas y dígitos cada una de ellas. Su programa
debe de escribir en la salida estándar M líneas, una
por
cada cadena en la entrada, cada una de ellas conteniendo dos enteros
separados por un espacio: el código de dispersión de la
cadena seguido de un número 0, 1 ó 2 según
cuál de los tres casos descritos arriba haya sucedido.
Como ejemplo, si su programa recibe la entrada
7
6
HOLA
CASAS
HALO
SB2007I
TA2222P
CASAS
entonces deberá producir como salida
4
0
2 0
4 2
5 0
4 2
2 1
Como ejemplo, recuerde que 'H' = 72, 'O' = 79, 'L' = 76 y 'A' = 65,
entonces la función de dispersión de la cadena "HOLA" es
(2563*72 + 2562*79 + 2561*76 + 2560*65)
módulo 7 = 1213156417 módulo 7 = 4. La otra forma de
calcularlo es (65 + 256*(76 + 256*(79 + 256*72))) módulo 7 = (65
+ 256*(76 + 256*(79 + 1))) módulo 7 = (65 + 256*(76 + 256*80))
módulo 7 = (65 + 256*(76 + 5)) módulo 7 = (65 + 256*81)
módulo 7 = (65 + 2) módulo 7 = 67 módulo 7 = 4.
De la misma forma, el código de CASAS
es 2 y esa lista está vacía; el código de
HALO es 4, que es el mismo que el de HOLA; el código de SB2007I
es 5 y
esa lista está vacía; el código de TA2222P es
4, que es el mismo que el de HOLA; mientras que el código
de
CASAS es 2, pero esa palabra ya estaba en esa lista. Observe que las
listas 0, 1, 3 y 6 quedan vacías, la lista 2 contiene a
CASAS, la lista 4 contiene a HOLA, HALO y TA2222P y la lista 5 contiene
a SB2007I.