Fundamentos de programación con Módula-2 (21)

9.6.3 Operaciones entre conjuntos
Las operaciones entre conjuntos que se pueden realizar en Modula-2 son: unión, intersección, diferencia y diferencia simétrica. Todas estas operaciones se tienen que realizar entre dos conjuntos del mismo tipo, siendo el resultado otro conjunto también del mismo tipo. Los símbolos de operación y sus significados respectivos son los siguientes:

       Operación                                                 Elementos del conjunto resultante
   X + Y Unión                                                    elementos de X, o de Y, o de ambos
   X * Y Intersección                                            elementos comunes a X e Y
   X – Y Diferencia                                               elementos de X que no están en Y
   X / Y Diferencia simétrica                                 elementos de X o de Y, pero no de ambos

Por ejemplo, dados los conjuntos:

X := Existencias{ Pera, Kiwi, Naranja };
Y := Existencias{ Limon, Pera };

los resultados de las distintas operaciones entre ellos son los siguientes:

       Operación                                                 Resultado en el conjunto Z
   Z := X + Y                                                       Existencias{ Pera, Kiwi, Naranja, Limon }
   Z := X * Y                                                        Existencias{ Pera }
   Z := X – Y                                                        Existencias{ Kiwi, Naranja }
   Z := X / Y                                                        Existencias{ Kiwi, Naranja, Limon }

Además de estos operadores, en Modula-2 existen dos procedimientos predefinidos para manejar conjuntos, que fueron ya mencionados en el Tema 7. Estos procedimientos son los siguientes:

EXCL( S, X )             Excluye el elemento X del conjunto S
INCL( S, X )              Incluye el elemento X en el conjunto S

El primer argumento S debe ser una variable de un tipo conjunto. El valor del elemento X puede darse, en general, en forma de expresión, que habrá de ser del tipo referencial. Por ejemplo:

INCL( marcadoHoy, Pera );
…..
EXCL( boleto, 4*5);
…..
INCL( listaLetras, Caracter );

El mismo resultado se puede conseguir con las operaciones de unión y diferencia, utilizando un conjunto formado por el único elemento a incluir o excluir. Esto es:

mercadoHoy := mercadoHoy + Existencias{ Pera };
…..
boleto := boleto – Tabla{ 4*5 };
…..
listaLetras := listaLetras + Letras{ Caracter };

Además de las anteriores operaciones entre conjuntos, que producen como resultado otro conjunto, también se pueden realizar entre conjuntos operaciones de realción que dan como resultado un valor BOOLEAN. Los operadores disponibles son los siguientes:

       Operación                                              Condición examinada
   X = Y   Equivalencia                                  X e Y tienen los mismo elementos
   X <> Y   Desigualdad                                X e Y tienen algún elemento distinto
   X <= Y   Inclusión                                     todos los elementos de X pertenecen a Y
   X >= Y   Inclusión                                     todos los elementos de Y pertenecen a X

Por ejemplo, a partir de los conjuntos que se indican a continuación:

X := Existencias{ Pera, Kiwi, Naranja };
Y := Existencias{ Limon, Pera };
U := Existencias{ Pera .. Limon };
V := Existencias{ Pera, Kiwi };
W := Existencias{ };

los resultados de distintas operaciones entre ellos son los siguientes:

       Operación                                   Resultado
   Y = U                                              FALSE
   V <= X                                             TRUE
   U <> V                                            TRUE
   X >= W                                            TRUE
   X = Y                                               FALSE
   U >= X                                             FALSE
   U <> Y                                            TRUE
   Y <= W                                           FALSE

Nótese que el conjunto vacío siempre está incluido en cualquier otro.

Otro operador que da lugar a un resultado de tipo BOOLEAN es el operador que permite comprobar si un elemento pertenece o no a un conjunto. Este operador necesita un operando de tipo conjunto y otro del tipo referencial de dicho conjunto, que será el elemento a comprobar. Este operador se indica con la palabra clave IN

Elemento IN Conjunto

