Problema 7.3

.
Enunciado
Una companía aerea requiere implementar un sistema de fidelización de clientes mediente un "Programa de Pasajeros Frecuentes" (PPF). La idea es premiar a quienes más viajan por la aerolínea pasajes gratis a diferentes destinos según la cantidad de millas que lleven acumuladas en función de los viajes realizados.

Se dispone de los siguientes archivos.

VIAJES.dat (ordenado por el campo nroSocio)

• nroSocio - (9 dígitos)
  
• idCdadOri - (1 a 25)
  
• idCdadDes - (1 a 25)
  
• fecIda - (aaaammdd)
  
• fecReg - (aaaammdd)
  
• categ - (1 caracter, T = "turista", P = "primera", B = "business")
• flgTray - (1 dígito, 1 = "ida", 2 = "ida y vuelta")

Este archivo tiene la información de todos los viajes realizados por los pasajeros registrados en el programa PPF durante el año a procesar. Cabe aclarar que un mismo socio puede haber realizado más de un viaje dentro del año en proceso.

DESTINOS.dat (máximo 25 registros)

• idDestino
• descripcion

Contiene la información de los destinos (ciudades) a los cuales llegan los vuelos de la aerolínea.

DISTANCIAS.dat (máximo 25 x 25 registros)

• idCdad1
• idCdad2
• distancia - (word, expresado en millas)

Indica la distancia que existe entre un destino y otro. Para simplificar no consideraremos la posibilidad "tramos" o escalas. Las distancias son directas entre ciudad y ciudad.

PREMIOS.dat (ordenado por el campo millasHasta)

• millasHasta - (word)
• idDestino
  

A lo sumo 25 registros, indica cuantas millas son necesarias para acceder a cada destino de los que están en el programa.


Se pide
1 - Grabar un archivo con la información de los socios que resultarán beneficiados con viajes gratis en función de las millas que acumularon en sus vuelos. El archivo debe tener la siguiente información.

BENEFICIADOS.dat (ordenado por idDestino)

• nroSocio
• millasAcum
• idDestino

2 - Emitir un listado ordenado por destino, indicando por cada destino cuantos pasajes serán entregados en concepto de premio.


Análisis
La idea para resolver este problema es la siguiente: recorrer el archivo VIAJES.dat con corte de control por nroSocio, acumulando las millas de los vuelos de cada socio para luego determinar que destino le corresponderá como premio.

Veamos la sección type (solo la parte de definición de archivos y registros). Las estructuras con las cuales resolveremos el problema las analizaremos más adelante, a medida que las vayamos deduciendo.

   1:
   2:type
   3:   // registro y archivo VIAJES.dat
   4:   RViaje = record
   5:      nroSocio: longint;
   6:      idCdadOri: byte;  // id origen
   7:      idCdadDes: byte;  // id destino
   8:      fecIda: longint;
   9:      fecReg: longint;
  10:      categ: char;
  11:      flgTray: byte; // flag trayecto
  12:   end;
  13:
  14:   FViajes = file of RViaje;
  15:
  16:   // registro y archivo DESTINOS.dat
  17:   RDestino = record
  18:      idCdad: byte;
  19:      descripcion: string[30];
  20:   end;
  21:
  22:   FDestinos = file of RDestino;
  23:
  24:   // registro y archivo DISTANCIAS.dat
  25:   RDistancia = record
  26:      idCdad1: byte;
  27:      idCdad2: byte;
  28:      distancia: word;
  29:   end;
  30:
  31:   FDistancias = file of RDistancia;
  32:
  33:
  34:   // registro y archivo PREMIOS.dat
  35:   RPremio = record
  36:      millasHasta: word;
  37:      idDestino: byte;
  38:   end;
  39:
  40:   FPremios = file of RPremio;
  41:
  42:   // registro y archivo de salida BENEFICIADOS.dat
  43:   RBeneficiado = record
  44:      nroSocio: longint;
  45:      millasAcum: word;
  46:      idCdad: byte;
  47:   end;
  48:
  49:   FBeneficiados = file of RBeneficiado;
  50:
  51:   // :
  52:   // continua mas abajo
  53:   // : 
  54:

Teniendo la cantidad de millas acumuladas por cada usuario (luego del corte de control) el problema se limita a calcular que premio le corresponde al usuario (si es que le corresponde algún premio) y luego generar el archivo de salida BENEFICIADOS.dat. Analicemos estos dos puntos por separado.


