Tarea 2 de Software de Base
Trimestre 2007 Primavera
Entrega: 31 de mayo de 2007 a las 22:00.
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 codigoZZ.c,
codigoZZ.cpp, codigoZZ.java o codigoZZ.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. 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
SBI
TAP
CASAS
entonces deberá producir como salida
3
0
1 0
3 2
3 2
0 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*16716) módulo 7 = 72 + 256*(79 + 256*0)
módulo 7 = 72 + 256*79 módulo 7 = 72 + 256*2
módulo 7 = 584 módulo 7 = 3.