Capítulo 4

se dispo.
Corte de Control

Los problemas de corte de control tienen la característica de que el conjunto de los datos puede verse dividido en varios subconjuntos que contengan datos relacionados. Entonces es posible, a medida que se van leyendo los datos, brindar información referida a cada subconjunto y al conjunto en general.

El siguiente problema ilustra un caso típico de corte de control por una variable.


Problema 4.1
Una empresa de colectivos maneja varias líneas, cada una de las cuales cuenta con varios coches. Se dispone de un conjunto de registros con la siguiente información:

• nroLinea
• nroCoche
• recMes (recaudación mensual del coche)
  

Los datos están ordenados por nroLinea de forma tal que todos los registros correspondientes a la recaudación de los coches de una misma línea se encuentran agrupados. Finaliza con un registro con nroLinea = -1, nroCoche = -1, recMes = -1.

Se pide:

1. Por cada línea, coche de mayor recaudación y recaudación del mismo.
2. Por cada línea, recaudación promedio de sus coches.
   
3. Por cada línea, total recaudado.
   
4. Cual fue la línea de mayor recaudación.
5. Recaudación total de la empresa.
6. Recaudación promedio de las líneas de la empresa.
   

Análisis
Primero analicemos un ejemplo de como podrían venir los datos.

Hay 3 registros que corresponden a coches de la línea 1. Luego 2 registros que corresponden a la línea 2. 4 registros para la línea 3 y 2 registros para la línea 4. Por último el fin de datos identificado con (-1, -1, -1).

Siguiendo los datos de ejemplo podemos también identificar cuales son los resultados que nuestro programa tiene que brindar para este lote de datos.

• Por cada línea, coche de mayor recaudación y recaudación del mismo: Línea 1 (coche 42, $200), Línea 2 (coche 57, $250), Línea 3 (coche 68, $300), Línea 4 (coche 2, $150).
• Recaudación promedio de los coches de cada línea: Linea 1 ($225), Línea 2 ($150), Línea 3 ($350), Línea 4 ($150).
• Total recaudado por cada línea: Linea 1 ($450), Línea 2 ($300), Línea 3 ($700), Línea 4 ($250).
• Línea de mayor recaudación: Línea 3 ($700).
• Racaudación total de la empresa: $1700.
• Recaudación promedio de las líneas de la empresa: $425.

Notemos tambien que los puntos 1,2 y 3 del enunciado se pueden informar luego de procesar los registros de cada una de la líneas. En cambio, para los puntos 4, 5 y 6 será necesario procesar la totalidad de los registros antes de poder informar los resultados.

Para un problema de corte de control es fundamental el hecho de que los datos estén ordenados por la variable que identifica al grupo (en este caso nroLinea). Esto nos garantiza que al finalizar el proceso de los datos de un grupo comenzaremos con los datos del próximo grupo y así.


Para resolver este problema tenemos que asegurarnos dos cosas:

• que nuestro programa lea todos los registros del lote de datos, desde el primero hasta el último y
  
• que podamos detectar cada vez que leamos un registro que corresponde al próximo grupo. Es decir: detectar que terminamos de procesar los registros de los coches de una línea y comenzaremos con los de la próxima.
  

Generalmente esto se resuelve con dos ciclos repetitivos anidados. Uno controla que no llegue el fin de datos y el otro (el interno) controla que los datos que se están procesando pertenezcan al mismo grupo.

En el diagrama vemos la estructura con la cual manejamos el corte de control. La secuencia es la siguiente:

1. Leemos los datos del primer registro (primera fila del lote de datos).
2. Mientras no sea el fin de datos (rec = -1) iteramos.
3. Asignamos a una variable auxiliar (lineaAnt) el nroLinea ingresado por el usuario.
4. Iteramos mientras no llegue el fin de datos y mientras nroLinea sea igual a lineaAnt.

