Tarea 2 de Software de Base (2006 Otoño)
Fecha de entrega: 20 de octubre de 2006 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 2560*S[0] + 2561*S[1]
+ 2562*S[1] + ... + 256L-1*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[0] + 256*(S[1] + 256*(S[2] + ... + 256*(S[L-2] + 256*S[L-1]) ... )) 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
SB2006P
TA2222P
CASAS
entonces deberá producir como salida
3
0
1 0
3 2
0 0
6 0
1 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
(2560*72 + 2561*79 + 2562*76 + 2563*65)
módulo 7 = 1095520072 módulo 7 = 3. La otra forma de
calcularlo es (72 + 256*(79 + 256*(76 + 256*65))) módulo 7 = (72
+ 256*(79 + 256*(76 + 1))) módulo 7 = (72 + 256*(79 + 256*77))
módulo 7 = (72 + 256*(79 + 0)) módulo 7 = (72 + 256*79)
módulo 7 = (72 + 1) módulo 7 = 73 módulo 7 = 3.
De la misma forma, el código de CASAS
es 1 y esa lista está vacía; el código de HALO es
3, que es el mismo que el de HOLA; el código de SB2006P es 0 y
esa lista está vacía; el código de TA2222P es 6 y
esa lista está vacía; mientras que el código de
CASAS es 1, pero esa palabra ya estaba en esa lista. Observe que las
listas 2, 4 y 5 quedan vacías, la lista 0 contiene a SB2006P, la
lista 1 contiene a CASAS, la lista 3 contiene a HOLA y HALO, mientras
que la lista 6
sólo contiene a TA2222P.