El valor del elemento puede darse en forma de expresión. El resultado será TRUE cuando el elemento esté en el conjunto y FALSE en caso contrario. Por ejemplo, para los conjuntos anteriores se tienen los siguientes resultados:

       Operación                                   Resultado
   Pera IN X                                         TRUE
   Limon IN X                                        FALSE

9.7 Ejemplos de programas

Para finalizar este Tema se recogen en este apartado varios ejemplos que utilizan los nuevos tipos introducidos. El primer ejemplo hace especial hincapié en los tipos enumerados y los siguientes están dedicados fundamentalmente al manejo de conjuntos.

9.7.1 Ejemplo: Cálculo del día de la semana de una fecha
Con este programa se calcula qué día de la semana corresponde a una fecha cualquiera que se introduce como dato. Para el cálculo se supone conocido que el día 31 de Diciembre de 1988 fue Sábado. El programa sirve para fechas desde el año 1989 hasta el año 2088 (teniendo en cuenta el EFECTO 2000).

Las declaraciones de los días de la semana, los meses y los subrangos de días y años son las empleadas en los apartados anteriores. Asimismo, se utiliza la función SumarDias descrita en el apartado 9.2.2 para calcular el día de la semana que será dentro de N días conociendo el día de hoy.

La función DiadelaSemana realiza el cálculo del día de la semana teniendo en cuenta los siguientes aspectos:

  • El desfase en días de la semana que se introduce para cada mes, respecto al mismo día del mes de Enero. Por ejemplo, el mes de Febrero son 3, el mes de Marzo 3, .., el mes de Julio 6, etc.
  • Los años bisiestos son los múltiplos de 4.
  • Si el año es inferior a 89 se considera que es posterior al 2000
  • Cada año bisiesto pasado incrementa en 1 día el desfase.

El procedimiento EscribirDia escribe el tipo de día resultante. El listado del programa completo es el siguiente:

(****************************************************************************************
*
*   Programa: Calendario
*
*   Descripción: Programa para el cálculo del día de la semana que
*                      es cualquier fecha desde el 1/I/1989 hasta 31/XII/2088
*
****************************************************************************************)
MODULE Calendario;
   FROM InOut IMPORT
      WriteString, WriteLn, ReadInt, Read, Write;
   CONST
      DiasSemana = 7;
   TYPE
      TipoDia = (Lunes, Martes, Miercoles, Jueves, Viernes, Sabado, Domingo);
      TipoMes = (Enero, Febrero, Marzo, Abril, Mayo, Junio, Julio, Agosto, Septiembre, Octubre, Noviembre, Diciembre);
      RangoDias = [0..31];
      RangoAnnos = [0..99];
   VAR
      dia, mes, anno : INTEGER;
      tecla : CHAR;

PROCEDURE DiadelaSemana(D: RangoDias; M: TipoMes; A: RangoAnnos) : TipoDia;
(*==================================================================
Función para calcular el dia de la semana que corresponde a una fecha (D/M/A) cualquiera
===================================================================*)
   CONST
      OrigenA = 89;
      TreintaUnoDiciembre88 = Sabado;
   VAR
      bisiesto : BOOLEAN;
      sumaBisis, sumaAnnos, sumaDias : RangoDias;
   PROCEDURE SumarDias(Hoy : TipoDia; N: RangoDias) : TipoDia;
   (*================================================
   Función para sumar dias de la semana ciclicamente
   =================================================*)
      VAR
         aux : INTEGER;
   BEGIN
      aux := (ORD(Hoy) + N) MOD DiasSemana;
      RETURN VAL(TipoDia, aux);
   END SumarDias;