Obviamente, al inicio (primer registro) las dos condiciones del ciclo iterativo interno se cumplen:

• rec <> -1 - Si ingresamos al ciclo externo, entonces se cumple que rec es distinta de -1
• lineaAnt = nroLinea - En la acción inmediatamente anterior asignamos a lineaAnt el valor de nroLinea por lo tanto es seguro que se verifica que son iguales.

Habiendo ingresado al ciclo iterativo interno, y luego de procesar los datos del registro (esto no está representado en el gráfico) volvemos a leer para obtener la información del próximo registro que, si no tiene rec = -1 y corresponde a la misma línea que el anterior entonces permanecerá dentro del ciclo interno.

Cuando leamos un registro que corresponda a la próxima línea no se cumplirá la condición del ciclo interno y este cortará.

Podemos diferenciar entonces diferentes partes o secciones del algoritmo.

cabLinea - En esta sección (o en este procedimiento) estamos a punto de comenzar a procesar los registros correspondientes a los coches de una línea. Aquí debemos asignar la variable de control (lineaAnt) e inicializar los contadores, máximos, mínimos y todas la variables que utilicemos para almacenar datos que son propios para cada línea y que deban volver a ser inicializados al comenzar a procesar los registros correspondientes a la próxima línea.

finLinea - Cuando el algoritmo llega a esta sección es porque terminó de procesar todos los registros que conforman un mismo grupo (coches de una misma línea). Entonces aquí debemos mostrar los resultados propios de cada grupo (en nuestro enunciado serían los puntos 1,2 y 3) y procesar la información para los totales generales.

proceso - En esta sección procesamos cada uno de los registros de un mismo grupo. Estamos plenamente seguros de esto porque el lote de datos está ordenado y (por otro lado) el ciclo interno controla que el registro leido pertenezca al mismo grupo que el registro anterior.

inicializar - Aquí inicializamos las variables que tengan información referente al total de los registros. Por ejemplo un contador de líneas (para saber cuantas líneas hay en la empresa), un máximo (para saber cual fue la línea de mayor recaudación), etc.

resultados - Aquí estamos en condiciones de mostrar los resultados generales. Los que involucran a la totalidad de los registros (en este caso los puntos 4,5 y 6).


Ahora si, podemos plantear la solución al problema.

Analizaremos cada uno de los items que nos pide el enunciado.

1 - Por cada línea, coche de mayor recaudación y recaudación del mismo.

Para resolver esto simplemente necesitamos un máximo (maxRec) y una variable (nroCocheMax) en la cual guardar el número de coche cuya recaudación vamos identificando que es mayor que las anteriores. El resultado esperado es por cada línea entonces la variable maxRec debe estar en cero antes de comenzar a procesar los registros de cada línea. Por este motivo la inicializamos en cabLinea con el valor cero (como hablamos de recaudaciones, cero resulta ser una cota inferior para el conjunto de valores posibles). En proceso vamos calculando la recaudación máxima por línea y en finLinea mostramos los resultados (maxRec, nroCocheMax).

2 - Por cada línea, recaudación promedio de sus coches.

Para obtener la recaudación promedio de cada línea necesitaremos un alumulador (sumRecaud) con el que iremos sumando la recaudación de cada uno de los coches y un contador (cantCoches) para contar la cantidad de coches y luego (en finLinea) calcular y mostrar el promedio dividiendo sumRecaud/cantCoches. Tanto sumRecaud como cantCoches deben inicializarse o cero en cabLinea.

3 - Por cada línea, total recaudado.

Este punto se resuelve aprovechando el acumulador sumRecaud definido en el punto anterior. Así que simplemente mostramos el resultado en finLinea.

4 - Cual fue la línea de mayor recaudación.

