MOD. II, UND. 5, OBJ.5
1.-Lea con atención el siguiente planteamiento:
Un vendedor para poder promocionar un producto, recorre varios
regiones de Estados Unidos, y para realizar este recorrido debe
escoger la ruta mas óptima es decir, la menos costosa en términos de
gastos en hospedaje y tiempo. En la Fig. 1, este recorrido esta
representado desde el punto 1 (estado 1) hasta el punto 10 (estado
10). Ver Fig. Nº 1 y Tabla No.1.
Rutas posibles del Vendedor
Fig. Nº 1
[title ]l a figura y la tabla esta anexada en imágenes [/title]
Características:
1-Ese problema está dividido en etapas donde se requiere una
política de decisión en cada una de ellas.
2- Cada etapa tiene determinada información que sirve para
determinar la decisión más óptima.
3-El efecto de la política de decisión en cada etapa es transformar el
estado actual en un estado asociado con la siguiente etapa.
4-Dado el estado actual, una política óptima para las etapas restantes
es independiente de la política adoptada en etapas anteriores.
5- El procedimiento de solución se inicia al encontrar la política óptima
para la última etapa.
6-Se dispone de una relación recursiva que indica la política óptima
para la etapa (n+1).
Con estos conceptos previos, se le pide elabore un programa en
lenguaje de programación Pascal que genere:
1· La cantidad de etapas en que se puede realizar el viaje del punto 1
al punto 10.
2· Cálculos para cada etapa utilizando la información matemática
dada.
3· Visualizar mediante gráficos cada una de las etapas del recorrido
del vendedor, utilizando la matriz dada en la Tabla N°1, la cual se
muestra en la siguiente página, donde están todos los nombres de
los estados con la ciudad y distancia desde el punto 1.
·4 Imprima los gráficos junto con la información dada en la tabla No.1
Tabla No.1
Estados a recorrer de la Ruta del Vendedor
Nombre Posición Hospedaje(Us$) Ciudad. Distancia (Kms.)
Nuevo México 1 120 Alburquerque --
Oklahoma 2 120 Oklahoma City 826,94
Arkansas 3 130 Little Rock 1.306,48
Tennessee 4 120 Nashville 1.794,45
Texas 5 140 Houston 941,83
Luisiana 6 150 Baton Rouge 1.535,56
Misisipi 7 130 Memphis 1.506,01
Alabama 8 140 Montgomery 1.901,33
Georgia 9 150 Atlanta 2.041,78
Florida 10 150 Tallahassee 2.148,67
2. Con la tabla No.1 que se presenta en el Obj.No.5, desarrolle un
programa en PASCAL, que construya una estructura tipo hashing o
dispersión, para almacenar los nombres de los estados por su posición
dada en la tabla, en un archivo tipo texto. El programa se hará bajo
las siguientes consideraciones:
A través del archivo de texto, extraiga el nombre de cada estado y
ubíquelo en la estructura mencionada.
· Imprima el nombre del estado a medida que lo inserta en la
estructura y el número de la celda, para ello utilice una función de
hashing,
Función hashing: consiste en la suma de las posiciones en el alfabeto
de las letras (codificación ASCII) que conforman el nombre del estado.
Como se indica a continuación:
f (nombre_estado)= ( Σ Li) mod r (esta formula esta en la 2 imagen)
en donde Li es el código ASCII de cada letra que forma el nombre del
estado, r es el número de entradas de la tabla de hashing o número
de buckets o slots. Las tablas de Codificación ASCII (también llamada
asqui), las cuales se presentan en la siguiente página, identificadas
como Tabla 2 y 3, servirán para la realización de los cálculos, tal y
como se presentan en el siguiente ejemplo:
Ejemplo: si se va a construir la “llave” para una tabla de 200 slots( de
0 a 199), y se desea insertar el nombre Texas, de acuerdo a los
códigos ASCII ( ver tabla ASCII), la construcción de la “llave” será la
siguiente:
Valor = Cod(T) + Cod (e) + Cod (x) + Cod (a) + Cod (s) = 84 + 113 +
120 + 97+115 = 1012
Valor mod r = 529 mod 199 = 131 (resto de la división entera).Por lo
tanto la palabra Texas se insertará en una lista asociada a la celda (o
slot) 131.
Tabla No.2 ASCII (mayúsculas)
Símbolo Valor ASCII Símbolo Valor ASCII
A 65 N 78
B 66 O 79
C 67 P 80
D 68 Q 81
E 69 R 82
F 70 S 83
G 71 T 84
H 72 U 85
I 73 V 86
J 74 W 87
K 75 X 88
L 76 Y 89
M 77 Z 90
Tabla No.3 ASCII (minúsculas)
Símbolo Valor ASCII Símbolo Valor ASCII
a 97 n 110
b 98 ñ 241
c 99 o 111
d 100 p 112
e 101 q 113
f 102 r 114
g 103 s 115
h 104 t 116
i 105 u 117
j 106 v 118
k 107 w 119
l 108 x 120
m 109 y 121
z 122
MOD. III, UND. 7, OBJ.7
3. Elabore un procedimiento de búsqueda en Pascal, de tal forma
que, toda vez dados los nombres de los estados, se busque en la tabla
de hashing y se imprima la celda a la cual está asignada.
Instrucciones generales sobre el Trabajo Práctico
Para considerar el logro de cada uno de los objetivos, el estudiante
debe entregar lo siguiente:
· Listado documentado del programa fuente. En el encabezado de
cada procedimiento, función o sección de programa que lo requiera,
debe incluir un breve comentario del proceso que se realiza o del
método que aplica. Igualmente es conveniente hacerlo en la
definición de las estructuras de datos y variables utilizadas.
· Listado de los resultados.
· CD (Disco Compacto) que contenga el programa fuente (.PAS) y el
programa ejecutable (.EXE), debidamente identificado. Si utiliza
unidades modulares (units) en PASCAL, debe incluirlas.
Recomendaciones
· Emplee nombres de variables, constantes, funciones y
procedimientos alusivos a lo que representan.
· Utilice un diseño modular para la resolución del problema. Esta
estructura aportará legibilidad y facilidad de comprensión, además
evitará redundancias en los procesos. Evite variables globales en
las funciones y procedimientos. Emplee parámetros en los mismos,
determine cuáles son parámetros valor y cuáles parámetros
variables.
· Desarrolle algoritmos eficientes.
· Elabore procedimientos de validación de la data y de detección de
errores para evitar interrupciones inesperadas en la ejecución del
trabajo.
·
Crear cuenta