Calcular el premio que le corresponde a un usuario

Para resolver esto tendremos que agilizar el acceso a los archivos DISTANCIAS.dat y PREMIOS.dat.

El archivo de distancias contiene la distancia (en millas) que existe entre una ciudad (idCdad1) y otra (idCdad2). Por lo tanto, al estar (los códigos de ciudad) numerados entre 1 y 25 podemos utilizar una matríz de 25 por 25 en la cual almacenar la distancias existentes entre una y otra ciudad. Además, tenemos el archivo DESTINOS.dat que contiene los códigos y descripciones de las ciudades a las cuales llega la aerolínea. Para manejar toda esta información utilizaremos la siguiente estructura:

El gráfico muestra un array de strings de (a lo sumo) 25 elementos donde cada elemento contiene la descripción de cada uno de los destinos (ciudades) posibles. Este array es paralelo a las columnas de una matríz de (a lo sumo) 25 por 25 elementos donde cada elemento representa la distancia existente entre las ciudades representadas por la intersección [fila,columna].

Por ejemplo: llamemos al array aDest y a la matríz mDist entonces (según el gráfico) entre la ciudad aDest[1] la ciudad aDest[2] hay una distancia de 800 millas.

Con esto, por cada viaje de cada pasajero podemos saber cuantas millas debemos acumular accediendo a aMat[idCdadOri,idCdadDest]. Además, si flgTray es 1 ("ida y vuelta") debemos multiplicar ese valor por 2.

Luego de acumular las millas totales acumuladas por el socio tenemos que consultar la información del archivo PREMIOS.dat para conocer el idCdad que le corresponde en función de las millas acumuladas. Para esto "subiremos" el archivo a un array de registros tipo RPremio como el que vemos a continuación:

El archivo de premios está ordenado ascendentemente por el campo millasHasta por lo tanto para averiguar que destino (ciudad) le corresponde como premio a un socio que acumuló una cantidad de millas simplemente debemos recorrer el array (aPremios) mientras aPremios[i].millasHasta sea menor que las millas acumuladas. Es decir: el mayor valor de millasHasta de los valores menores a la cantidad acumulada.

Notemos que el array tiene 25 posiciones pero no necesariamente todas estarán ocupadas. Recordemos que la aerolínea opera "en a lo sumo" 25 destinos (no conocemos la cantidad exacta y la llamamos genericamente n). De esos n destinos no necesariamente todos estarán en promoción por eso este array puede tener 25 elementos, n elementos u otro valor menor a n. Lo llamamos m.

Veamos la parte de la sección type en la que definimos estas estructuras.

   1:
   2:   // array de destinos
   3:   ADestinos = array[1..25] of string;
   4:
   5:   // matriz de distancias
   6:   MDistancias = array[1..25]
   7:              of array[1..25] of word;
   8:
   9:   // array de premios
  10:   APremios = array[1..25] of RPremio;
  11:
  12:   // :
  13:   // todavia hay mas... continua mas abajo
  14:   // :  
  15:

Con esto podemos plantear el desarrollo de dos funciones que utilizaremos luego para resolver el problema pedido.

La función obtenerMillas recibe el código de ciudad desde (idOri), el código de ciudad hasta (idDest), el flgTray que indica si el viaje fue "ida y vuelta" y la matríz de distancias y retorna las millas que corresponde asignar a este viaje que, basicamente están dadas por el elemento aMat[idOri,idDest] multiplicado por 1 o por 2 según flgTray sea 0 o 1.

La función obtenerPremio recibe las millas acumuladas por un socio de PPF, el array de premios y la cantidad de elementos útiles del array (m) y retorna el código de ciudad que le corresponde como premio al pasajero o un valor negativo si las millas acumuladas no son suficientes como para acceder al menor de los premios previstos.

Generar el archivo de salida

Teniendo resueltas las dos funciones anteriores con las cuales podemos determinar facilmente cuantas millas suma cada viaje y que premio corresponde a una cantidad acumulada de millas podemos concentrarnos de lleno en resolver el tema centrar del problema.

El enunciado pide un archivo con los pasajero que resultarán premiados según los viaje que realizaron durante el año. El problema es que, además, este archivo debe estar ordenado por destino (idCdad).