Al finalizar el proceso de los datos de cada línea (en finLinea) tenemos el total recaudado de la misma. Entonces podemos comparar este total con el máximo detectado hasta el momento (maxRecGral). Esta variable la inicializamos en inicializar ya que solo debe inicializarse una única vez al comienzo del programa. Recordemos que este máximo incumbe a todas las líneas por lo tanto no debe inicializarse al comienzo de cada una. Analogamente, el resultado recién estará disponible en resultados.

Notemos que para guardar la línea de mayor recaudación hasta el momento (nroLineaMax) utilizamos la variable lineaAnt. Esto se debe que si llegamos a finLinea es porque leimos el primer registro de la siguiente línea, pero en el número de línea anterior quedó almacenado en lineAnt.

5 - Recaudación total de la empresa.

Necesitamos una variable para acumular las recaudaciones de cada una de las líneas: recTotal.
En finLinea acumulamos en esta variable los valores de sumRecaud. Así, al finalizar el proceso de los datos de todas las líneas de la empresa la variable recTotal representará el total recaudado por la empresa.

6 - Recaudación promedio de las líneas de la empresa

Este dato lo obtenemos dividiendo la recaudación total por la cantidad de líneas que opera la empresa. Por lo tanto necesitamos un contador de líneas: cantLineas. Esta variable la incrementamos en finLinea ya que cada vez que el programa pase por este procedimiento será porque terminó de procesar los registros de los coches de una misma línea. O sea: proceso los datos una línea más.


Nota: La solución al problema 4.1 que hemos planteado supone que todos procedimientos tienen acceso a todas las variables del programa. Esto solo es posible si consideramos que las variables son variables globales.

Si bien todos los lenguajes de programación permiten utilizar variables globales, es una muy mala práctica y no la consideraremos válida en este trabajo. Sin embargo, para el análisis de los problemas de corte de control nos facilita su estudio al permitirnos identificar cada sección del programa (cabLinea, finLinea, proceso, etc).


Ahora veamos el código Pascal que resuelve el problema anterior.