BEGIN
   IF M = Enero                 THEN sumaDias := 0
   ELSIF M = Febrero        THEN sumaDias := 3
   ELSIF M = Marzo          THEN sumaDias := 3
   ELSIF M = Abril             THEN sumaDias := 6
   ELSIF M = Mayo           THEN sumaDias := 1
   ELSIF M = Junio            THEN sumaDias := 4
   ELSIF M = Julio             THEN sumaDias := 6
   ELSIF M = Agosto         THEN sumaDias := 2
   ELSIF M = Septiembre   THEN sumaDias := 5
   ELSIF M = Octubre        THEN sumaDias := 0
   ELSIF M = Noviembre     THEN sumaDias := 3
   ELSE sumaDias := 5
   END;
   bisiesto := (A MOD 4) = 0;
   IF A < OrigenA THEN
      A := A + 100      (* Año posterior al 2000 *)
   END;
   sumaAnnos := A – OrigenA;  (* Años pasados desde el 89 *)
   sumaBisis := sumaAnnos DIV 4;  (* Bisiestos pasados *)
   sumaDias := sumaDias + D + sumaAnnos + sumaBisis;
   IF bisiesto AND (M > Febrero) THEN
      sumaDias := sumaDias + 1
   END;
   RETURN SumarDias(TreintaUnoDiciembre88, sumaDias)
END DiadelaSemana;

PROCEDURE EscribirDia(S : TipoDia);
(*==================================
Procedimiento para escribir el día de la semana
===================================*)
BEGIN
   IF S = Lunes                 THEN WriteString("Lunes")
   ELSIF S = Martes          THEN WriteString("Martes")
   ELSIF S = Miercoles      THEN WriteString("Miercoles")
   ELSIF S = Jueves           THEN WriteString("Jueves")
   ELSIF S = Viernes         THEN WriteString("Viernes")
   ELSIF S = Sabado          THEN WriteString("Sabado")
   ELSE WriteString("Domingo")
   END;
   WriteLn;
END EscribirDia;

BEGIN
   tecla := "S";
   WHILE tecla <> "N" DO
      WriteString("¿Dia Mes Año?");
      ReadInt(dia); Write(" ");
      ReadInt(mes); Write(" ");
      ReadInt(anno); WriteLn;
      EscribirDia(DiadelaSemana(dia, VAL(TipoMes,mes-1), anno));
      WriteString("¿Otra Fecha (S/N)?");
      Read(tecla); Write(tecla); WriteLn
   END
END Calendario.

Un resultado de la ejecución del programa es el siguiente:

¿Día Mes Año?1 4 93
Jueves
¿Otra Fecha (S/N)?S
¿Día Mes Año?1 10 94
Sabado
¿Otra Fecha (S/N)?N

9.7.2 Ejemplo: Criba de Eratóstenes
En el tema anterior se realizó un programa para imprimir de manera sucesiva los números primos según se calculaban dado que no se podian almacenar en ninguna variable estructurada. Ahora ya disponemos del tipo conjunto y en este ejemplo se trata de obtener la tabla completa de los números primos entre 1 y 500, mediante el método de criba de Eratóstenes, antes de imprimirlos por pantalla. Para ello se parte de un tipo de conjunto Lista definido sobre un referencial subrango de 1 a 500. El procedimiento Eratostenes inicializa el conjunto que se le pasa como argumento con todos los elementos. A continuación se realiza la criba excluyendo aquellos números que son múltiplos de un número primo. La elección del siguiente número primo se efectúa comprobando que no ha sido excluído todavía de la tabla.

El procedimiento EscribirLista escribe los elementos que pertenecen al conjunto de 10 en 10. El listado completo del programa es el siguiente:

(**************************************************************************************************
*
*   Programa: Criba
*
*   Descripción:
*                    Programa para obtener la criba de Eratostenes
*
**************************************************************************************************)
MODULE Criba;
   FROM InOut IMPORT
      WriteString, WriteLn, WriteInt;
   CONST
      Mayor = 500;        (* Valor mayor de la criba *)
   TYPE
      Margen = [1..Mayor];
      Lista = SET OF Margen;
   VAR
      numerosPrimos : Lista;

PROCEDURE Eratostenes(VAR Numeros : Lista);
(*=========================================
Procedimiento para realizar la criba
==========================================*)
   VAR primo, multiplo : CARDINAL;
