Tarea 2 de Software de Base (2006P)
Fecha de entrega: 16 de mayo 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). Sume los valores
S[0]+S[1]+...+S[L-1], es decir, los códigos ASCII de todos los
caracteres de la cadena. 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.
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
5
0
6 0
5 2
2 0
2 2
6 1
ya que: la suma de los caracteres de HOLA es 'H'+'O'+'L+'A' =
72+79+76+65 = 292 y 292 módulo 7 es igual a 5 y esa lista
está vacía; de la misma forma, el código de CASAS
es 6 y esa lista está vacía; el código de HALO es
5, que es el mismo que el de HOLA; el código de SB2006P es 2 y
esa lista está vacía; el código de TA2222P es 2,
que es el mismo que el de SB2006P; mientras que el código de
CASAS es 6, pero esa palabra ya estaba en esa lista. Observe que las
listas 0, 1, 3 y 4 quedan vacías, la lista 2 contiene a SB2006P
y TA2222P, la lista 5 contiene a HOLA y HALO, mientras que la lista 6
sólo contiene a CASAS.