problema4.1.pas

   1:
   2:procedure inicializar(var maxRecGral,recTotal: real;
   3:                      var cantLineas: integer);
   4:begin
   5:   maxRecGral:=0;
   6:   recTotal:=0;
   7:   cantLineas:=0;
   8:end;
   9:
  10:procedure resultados(nroLineaMax: integer
  11:                    ;maxRecGral,recTotal:real
  12:                    ;cantLineas:integer);
  13:begin
  14:   writeln('--- Resultados Generales ---');
  15:   write('Linea de mayor recaudacion:');
  16:   writeln(nroLineaMax,' $',maxRecGral:0:2);
  17:
  18:   write('Recaudacion Promedio de las lineas: $');
  19:   writeln((recTotal/cantLineas):0:2);
  20:
  21:   write('Recaudacion Total de la Empresa: $');
  22:   writeln(recTotal:0:2);
  23:end;
  24:
  25:procedure finLinea(nroCocheMax: integer
  26:                  ;maxRec,sumRecaud: real
  27:                  ;lineaAnt, cantCoches: integer
  28:                  ;var maxRecGral: real
  29:                  ;var nroLineaMax: integer
  30:                  ;var recTotal: real
  31:                  ; var cantLineas: integer);
  32:begin
  33:   writeln('-- LINEA:', lineaAnt,' ---');
  34:   write('Coche de mayor recaudacion:');
  35:
  36:   // al poner ":0:2" se mostrara el valor de la 
  37:   // variable con dos digitos decimales  
  38:   writeln(nroCocheMax,' $',maxRec:0:2);
  39:
  40:   write('Recaudacion Promedio de los coches: $');
  41:   writeln((sumRecaud/cantCoches):0:2);
  42:
  43:   write('Recaudacion total de la linea: $');
  44:
  45:   writeln(sumRecaud:0:2);
  46:
  47:   if( sumRecaud>maxRecGral ) then begin
  48:      maxRecGral:=sumRecaud;
  49:      nroLineaMax:=lineaAnt;
  50:   end;
  51:
  52:   recTotal:=recTotal+sumRecaud;
  53:   cantLineas:=cantLineas+1;
  54:end;
  55:
  56:procedure proceso(rec: real
  57:                 ;var maxRec: real
  58:                 ;var nroCocheMax: integer
  59:                 ; nroCoche: integer
  60:                 ;var sumRecaud: real
  61:                 ; var cantCoches: integer);
  62:begin
  63:   if( rec>maxRec) then begin
  64:      maxRec:=rec;
  65:      nroCocheMax:=nroCoche;
  66:   end;
  67:   sumRecaud:=sumRecaud+rec;
  68:   cantCoches:=cantCoches+1;
  69:end;
  70:
  71:procedure cabLinea(var lineaAnt:integer
  72:                  ;nrolinea: integer
  73:                  ;var maxRec: real
  74:                  ;var nroCocheMax: integer
  75:                  ;var cantCoches: integer
  76:                  ;var sumRecaud: real);
  77:begin
  78:   lineaAnt:=nroLinea;
  79:   maxRec:=0;
  80:   nroCocheMax:=0;
  81:   cantCoches:=0;
  82:   sumRecaud:=0;
  83:end;
  84:
  85:
  86:// ------------------------
  87:// -- PROGRAMA PRINCIPAL --
  88:// ------------------------
  89:
  90:var
  91:   // variables de ingreso de datos
  92:   nroLinea,nroCoche: integer;
  93:   rec: real;
  94:
  95:   // variable de control
  96:   lineaAnt: integer;
  97:
  98:   // variables por linea
  99:   maxRec: real;
 100:   nroCocheMax: integer;
 101:   sumRecaud: real;
 102:   cantCoches: integer;
 103:
 104:
 105:   // variables por empresa
 106:   maxRecGral, recTotal: real;
 107:   cantLineas: integer;
 108:   nroLineaMax: integer;
 109:
 110:begin
 111:   // llamamos a inicializar()
 112:   inicializar(maxRecGral,recTotal,cantLineas);
 113:
 114:   // llemos el primer registro
 115:   read(nroLinea, nroCoche,rec);
 116:
 117:   // iteramos mientras no llegue el fin de datos
 118:   while( rec<>-1 ) do begin
 119:
 120:      // invocamos a cabLinea()
 121:      cabLinea(lineaAnt
 122:              ,nrolinea
 123:              ,maxRec
 124:              ,nroCocheMax
 125:              ,cantCoches
 126:              ,sumRecaud);
 127:
 128:      // interamos mientras no llegue el fin y
 129:      // mientras los registros leidos correspondan
 130:      // a coches de la misma lenea
 131:      while((rec<>-1) AND (nroLinea=lineaAnt))
 132:      do begin
 133:
 134:         // invocamos a proceso()
 135:         proceso(rec
 136:                ,maxRec
 137:                ,nroCocheMax
 138:                ,nroCoche
 139:                ,sumRecaud
 140:                ,cantCoches);
 141:
 142:         // leemos el proximo registro
 143:         read(nroLinea, nroCoche,rec);
 144:
 145:      end;  // fin del while interno
 146:
 147:      // invocamos a finLinea()
 148:      finLinea(nroCocheMax
 149:              ,maxRec
 150:              ,sumRecaud
 151:              ,lineaAnt
 152:              ,cantCoches
 153:              ,maxRecGral
 154:              ,nroLineaMax
 155:              ,recTotal
 156:              ,cantLineas);
 157:
 158:   end; // fin del while externo
 159:
 160:   // invocamos a resultados()
 161:   resultados(nroLineaMax
 162:             ,maxRecGral
 163:             ,recTotal
 164:             ,cantLineas);
 165:
 166:end. // fin programa principal
 167:

Para probar este tipo de programas tendremos que ir ingresando "a mano" cada uno de los registros del lote de datos lo cual resulta bastante tedioso. Además, al tener que ingresar tantos datos existe la probabilidad de que ingresemos mal algúno con lo cual tendremos que volver a correr el programa y volver a ingresar todo nuevamente.