Si no nos impusieran este orden (por idCdad) el problema sería mucho más simple ya que con un corte de control por idSocio sobre el archivo de viajes podemos acumular las millas del socio y luego, al cortar podemos obtener el premio que corresponde asignarle. Entonces, si le corresponde premio grabamos el registro en el archivo de beneficiados. Claro que en este caso el archivo resultará ordenado por idSocio ya que VIAJES.dat tiene ese orden.

Como debemos respetar el orden por idCdad entonces tenemos que pensar en diseñar una estructura en la cual ir almacenando la información que vamos procesando del archivo de viajes, de forma tal que la salida vaya quedano ordenada con el orden que nos piden.

El gráfico ilustra un array de 25 elementos donde cada uno es un registro con un contador y puntero a una lista con información de los pasajeros a los que se los premiará con el destino cuyo código corresponde con la posición del array.

Con esta estructura, recorriendo el archivo VIAJES.dat con corte de control acumulamos las millas de cada socio y al cortar invocamos a la función obtenerPremio para averiguar el destino que le corresponde. Luego insertamos un nodo en la lista apuntada por el array (en la posición correspondiente al destino indicado) y sumamos 1 al contador de forma tal que al finalizar el proceso tendremos por cada destino la cantidad de pasajes a entregar y la lista de beneficiados.

Recorriendo el array podemos generar el archivo de salida con el orden que nos piden y también podemos emitir el listado requerido en el punto 2 del enunciado.

Veamos entonces la tipificación de datos de esta estructura y luego analizaremos el programa principal.

   1:
   2:   // nodo y puntero a nodo de lista de beneficiados
   3:   PNBeneficiado = ^NBeneficiado;
   4:   NBeneficiado = record
   5:      nroSocio: longint;
   6:      millasAcum: word;
   7:   end;
   8:
   9:   // tipo de registro y array de viajes asignados
  10:   RDestAsignados = record
  11:      cont: integer;
  12:      lst: PNBeneficiado;
  13:   end;
  14:   ADestAsignados = array[1..25] of RDestAsignados;
  15:
  16:   // 
  17:   // fin seccion type
  18:   // 
  19:

Ahora si, podemos ver el diagrama del programa principal.

El programa comienza invocando a los procedimientos:

• inicializarADestAsign - recibe (por referencia) el array aDestAsign, lo recorre asignando NIL a los punteros y 0 a los contadores.
• subirArchPremios - recibe (por referencia) el array aPrem y m. Sube todo el archivo PREMIOS.dat a aPrem y asigna a m la cantidad de elementos insertados en el array (a lo sumo 25). Notemos el el archivo de premios solo es necesario en este procedimiento por eso no lo recibimos como parámetro. Simplemente lo abrimos, lo usamos y lo cerramos dentro del procedimiento.
• subirArchDistancias - idem anterior pero con la matríz mDist y n.

Luego abrimos los archivos de viajes y beneficiados asignándolos a las variables archViajes y archBenef respectivamente. El primero para lectura y el segundo para escritura.

Para barrer (recorrer) archViajes utilizamos la función leerViajes que returna true o false según queden o no registros por leer en el archivo y (si retornó true) asigna en reg el registro leido.

Luego comienza el recorrido del archivo archViajes con corte de control por codSocio.

Mientras procesamos los registros (viajes) de un mismo socio simplemente acumulamos las millas. Estos lo hacemos invocando a la función obtenerMillas que fue analizada y desarrollada más arriba.

Cuando llega el corte (porque leimos un registro (viaje) de otro socio) invocamos a la función obtenerPremio (analizada y desarrollada más arriba) para determinar que premio le corresponde al socio cuyos viajes terminamos de procesar. Si le corresponde algún premio (la función retornó un valor mayor que cero) entonces invocamos al procedimiento procesarPremio que recibe el idCdadPrem, las millas acumuladas, el nroSocio y el array aDestAsign y todo lo que hace es colgar un nodo en la lista aDestAsign[idCdadPrem].lst e incrementar el contador aDestAsign[idCdadPrem].cont.

Para finalizar, el procedimiento generarArchivoBenef recorre el array aPrem, y por cada posición accede a aDestAsign[aPrem[i].idDestino] para recorrer la lista de pasajeros beneficiados con ese destino y así generar el archivo de bejeficiados con el orden pedido.

Luego, el procedimiento emitirListado simplemente recorre el array aPrem. Llamemos id a aPrem[i].idDestino, entonces por cada posición imprime aDest[id] y aDestAsign[id].cont.





Algoritmos y Estructuras de Datos - UTN - UBA

.