BEGIN
   Numeros := Lista{1..Mayor};     (* Todos inicialmente *)
   FOR primo := 2 TO Mayor DIV 2 DO
      IF primo IN Numeros THEN
         multiplo := primo + primo;
         WHILE multiplo <= Mayor DO
            EXCL(Numeros,multiplo);
            multiplo := multiplo + primo
         END
      END
   END
END Eratostenes;

PROCEDURE EscribirLista(T : Lista);
(*==========================================
Procedimiento para escribir la lista de 10 en 10 elementos
===========================================*)
   VAR i, j: CARDINAL;
BEGIN
   WriteLn; WriteLn; j := 0;
   FOR i := 1 TO Mayor DO
      IF i IN T THEN
         WriteInt(i,4); j := j + 1;
         IF (j MOD 10) = 0 THEN
            WriteLn    (* Cambiar de línea con 10 elementos *)
         END
      END
   END; WriteLn
END EscribirLista;

BEGIN
   Eratostenes(numerosPrimos);
   WriteString("                 Tabla de Números Primos:");
   EscribirLista(numerosPrimos);
END Criba.

y el resultado de la ejecución es el siguiente:

                Tabla de N·meros Primos:

    1   2     3     5     7  11  13   17   19   23
  29  31   37   41   43  47  53   59   61   67
  71  73   79   83   89  97 101 103 107 109
113 127 131 137 139 149 151 157 163 167
173 179 181 191 193 197 199 211 223 227
229 233 239 241 251 257 263 269 271 277
281 283 293 307 311 313 317 331 337 347
349 353 359 367 373 379 383 389 397 401
409 419 421 431 433 439 443 449 457 461
463 467 479 487 491 499

9.7.3 Ejemplo: Contar letras y dígitos
En este ejemplo se trata de analizar un texto y contar el número de letras, dígitos y espacios en blanco de los que consta. Asimismo, se toma nota de cuáles son las letras y dígitos utilizados. Como resultado se escriben las letras no utilizadas y los dígitos utilizados.

Para almacenar las letras y dígitos utilizados se emplean conjuntos sobre los referenciales desde la A a la Z y desde el 0 al 9. Hay que tener en cuenta que la letra ñ no está incluida en dicho conjunto y por tanto se considera un signo de puntuación. El procedimiento Analizar va incluyendo en cada conjunto los elementos según se encuentran en el texto. El procedimiento DarResultados escribe los resultados obtenidos. El listado completo del programa es el siguiente:

(**************************************************************************************************
*
*   Programa: Contar
*
*   Descripción:
*      Programa para contar las letras y dígitos de un texto
*
**************************************************************************************************)
MODULE Contar;
   FROM InOut IMPORT
      WriteString, WriteLn, WriteInt, Write, Read;
   TYPE
      Caracteres = SET OF CHAR;
      Letras = SET OF ["A".."Z"];
      Digitos = SET OF ["0".."9"];
   VAR
      listaLetras : Letras;
      listaDigitos : Digitos;
      total, totalLetras, totalDigitos, totalBlancos : INTEGER;

PROCEDURE Analizar;
(*===============================
Procedimiento para analizar el texto y contar las letras, dígitos,
blancos y el total de caracteres de un texto
================================*)
   VAR c : CHAR;
BEGIN
   (*– Inicializar –*)
      total := 0; totalLetras := 0; c := " ";
      totalDigitos := 0; totalBlancos := 0;
      listaLetras := Letras{}; listaDigitos := Digitos{};
   (*– Bucle hasta localizar el punto final –*)
      WHILE c <> "." DO
         Read(c); Write(c); INC(total);
         IF c IN Caracteres{"a".."z", "A".."Z"} THEN
         (*– Contar y anotar la letra analizada –*)
            INC(totalLetras); c := CAP(c);
            INCL(listaLetras, c)
         ELSIF c IN Digitos{"0".."9"} THEN
         (*– Contar y anotar el dígito analizado –*)
            INC(totalDigitos); INCL(listaDigitos, c)
         ELSIF c = " " THEN
         (*– Contar el blanco analizado –*)
            INC(totalBlancos)
         ELSE
         END
      END