Para evitar esto podemos crear un archivo de texto con toda la información que queremos procesar con nuestro programa.

Por ejemplo:

problema4.1datos.txt

   1:  1    42    200
   2:  1    23    100
   3:  1    44    150
   4:  2    33     50
   5:  2    57    250
   6:  3     7    100
   7:  3     8    250
   8:  3    68    300
   9:  3    97     50
  10:  4     6    100
  11:  4     2    150
  12: -1    -1     -1
  13:

Las columnas representan nroLinea, nroCoche y rec respectivamente. Vemos también que finaliza con un registro (fila) con todos valores negativos.

Entonces, luego de compilar el programa podemos redireccionar la "standard input" para que el programa en lugar de tomar los datos por teclado los tome desde este archivo de datos.

Teniendo el archivo de texto en el mismo directorio que el programa ejecutable podemos utilizar la siguiente instrucción.

c:\>problema4.1 < problema4.1datos.txt

El resultado es el que se ve a continuación:

Corte de Control por 2 variables

Para analizar este tema vamos a reformular el problema 4.1 introduciendo algunas modificaciones.


Problema 4.1.1
Una empresa de colectivos maneja varias líneas, cada una de las cuales cuenta con varios coches, cada uno de los cuales operó varios días del mes.

Se dispone de un conjunto de registros con la siguiente información:

• nroLinea
• nroCoche
• dia (día del mes)
  
• recDia (recaudación diaria del coche)
  

Los datos están ordenados por nroLinea y luego por nroCoche de forma tal que todos los registros correspondientes a los coches de una misma línea se encuentran agrupados y todas las recaudaciones diarias de un mismo coche están agrupadas también. Finaliza con un registro con nroLinea = -1, nroCoche = -1, dia = -1, recDia = -1.

Se pide:

1. Por cada coche: disponibilidad y recaudación mensual.
   
2. Por cada línea: recaudación promedio de sus coches.
   
3. Recaudación total de la empresa.
4. Línea de mayor recaudación.

Análisis
Veamos un ejemplo de los datos y comparémoslo con el ejemplo que utilizamos para analizar el problema de corte de control por 1 variable.

Podemos ver que en este lote de registros disponemos de más información. En el caso anterior teníamos la recaudación mensual de cada coche. Ahora tenemos la recaudación diaria de cada coche, de forma tal que la sumatoria de las recaudaciones diarias logradas por un coche, en este lote de datos, es igual a la recaudación mensual del mismo coche en el lote de datos anterior.

Como el lote está ordenado por nroLinea y luego por nroCoche tambien podemos diferenciar grupos de registros: primero, un grupo principal identificado por nroLinea (una línea tiene varios coches). Luego, si solo miramos los registros de una misma línea podemos identificar un subgrupo identificado por nroCoche (un coche trabajó varios días).

Con estas consideraciones, si analizamos lo que nos pide el enunciado podemos ver que los diferentes ítems del enunciado se refieren a diferentes subconjuntos del lote de registros:

1 - Por cada coche: disponibilidad operativa y recaudación mensual.

Esta pregunta se refiere a cada coche, de cada una de líneas. Por ejemplo: para la línea 1, el coche 42 tuvo una disponibilidad operativa del 10% (3 días trabajados * 100 / 30 días del mes) y su recaudación mensual fué $200.

2 - Por cada línea, recaudación promedio de sus coches.

Para responder esta pregunta será necesario procesar todos los coches de la línea. Por ejemplo: línea 1: $150, línea 2: $150, etc.

3, 4 - Recaudación total de la empresa y Línea de mayor recaudación.

Estas preguntas se refieren al total de los datos. Para responderlas será necesario procesar todo el lote de registros.


También en este caso vamos a necesitar procesar todos los datos de forma tal que podamos "cortar" cada vez que se detecte un registro que corresponda a otro subgrupo (coches) y cada vez que se detecte un registro que corresponda a otro grupo (líneas).

La estructura para manejar un problema de corte de control por 2 variables implica 3 ciclos iterativos anidados: uno (el externo) controla que no llegue el fin de datos. El siguiente controla que los datos sean del mismo grupo (en este caso líneas) el siguiente (el más interno) controla que los datos sean del mismo subgrupo (en este caso coches).

En proceso estaremos procesando registros de un mismo coche, de una misma línea. Cada registro corresponde a la recaudación de un día de trabajo de ese coche. Por lo tanto en este procedimiento tendremos que acumular la recaudacion diaria (recCoche) para que luego, en finCoche, podamos mostrar la recaudación mensual (sumatoria de las recaudaciones diarias del coche). También en proceso necesitamos un contador (diasTrab) que cuente cuantos días trabajó el coche. Con esto podremos mostrar (en finCoche) la disponibilidad operativa (dias trabajados * 100 / 30).

Todas las variables que utilizaremos en proceso (diasTrab y recCoche) deben inicializarse en cero al comenzar a procesar los registros de cada coche. Esto lo haremos en cabCoche.

Al llegar a finCoche podemos mostrar la información que nos piden en el punto 1 del enunciado y tenemos que procesar la información que nos piden en el punto 2 (a nivel línea). Para esto necesitamos un reacumulador con el acumularemos las recaudaciones mensuales de los coches de la línea (recLinea) y un contador de coches (contCoches) para luego, en finLinea, mostrar la recaudación promedio de sus coches.

Las variables recLinea y contCoches deben inicializarse en cero al momento de comenzar con una nueva línea. Esto es: en cabLinea.

En finLinea mostramos los resultados del punto 2 y procesamos los datos que nos piden en el punto 3 y 4. Llegamos a finLinea con la recaudacion de cada línea (recLinea). Sacamos el máximo con este valor (maxRecLinea) para mostrarlo en resultados y reacumulamos para poder obtener la recaudacion total de la empresa (recEmpr).

Las variables maxRecLinea y recEmpr deben inicializarse antes de comenzar con el proceso de los datos ya que incumben al total de los registros. Se inicializan en inicializar.

En resultados podemos mostrar cual fué la línea de mayor recaudación y la recaudación total de la empresa.

Corte de Control por Varias Variables

En líneas generales podemos decir que un problema de corte de control por n variables se resuelve con n+1 ciclos iterativos anidados.

Modifiquemos el problema 4.1.1 para agregarle un nivel más de corte de control.


Problema 4.1.1.1
Una empresa de colectivos opera en varias zonas, en cada una de las cuales maneja varias líneas, cada una de las cuales cuenta con varios coches, cada uno de los cuales trabajó varios días del mes.

Se dispone de un conjunto de registros con la siguiente información:

• nroZona
  
• nroLinea
• nroCoche
• dia (día del mes)
  
• recDia (recaudación diaria del coche)
  

Los datos están ordenados por nroZona, nroLinea y luego por nroCoche de forma tal que todos los registros correspondientes a las líneas de una misma zona estan agrupados. Luego, los coches de una misma línea se encuentran agrupados y todas las recaudaciones diarias de un mismo coche están agrupadas también. Finaliza con un registro con nroZona = -1, nroLinea = -1, nroCoche = -1, dia = -1, recDia = -1.

Se pide:

1. Por cada coche: disponibilidad y recaudación mensual.
   
2. Por cada línea: recaudación promedio de sus coches.
   
3. Por cada zona: línea de mayor recaudación.
4. Recaudación total de la emprea y zona que tiene más líneas trabajando.

El diagrama del programa principal que resuelve este problema está a continuación. El desarrollo de los procedimientos queda a cargo del lector.

Algoritmos y Estructuras de Datos UTN - UBA.