END Analizar;

PROCEDURE DarResultados;
(*=============================
Procedimiento para escribir los resultados
==============================*)
   VAR c : CHAR;
BEGIN
   WriteLn; WriteLn;
   WriteString("               RESULTADOS"); WriteLn;
   WriteString("               ==========="); WriteLn; WriteLn;
   WriteString("Caracteres Totales:"); WriteInt(total, 4); WriteLn;
   WriteString("Letras Totales:       "); WriteInt(totalLetras, 4); WriteLn;
   WriteString("Dígitos Totales:      "); WriteInt(totalDigitos, 4); WriteLn;
   WriteString("Blancos Totales:    "); WriteInt(totalBlancos, 4); WriteLn; WriteLn;
   WriteString("LISTA DE LETRAS NO UTILIZADAS"); WriteLn;
   FOR c := "A" TO "Z" DO
      IF NOT (c IN listaLetras) THEN Write(c); Write(" ") END
   END;
   WriteLn; WriteLn;
   WriteString("LISTA DE DIGITOS UTILIZADOS"); WriteLn;
   FOR c := "0" TO "9" DO
      IF c IN listaDigitos THEN Write(c); Write(" "); END
   END;
END DarResultados;

BEGIN
   Analizar;
   DarResultados
END Contar.

y el resultado de la ejecución es el siguiente:

En un lugar de la Mancha
a 123 kilometros de Madrid.

               RESULTADOS
               ===========

Caracteres Totales:  52
Letras Totales:         38
DÝgitos Totales:         3
Blancos Totales:       9

LISTA DE LETRAS NO UTILIZADAS
B F J P Q V W X Y Z

LISTA DE DIGITOS UTILIZADOS
1 2 3

9.7.4 Ejemplo: Juego de lotería primitiva
En este último ejemplo se simula el juego de la Lotería Primitiva. El boleto con los números elegidos y la tabla de los números premiados se guardan en un conjunto sobre el referencial de rango 1 a 49. El número complementario se guarda aparta utilizando un tipo subrango.

El procedimiento Sortear genera aleatoriamente los 6 números premiados y el complementario. En todos los lenguajes existe algún sistema para generar números aleatorios. Para generar dichos valores se utiliza el módulo Lib, que contiene un procedimiento RANDOMIZE encargado de iniciar el proceso de generación de números aleatorios y una función RANDOM que devuelve cada vez que se la invoca un nuevo número aleatorio comprendido entre 0 y el valor máximo que se le pasa como argumento (la mayoría de los compiladores de lenguajes de alto nivel incluyen funciones auxiliares o de utilidad, entre las que se encuentra la generación de valores seudoaleatorios). "aquí para descargar el módulo anterior"

En este caso el máximo valor aleatorio es 49. Se generan los 6 números premiados y el complementario por este procedimiento. Con cada nuevo número se comprueba que no figura ya en la Tabla de premiados y que es distinto de 0. En caso afirmativo se incluye en la Tabla.

El procedimiento LeerBoleto funciona de forma parecida al anterior. En este caso se comprueba que los números elegidos están dentro de los posibles (entre 1 y 49). Se permite realizar apuestas múltiples con hasta el doble de números, y se calcula el número de apuestas realizadas con los números elegidos.

El procedimiento EscribirTabla, escribe los números que pertenecen al conjunto que se le pasa como argumento.

Los números acertados se obtienen como el conjunto intersección entre los premiados y el boleto elegido. El complementario se comprueba aparte. El listado completo del programa es el siguiente:

(**************************************************************************************************
*
*   Programa: Primitiva
*
*   Descripción:
*      Programa para jugar a la lotería primitiva con el computador
*
**************************************************************************************************)
MODULE Primitiva;
   FROM InOut IMPORT
      WriteString, WriteLn, WriteInt, ReadInt, Read, Write;
   FROM Lib IMPORT
      RANDOMIZE, RANDOM;
   CONST
      Maximo = 49;        (* Número mayor que se puede elegir *)
      Numeros = 6;        (* Números que forman una apuesta *)
   TYPE
      Rango = [1..Maximo];
      Tabla = SET OF Rango;
   VAR
      boleto, premiados, acertados : Tabla;
      complementario : Rango;

PROCEDURE Sortear(VAR SeisN : Tabla; VAR C : Rango);
(*=============================================
Procedimiento que realiza el sorteo aleatoriamente. Lo devuelve
en una tabla y el número complementario
==============================================*)
   VAR
      i, n : CARDINAL;
BEGIN
   RANDOMIZE;
   SeisN := Tabla{};
   i := 0;
   WHILE i <= Numeros DO
      n := RANDOM(Maximo);     (* Número aleatorio *)
      IF NOT (n IN SeisN) AND (n <> 0) THEN
         IF i < Numeros THEN
            INCL(SeisN,n)
         ELSE
            C := n
         END;
         INC(i)
      END
   END
END Sortear;

PROCEDURE LeerBoleto(VAR B : Tabla);
(*====================================
Procedimiento para leer el boleto en una tabla.
El máximo de números que se pueden seleccionar son 6*2=12
=====================================*)
   VAR
      apuestas, i, aux : INTEGER;
      n : Rango;
      tecla : CHAR;
BEGIN
   B := Tabla{};
   WriteString("Introduzca los números del boleto");
   WriteLn; i := 0; tecla := "S";
   WHILE (i < 2*Numeros) AND (tecla <> "N") DO
      WriteInt(i+1,3); WriteString("º número ?");
      ReadInt(aux); WriteLn; n := VAL(Rango, aux);
      IF NOT (n IN B) AND (n > 0) AND (n <= Maximo) THEN
         B := B + Tabla{n};
         i := i + 1
      END;
      IF ( i >= Numeros) AND (i < 2*Numeros) THEN
         WriteString("¿Más números (S/N)?");
         Read(tecla); Write(tecla); WriteLn
      END
   END;
   IF i = 12 THEN apuestas := 924
   ELSIF i = 11 THEN apuestas := 462
   ELSIF i = 10 THEN apuestas := 210
   ELSIF i = 9 THEN apuestas := 84
   ELSIF i = 8 THEN apuestas := 28
   ELSIF i = 7 THEN apuestas := 7
   ELSE apuestas := 1
   END;
   WriteLn; WriteString("Total apuestas =");
   WriteInt(apuestas, 6); WriteLn; WriteLn
END LeerBoleto;

PROCEDURE EscribirTabla(T : Tabla);
(*=====================================
Procedimiento para escribir los números de una tabla
======================================*)
   VAR
      i : CARDINAL;
BEGIN
   FOR i := 1 TO Maximo DO
      IF i IN T THEN
         WriteInt(i,3)
      END;
   END;
   WriteLn
END EscribirTabla;

BEGIN
   (*– Sortear –*)
      Sortear(premiados, complementario);
   (*– Leer numeros elegidos –*)
      LeerBoleto(boleto);
   (*– Escribir números premiados –*)
      WriteString("Números premiados:");
      EscribirTabla(premiados);
      WriteString("Complementario =");
      WriteInt(complementario, 3); WriteLn; WriteLn;
   (*– Acertados = Coinciden entre boleto y premiados –*)
      acertados := premiados * boleto;
   (*– Escribir aciertos –*)
      WriteString("Números acertados:");
      EscribirTabla(acertados);
      IF complementario IN boleto THEN
         WriteString("y el complementario");
      END
END Primitiva.

Un ejemplo del resultado de la ejecución es el siguiente:

Introduzca los números del boleto
  1º número ?23
  2º número ?12
  3º número ?5
  4º número ?8
  5º número ?37
  6º número ?21
¿Más números (S/N)?S
  7º número ?44
¿Más números (S/N)?N

Total apuestas =     7

Números premiados: 11 21 27 35 37 39
Complementario =  3

Números acertados: 21 37

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s