VECINOS INTERNACIONALES

Condiciones iniciales:

  • Tenemos cinco casas, cada una de un color.
  • Cada casa tiene un dueño de nacionalidad diferente.
  • Los 5 dueños toman una bebida diferente, fuman marca diferente y tienen mascota diferente.
  • Ningún dueño tiene la misma mascota, fuma la misma marca o bebe el mismo tipo de bebida que otro.

Datos:

  • El noruego vive en la primera casa, junto a la casa azul.
  • El que vive en la casa del centro toma leche.
  • El inglés vive en la casa roja.
  • La mascota del Sueco es un perro.
  • El danés bebe té.
  • La casa verde es la inmediata de la izquierda de la casa blanca.
  • El de la casa verde toma café.
  • El que fuma Pall Mall cría pájaros.
  • El de la casa amarilla fuma Dunhill.
  • El que fuma Blend vive junto al que tiene gatos.
  • El que tiene caballos vive junto al que fuma Dunhill.
  • El que fuma Blue Master bebe cerveza.
  • El alemán fuma Prince.
  • El que fuma Blend tiene un vecino que bebe agua.

¿Quién tiene peces por mascota?

problema7

::SOLUCIÓN::
aquí

Anuncios

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

11.7 Ejemplos de programas

A continuación se muestran varios programas completos con ejemplos de sus respectivas ejecuciones.

11.7.1 Sopa de letras
Con este programa se trata de realizar la búsqueda de una palabra dentro de una matriz de caracteres. La búsqueda debe realizarse en horizontal, vertical y diagonal en ambos sentidos. Por tanto, se pueden establecer 8 direcciones de búsqueda: norte, sur, este, oeste, noroeste, suroeste, noreste y sureste. En la búsqueda se deben tener en cuenta los límites de la matriz. La función Buscar comprueba si la palabra P de longitud L coincide con los caracteres de la matriz desde la posición: fila F y columna C, siguiendo la dirección R. Esta función tienen en cuenta los límites de la matriz y devuelve un resultado cierto o falso según se encuentre o no la palabra buscada.

Los demás procedimientos son auxiliares. El procedimiento IniciarSopa inicializa de forma aleatoria la matriz, mediante un recorrido de la misma. Cada carácter se obtiene a partir de un número aleatorio entre 0 y 26, al que se suma la posición del carácter "a" dentro de la tabla ASCII.

El procedimiento Cambiar, es el encargado de pasar de minúsculas a mayúsculas la palabra encontrada. Este cambio se realiza mediante un recorrido parcial de Lg caracteres de la matriz desde la posición: fila Fil y columna Col, siguiendo la dirección Ru.

El procedimiento EscribirSopa es un recorrido total de la matriz en el que se escriben por filas todos los caracteres de la matriz separados por un blanco.

En el programa se lee la palabra a buscar, acabada en punto, e inmediatamente se realiza su búsqueda exhaustiva desde todas las posiciones de la matriz y con todas las direcciones posibles. Si se encuentra, se cambia a mayúsculas. El listado del programa es el siguiente:

(**************************************************************************************************
*
*   Programa: SopaLetras
*
*   Descripción:
*      Este programa busca una palabra en una matriz de caracteres, en cualquier
*      dirección de forma semejante a como se hace en una sopa de letras
*
**************************************************************************************************)
MODULE SopaLetras;
   FROM InOut IMPORT
      WriteString, Write, WriteLn, Read;
   FROM Lib IMPORT RANDOMIZE, RANDOM;
   CONST
      Filas = 10;               (* Filas de la sopa de letras *)
      Columnas = 20;    (* Columnas de la sopa de letras *)
      TotalLetras = 26;    (* Total letras abecedario inglés *)
   TYPE
      Largo = [1..Filas];
      Ancho = [1..Columnas];
      TipoSopa = ARRAY Largo, Ancho OF CHAR;
      Ristra = ARRAY Ancho OF CHAR;
      TipoRumbo = ( Norte, Sur, Este, Oeste, Noroeste, Suroeste, Noreste, Sureste );
      Caracteres = SET OF CHAR;
   VAR
      sopa: TipoSopa;   palabra: Ristra;   long: Ancho;
      indFila: Largo;   indColu: Ancho;   rumbo: TipoRumbo;
      tecla: CHAR;

PROCEDURE IniciarSopa;
(*=====================================
Procedimiento para iniciar aleatoriamente una sopa de letras
=====================================*)
   VAR i : Largo; j : Ancho;
BEGIN
   RANDOMIZE;
   FOR i := 1 TO Filas DO
      FOR j := 1 TO Columnas DO
         sopa[i,j] := CHR(RANDOM(TotalLetras) + ORD("a"))
      END
   END
END IniciarSopa;

PROCEDURE Cambiar( Lg, Col: Ancho; Fil: Largo; Ru : TipoRumbo);
(*=====================================
Procedimiento para cambiar Lg letras a mayusculas desde
la posición Col, Fil con el rumbo RU
=====================================*)
   VAR i : Ancho;
BEGIN
   FOR i := 1 TO Lg DO
      sopa[Fil,Col] := CAP(sopa[Fil,Col]);
      (*– Nueva fila según el rumbo –*)
      CASE Ru OF
         Norte, Noreste, Noroeste : Fil := Fil-1 |
         Sur, Sureste, Suroeste : Fil := Fil+1 |
         Este, Oeste :
      END;
      (*– Nueva columna según el rumbo –*)
      CASE Ru OF
         Este, Noroeste, Sureste : Col := Col+1 |
         Oeste, Suroeste : Col := Col-1 |
         Norte, Sur :
      END
   END
END Cambiar;

PROCEDURE  Buscar( P: Ristra; L,C: Ancho; F: Largo; R: TipoRumbo): BOOLEAN;
(*============================================================
Procedimiento para buscar las L letras de la ristra P, desde la posición C, F con el
rumbo R en la sopa de letras
============================================================*)
   VAR i : Ancho; sigue : BOOLEAN;
BEGIN
   i := 1; sigue := TRUE;
   WHILE (i <= L) AND sigue DO
      (*– Se sigue buscando si está la letra buscada en mayúscula o minúscula –*)
      (*sigue := ( CAP( P[i] ) = CAP( sopa[F,C] ) );*)
      CASE R OF
         Norte, Noreste, Noroeste : F := F – 1 |
         Sur, Sureste, Suroeste : F := F + 1 |
         Este, Oeste:
      END;
      (*– Seguir si la nueva fila está dentro de la sopa –*)
      sigue := sigue AND (F > 0) AND (F <= Filas);
      CASE R OF
         Este, Noreste, Sureste : C := C+1 |
         Oeste, Suroeste : C := C-1 |
         Norte, Sur :
      END;
      (*– Seguir si la nueva columna está en la sopa –*)
      sigue := sigue AND (C > 0) AND (C <= Columnas);
      i := i+1
   END;
   RETURN sigue
END Buscar;

PROCEDURE EscribirSopa;
(*=====================================
Procedimiento para escribir la sopa de letras
=====================================*)
   VAR i : Largo; j : Ancho;
BEGIN
   WriteLn;
   FOR i := 1 TO Filas DO
      FOR j := 1 TO Columnas DO
         Write(sopa[i,j]); Write(" ")
      END;
      WriteLn
   END
END EscribirSopa;

BEGIN
   IniciarSopa;
   EscribirSopa;
   REPEAT
      long := 1;
      WriteString("¿Palabra a buscar.?");
      (*– Leer palabra a buscar –*)
      REPEAT
         Read(tecla); Write(tecla);
         IF tecla IN Caracteres{"a".."z"} THEN
            long := long + 1; palabra[long] := tecla
         END
      UNTIL tecla = ".";
   (*– Buscar desde todos los puntos posibles y en todas las direcciones  posibles –*)
   FOR indFila := 1 TO Filas DO
      FOR indColu := 1 TO Columnas DO
         FOR rumbo := Norte TO Sureste DO
            IF Buscar( palabra, long, indColu, indFila, rumbo)
            THEN
               (*– Cuando se encuentra se camba a mayusculas –*)
               Cambiar( long, indColu, indFila, rumbo )
             END
         END
      END
   END;
   (*– Escribir cómo queda la sopa –*)
   EscribirSopa;
   WriteString( "¿Otra Palabra (s/n)?");
   Read( tecla ); Write( tecla ); WriteLn
   UNTIL tecla = "n"
END SopaLetras.

La ejecución del programa produce el siguiente resultado:

w a u l k v j x j c q d x w g l u v u w
t y j k j d a l d p a i t j k d t n m e
w n r u x v o h c f o f r q y j n g o d
d n e v y w r b q q f r t k d p s z i i
e w k i d c i w d y j o e n p v a p q j
d q k w r p o n s n k v k e d z t v y o
g t h x w d c h g e u j l z e s z i b w
q k q o a u c a l f j v q r p k a w q y
u m i o c b l z x i g z k q y a z y e n
j o c t w b g n v d b c m x w m z b h a
¿Palabra a buscar.?re.
w a u l k v j x j c q d x w g l u v u w
t y j k j d a l d p a i t j k d t n m e
w n R u x v o h c f o f r q y j n g o d
d n E v y w r b q q f R t k d p s z i i
e w k i d c i w d y j o E n p v a p q j
d q k w r p o n s n k v k e d z t v y o
g t h x w d c h g e u j l z E s z i b w
q k q o a u c a l f j v q R p k a w q y
u m i o c b l z x i g z k q y a z y e n
j o c t w b g n v d b c m x w m z b h a
¿Otra Palabra (s/n) ?n

11.7.2 Recortar una imagen
Este programa es un ejemplo de utilización de una matriz orlada. El procedimiento Recortar ya fue explicado en el apartado dedicado a las matrices orladas. El procedimiento Imprimir es simplemente un recorrido de la matriz para imprimir la imagen contenida. El procedimiento LeerFoto lee una imagen de los datos de entrada, leyendo un carácter por cada punto.

El listado completo del programa es el siguiente:

(*****************************************************************************
*     Programa: RECORTE
*    
*     Descripción:
*        Este programa recorta una imagen digitalizada
*
****************************************************************************)
MODULE Recorte;

FROM InOut IMPORT WriteString, WriteLn, Read, Write;

CONST
   Ancho = 40;                      (* Anchura de la imagen *)
   Alto = 20;                          (* Altura de la imagen *)
   Borde = -1;                         (* Indicador de borde de la imagen *)
   Blanco = 0;                        (* Nivel bajo de grises = blanco *)
   Negro = 5;                         (* Nivel alto de grises = negro *)

TYPE
   Grises = [Borde..Negro];
   TipoImagen = ARRAY [0..Alto+1], [0..Ancho+1] OF Grises;

VAR
   imagen: TipoImagen;

PROCEDURE LeerImagen;
(*===============================================
   Lee la imagen como dato de entrada.
================================================*)
   VAR i, j: INTEGER; c: CHAR;
BEGIN
   (*– 1º Paso: Inicializar toda la imagen a ‘Borde’ –*)
      FOR i := 0 TO Alto+1 DO
         FOR j := 0 TO Ancho+1 DO
            imagen[i,j] := Borde
         END
      END;
   (*– 2º Paso: Leer los datos, punto a puto –*)
      FOR   i := 1 TO Alto DO
         FOR j := 1 TO Ancho DO
            Read( c );
            imagen[i,j] := ORD( c ) – ORD( ‘0’ )
         END;
         Read( c )                     (* salto de línea *)
      END;
   END LeerImagen;

PROCEDURE Constrastar( nivel: Grises );
(*===============================================
    Procedimiento para constrastar la imagen
================================================*)
   VAR i,j: INTEGER;
BEGIN
   FOR i := 1 TO Alto DO
      FOR j := 1 TO Ancho DO
         IF imagen[i,j] <= nivel THEN
            imagen[i,j] := Blanco
         ELSE
            imagen[i,j] := Negro
         END
      END
   END;
END Constrastar;

PROCEDURE Recortar;
(*===============================================
   Procedimiento para recortar la imagen
================================================*)
   VAR i, j: INTEGER; fin : BOOLEAN;
BEGIN
   REPEAT
      fin := TRUE;
      FOR i := 1 TO Alto DO
         FOR j := 1 TO Ancho DO
            IF (imagen[i,j] = Blanco) AND ( (imagen[i-1, j] = Borde)
                                                          OR (imagen[i, j-1] = Borde)
                                                          OR (imagen[i, j+1] = Borde)
                                                          OR (imagen[i+1,j] = Borde) ) THEN
                 imagen[i,j] := Borde;
                 fin := FALSE
            END
         END
      END
   UNTIL fin
END Recortar;

PROCEDURE Imprimir;
(*================================================
   Procedimiento para imprimir la imagen
=================================================*)
   VAR i, j: INTEGER;
BEGIN
   FOR i := 1 TO Alto DO
      FOR j := 1 TO Ancho DO
         CASE imagen[i,j] OF
            Borde: Write( " " ) |
            Blanco: Write( "." ) |
            1:       Write( ".") |
            2:       Write( "+") |
            3:       Write( "x") |
            4:       Write( "*") |
            Negro: Write( "#" )
         END
       END;
       WriteLn
   END
END Imprimir;
BEGIN
(*– Leer la imagen inicial –*)
   LeerImagen;
   WriteString( "Imagen inicial:"  ); WriteLn;
   Imprimir;
(*– Reducir la imagen a blanco y negro –*)
   Constrastar( 3 );
   WriteLn;
   WriteString( "Imagen constratada:" ); WriteLn;
   Imprimir;
(*– Recortar la imagen, marcando el borde externo –*)
   Recortar;
   WriteLn;
   WriteString( "Imagen recortada:xXx" ); WriteLn;
   Imprimir;
END Recorte.

A continuación se presenta un ejemplo de la ejecución de este programa. Los datos de entrada contienen un carácter por cada punto de la imagen, y simulan una rejilla. Una de las esquinas del borde derecho está rota. Los datos son:

0123454321012345432101234543210123454321
1234545432123454543212345454321234545432
2345434543234543454323454345432345434543
3454323454345432345434543234543454323454
4543212345454321234545432123454543212344
5432101234543210123454321012345432101233
4543212345454321234545432123454543212344
3454323454345432345434543234543454323454
2345434543234543454323454345432345434543
1234545432123454543212345454321234545432
0123454321012345432101234543210123454321
1234545432123454543212345454321234545432
2345434543234543454323454345432345434543
3454323454345432345434543234543454323454
4543212345454321234545432123454543212345
5432101234543210123454321012345432101234
4543212345454321234545432123454543212345
3454323454345432345434543234543454323454
2345434543234543454323454345432345434543
1234545432123454543212345454321234545432

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

Imagen inicial:
..+x*#*x+…+x*#*x+…+x*#*x+…+x*#*x+.
.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+
+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x
x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*
*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+.+x**
#*x+…+x*#*x+…+x*#*x+…+x*#*x+…+xx
*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+.+x**
x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*
+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x
.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+
..+x*#*x+…+x*#*x+…+x*#*x+…+x*#*x+.
.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+
+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x
x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*
*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#
#*x+…+x*#*x+…+x*#*x+…+x*#*x+…+x*
*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#
x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*
+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x+x*#*x*#*x
.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+.+x*#*#*x+

Imagen constratada:
….###…….###…….###…….###…
…#####…..#####…..#####…..#####..
..###.###…###.###…###.###…###.###.
.###…###.###…###.###…###.###…###
###…..#####…..#####…..#####…..##
##…….###…….###…….###……..
###…..#####…..#####…..#####…..##
.###…###.###…###.###…###.###…###
..###.###…###.###…###.###…###.###.
…#####…..#####…..#####…..#####..
….###…….###…….###…….###…
…#####…..#####…..#####…..#####..
..###.###…###.###…###.###…###.###.
.###…###.###…###.###…###.###…###
###…..#####…..#####…..#####…..##
##…….###…….###…….###…….#
###…..#####…..#####…..#####…..##
.###…###.###…###.###…###.###…###
..###.###…###.###…###.###…###.###.
…#####…..#####…..#####…..#####..

Imagen recortada:
    ###       ###       ###       ###
   #####     #####     #####     #####
  ###.###   ###.###   ###.###   ### ###
###…### ###…### ###…### ###   ###
###…..#####…..#####…..#####     ##
##…….###…….###…….###
###…..#####…..#####…..#####     ##
###…###.###…###.###…###.###   ###
  ###.###…###.###…###.###…### ###
   #####…..#####…..#####…..#####
    ###…….###…….###…….###
   #####…..#####…..#####…..#####
  ###.###…###.###…###.###…###.###
###…###.###…###.###…###.###…###
###…..#####…..#####…..#####…..##
##…….###…….###…….###…….#
###…..#####…..#####…..#####…..##
###…### ###…### ###…### ###…###
  ###.###   ###.###   ###.###   ###.###
   #####     #####     #####     #####

11.7.3 Frases políndromas
Este programa ilustra el uso de vectores abiertos. Se trata de comprobar si una frase es un políndromo, esto es, si las letras de las que consta se leen igual hacia adelante que hacia atrás. Para ello se define un procedimiento LeerTexto, capaz de leer un vector de caracteres de cualquier longitud. Este procedimiento sólo guarda las letras válidas de la "a" a la "z" y finaliza cuando se introduce un punto "." o se llena el vector pasado como argumento.

La función Simetrico es la encargada de comprobar que el contenido del vector abierto, pasado como argumento por valor, es simétrico. Primeramente, se busca el punto de final del texto a analizar o el final del vector. Esto se hace mediante el esquema típico de búsqueda. La posición final se decrementa en uno después de la búsqueda para apuntar al primer carácter válido Después, se comprueba si coinciden los caracteres de un extremo con los del otro. Esta comprobación acaba o bien cuando se cruzan los índices y todos los caracteres han sido iguales o bien cuando no coinciden algunos de ellos.

El listado completo del programa es el siguiente:

(**************************************************************************************************
*
*   Programa: Palindromo
*
*   Descripción:
*      Este programa comprueba si una frase es un palindromo.
*
**************************************************************************************************)
MODULE Palindromo;
   FROM InOut IMPORT
      WriteString, WriteLn, Write, Read;

   CONST
      Fin = ".";
      Maximo = 100;            (* Máxima longitud de la frase *)

   TYPE
      TipoLong = [0..Maximo];
      TipoRistra = ARRAY TipoLong OF CHAR;
      Caracteres = SET OF CHAR;

   VAR
      frase : TipoRistra;

PROCEDURE LeerTexto( VAR Tex: ARRAY OF CHAR );
(*===============================================
Procedimiento para leer una frase acabada en un punto (.) y dejarla
en el argumento vector abierto. Solo se guardan en el vector las letras
de a..z mayúsculas o minúsculas y el punto final.
===============================================*)
   VAR   car: CHAR;   long: TipoLong;
BEGIN
   WriteString( "¿Frase acabada en punto(.)?"); WriteLn;
   long := 0;
   REPEAT
      Read(car);   Write(car);
      (*– Se comprueba si es un caracter correcto –*)
      IF car IN Caracteres{"A".."Z", "a".."z", Fin} THEN
         long := long + 1;   Tex[long] := CAP(car)
      END;
      (*– Se acaba al encontrar el punto o si se acaba el vector  –*)
   UNTIL (car = Fin) OR (long = HIGH(Tex));
END LeerTexto;

PROCEDURE Simetrico( Texto: ARRAY OF CHAR ): BOOLEAN;
(*===============================================
Función que comprueba si hay simetría entre las letras del
comienzo y las del final de una frase: es un palindromo. El
argumento pasado es de tipo vector abierto
===============================================*)
   VAR i, j: TipoLong;
BEGIN
(*– 1º Paso: Buscar el punto final (.) o final del vector –*)
   j := 0;
   WHILE (Texto[j] <> Fin) AND (j <= HIGH(Texto)) DO
      j := j + 1
   END;
   j := j – 1; i := 1;
(*– 2º Paso: Comprobar igualdad entre caracteres simetricos –*)
   WHILE (i < j) AND (Texto[i] = Texto[j]) DO
      i := i+1; j := j-1
   END;
   RETURN i >= j
END Simetrico;

BEGIN
   LeerTexto( frase );
   IF Simetrico( frase ) THEN
      WriteString( " Es Palindromo")
   ELSE
      WriteString( " No es Palindromo")
   END
END Palindromo.

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

¿Frase acabada en punto(.)?
Dabale arroz a la zorra el abad. Es Palindromo

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

11.4.2 Búsqueda secuencial
Para buscar un elemento dentro de una formación es necesario recorrerla, pero no siempre en su totalidad. El recorrido se debe detener en cuanto se encuentre el elemento buscado, y por tanto sólo será completo cuando no se encuentre el elemento buscado dentro de la formación. Este planteamiento del problema indica que no se puede utilizar una sentencia FOR para la operación de búsqueda.

Para establecer un esquema general de búsqueda es necesario fijar la condición o condiciones que determinan las características del elemento buscado. Además se debe tener en cuenta el tamaño y estructura de la formación para controlar cuándo se da por finalizada una búsqueda infructuosa. En algunos casos es posible incluso que el tamaño de la formación sea nulo y no contenga ningún elemento. Todos estos condicionantes apuntan en el sentido de emplear una sentencia WHILE para realizar la búsqueda. Como esquema general se puede plantear el siguiente:

Iniciar búsqueda
WHILE ( NOT Encontrado ) AND ( NOT Final ) DO
   Pasar al siguiente elemento;
   Verificar encuentro
END

Este esquema se puede emplear, por ejemplo, para la búsqueda del contenido de la variable elemento en la formación vectorUno. Para ello se necesitan las siguientes declaraciones previas:

VAR
   elemento: INTEGER;
   posicion: Dimension;
   visto: BOOLEAN;

el fragmento de programa que realiza la búsqueda sería el siguiente:

visto := FALSE;
posicion := 0;
WHILE ( NOT visto ) AND ( posicion < Ultimo ) DO
   posicion := posicion + 1;
   visto := elemento = vectorUno[ posicion ]
END

El valor final de la variable booleana visto indica si ha sido encontrado elemento y el valor de la variable posicion apunta la posición en la que ha sido encontrado. El empleo de dos variables tiene el incoveniente de que ambas deben ser analizadas al finalizar la búsqueda para conocer el resultado. Para evitar esto se puede dar a la variable posicion un valor fuera del rango de las posiciones posibles (normalmente la posición cero), para indicar que elemento no ha sido encontrado. Para concluir la búsqueda infructuosa apuntado a la posición cero se puede realizar el recorrido hacia atrás, empezando por Ultimo. Con este planteamiento el resultado es el siguiente:

visto := FALSE;
posicion := Ultimo;
WHILE ( NOT visto ) AND (poisicon > 0) DO
   IF elemento <> vectorUno[ posicion ] THEN
      posicion := posicion -1
   ELSE
      visto := TRUE
   END
END

Cuando se sabe que el vector tiene al menos un elemento, es posible emplear la sentencia REPEAT de la siguiente forma:

visto := FALSE;
posicin := Ultimo;
REPEAT
   IF elemento <> vectorUno[ posicion ] THEN
      posicion := posicion – 1
   ELSE
      visto := TRUE
   END
UNTIL visto OR ( posicion = 0 )

También se puede utilizar la sentencia LOOP, incluso con un vector vacío. En este caso el esquema a emplear es el siguiente:

Iniciar la búsqueda;
LOOP
   IF Final THEN EXIT END
   Verificar encuentro;
   IF Encontrado THEN EXIT END;
   Pasar al siguiente elemento
END

La búsqueda en vectoUno sería de la siguiente forma:

posicion := Ultimo;
LOOP
   IF posicion = 0 THEN EXIT END;
   IF ( elemento = vectorUno[ posicion ] ) THEN EXIT END;
   posicion := posicion – 1
END

La elección del esquema más adecuado depende de la complejidad de las operaciones Verificar encuentro y Pasar al siguiente elemento, y de las posibles simplificaciones que se puedan introducir en ambas empleando uno u otro esquema.

11.4.3 Inserción
Cuando los elementos de un vector se van incorporando al mismo de una forma paulatina, uno detrás de otro, se puede aprovechar esta circunstancia para insertar el nuevo elemento en la posición que le corresponda. De esta forma, los datos del vector podrían estar siempre ordenados, lo que supone grandes ventajas.

En general, una operación de inserción de un nuevo elemento en una formación supone desplazar algunos de sus datos actuales para conseguir el hueco que le corresponde al nuevo elemento y después insertarlo en el hueco. Un posible esquema sería:

Iniciar inserción;
WHILE ( NOT Encontrado hueco ) AND ( NOT Final ) DO
   Desplazar elemento;
   Pasar al siguiente elemento

END
Insertar nuevo elemento

Este esquema, para la inserción de elemento dentro de los N primeros elementos de vectorUno, que ya están ordenados, se convierte en el siguiente fragmento de programa:

j := N;
WHILE ( elemento < vectorUno[ j ] ) AND ( j >= 1 ) DO
   vectorUno[ j + 1 ] := vectorUno[ j ];
   j := j – 1
END;
vectorUno[ j + 1 ] := elemento;

Evidentemente, después de la inserción, el vector tiene un elemento más. Por tanto, el valor de N siempre deberá ser menor que Ultimo.

11.4.4 Ordenación por inserción directa
En este apartado se aborda una solución para la ordenación de un número indeterminado de datos dentro de un vector. Existen diversos métodos de ordenación de vectores cuyo estudio cae fuera del alcance de es libro (entradas de blog). El método de ordenación por inserción directa es uno de los más sencillos y está basado en el esquema de inserción mostrado en el apartado anterior. Por ejemplo, se trata de ordenar vectorUno definido como vector de diez elementos y que inicialmente está desordenado, tal como se muestra en la Figura 11.3.

Figura(11_3)
       Figura 11.3. Vector Inicial

Para comenzar, el primer elemento ( 21 ) se supone ordenado. A continuación, extraemos el segundo elemento ( 5 ) y se genera un hueco, que se puede utilizar para ampliar el vector ya ordenado. El método de ordenación consiste en insertar el elemento extraído en su lugar correspondiente entre los elementos ya ordenados. Este proceso se repite con el tercero, cuarto, quinto, … y décimo elemento hasta quedar ordenado todo el vector. La secuencia de inserciones de los sucesivos elementos del vector es la siguiente:

Figura(11_3a)

En la secuencia se muestra la posición del hueco inmediatamente antes de la inserción del siguiente elemento. La línea quebrada indica hasta qué punto se amplía el vector ordenado con cada nueva inserción. La inserción se realiza desde la posición anterior a la del elemento extraído. La variable elemento guarda el elemento extraído de la posición i. La ordenación total del vector se consigue mediante el recorrido de todos sus elementos, desde el segundo, para buscarles su hueco e insertarlos en él. Así, el fragmento de programa de ordenación es el siguiente:

FOR i := 2 TO Ultimo DO
   elemento := vectorUno[ i ]; j := i – 1;
   WHILE ( elemento < vectorUno[ j ] ) AND ( j >= 1 ) DO
      vectorUno[ j + 1 ] := vectorUno[ j ];
      j := j-1
   END;
   vectorUno[ j + 1 ] := elemento
END

Este programa es válido para cualquier tamaño del vector, ya que sólo depende del valor que tome la constante Ultimo.

11.4.5 Búsqueda por dicotomía
Cuando los datos están ordenados la búsqueda resulta mucho mas rápida. Si comparamos el elemento a buscar con el que está justo en la mitad de los datos ordenados, podemos decidir si es ése el elemento que buscamos o debemos continuar buscando, pero sólo en la mitad derecha o sólo en la mitad izquierda.

El mismo proceso se puede repetir con la mitad elegida, comparando con el elemento que está en el centro de dicha mitad. En cada comparación, la búsqueda se reduce a comprobar si el dato buscado está entre la mitad de los anteriores. La búsqueda finaliza cuando el elemento se encuentra, o bien cuando no es ninguno de los dos datos consecutivos a los que queda reducida la comparación después de sucesivas divisiones en mitades. Esta búsqueda se denomina búsqueda por dicotomía.

Como esquema general de búsqueda sigue siendo válido el mismo utilizado anteriormente. Sin embargo, ahora es necesario cambiar la obtención del siguiente elemento a comparar. Como ejemplo, realizaremos la búsqueda por dicotomía de elemento vectorUno. Se necesitan dos variables para acotar el trozo de vector que todavía queda por comprobar y otra variable para señalar el punto medio de ambas. Estas variables las denominaremos izq, dch y mitad. Sus declaraciones serán:

VAR izq, dch, mitad: Dimension;

El fragmento de programa sería como sigue:

posicion := 0; izq := 1; dch := Ultimo;
WHILE ( posicion = 0 ) AND ( izq <= dch ) DO
   mitad := ( izq + dch ) DIV 2;
   IF Elemento = VectorUn[ mitad ] THEN
      posicion := mitad
   ELSIF Elemento < VectorUno[ mitad ] THEN
      dch := mitad – 1
   ELSIF
      izq := mitad + 1
   END
END

En este caso la variable posicion se utiliza para conocer si ha sido encontrado Elemento y se inicializa a cero (no encontrado). Este valor sólo se modifica cuando se consigue encontrar el elemento buscado. La búsqueda por dicotomía se puede aplicar también, por ejemplo, en el esquema de ordenación por inserción, para localizar el lugar en que hay que insertar el nuevo elemento.

11.4.6 Simplificación de las condiciones de contorno
La programación de operaciones con vectores, realizadas elemento a elemento, exige con frecuencia realizar un tratamiento especial de los elementos extremos del vector o, en general, de los elementos del contorno de una formación. A continuación veremos algunas técnicas particulares para evitar la necesidad de detectar de manera explícita si se ha llegado a un elemento del contorno, o realizar con él un tratamiento especial.

Por ejemplo, en el procedimiento general de búsqueda es necesario comprobar con cada iteración si no se ha alcanzado todavía el Final del vector. Esto complica la condición del bucle de iteración y supone un tiempo adicional en la ejecución de cada iteración. Si el dato que se trata de buscar está dentro del vector, antes o después se termina encontrando y nunca se intenta buscar fuera de los límites del mismo. En este caso la condición Final resulta innecesaria. Por tanto, se podrá prescindir de la condición Final cuando se puede asegurar que cualquier dato que se busque estará en el vector. La manera de asegurar esto es incluir el dato en el vecor antes de comenzar la búsqueda. El vector se amplía, según se muestra en la Figura 11.4, en un elemento más de índice 0. En él se copia el dato a buscar antes de iniciar la búsqueda para que actúe como centinela (C) y asegure que la búsqueda nunca acaba de forma infructuosa.

Figura(11_4)
       Figura 11.4. Vector con centinela

Ahora, el esquema general de búsqueda se simplifica de la siguiente forma:

Iniciar centinela;
Iniciar búsqueda;
WHILE ( NOT Encontrado ) DO
   Pasar al siguiente elemento
END

Este esquema para la búsqueda del contenido de la variable elemento en el vectorUno requiere modificar la declaración de la dimensión del vector de la siguiente forma:

TYPE Dimension = [ 0..Ultimo ];
         TipoVector = ARRAY Dimension OF INTEGER;

y se tiene que redifinir la variable:

VAR vectorUno: TipoVector;

La posición cero del vector estará destinada a situar el centinela y la búsqueda se simplificaría de la siguiente forma:

vectorUno[ 0 ] := elemento;
posicion := Ultimo;
WHILE elemento <> vectorUno[ posicion ] DO
   posicion := posicion – 1
END

Igual que antes, si al final de la búsqueda, la variable posición tiene un valor igual a cero, quiere decir que la búsqueda ha sido infructuosa: el elemento encontrado ha sido el centinela.

La misma técnica del centinela se puede emplear en la inserción, lo que simplifica el algoritmo de ordenación. La nueva redacción del programa es la siguiente:

FOR i := 2 TO Ultimo DO
   elemento := vectorUno[ i ];
   vectorUno[ 0 ] := elemento; j := i – 1;
   WHILE elemento < vectorUno[ j ] DO
      vectorUno[ j + 1 ] := vectorUno[ j ];
      j := j – 1
   END;
   vectorUno[ j + 1 ] := elemento
END

Como se puede observar, la técnica del centinela simplifica las condiciones de contorno para cualquier operación que se realice con un vector y el programa resulta más simple y fácil de entender.

Cuando se trabaja con matrices, también se pueden simplificar las condiciones de contorno utilizando matrices orladas. Estas matrices se dimensionan con dos filas y dos columnas más de las necesarias tal como se muestra en la Figura 11.5.

Figura(11_5)
        Figura 11.5. Matriz Orlada

En esa matriz se inicializa todo su contorno (filas y columnas extras) con un valor tal que permita identificar dicho contorno (C). Si se elige adecuadamente el valor C, cualquier operación que se realice con la matriz no necesita tener en cuenta sus límites declarados. Además, en algunos casos el contorno puede jugar un papel fundamental en la operación con la matriz.

Para ilustrar el uso de una matriz orlada, supongamos que tenemos una imagen en blanco y negro digitalizada dentro de una matriz definida de la siguiente forma:

CONST       Puntos = 20;
                  Blanco = 0;
                  Negro = 5;

TYPE   Grises = [ Blanco .. Negro ];
            Indice = [ 1 .. Puntos ];

VAR   imagen: ARRAY Indice, Indice OF Grises;

Cada elemento de la matriz guarda el nivel de grises del correspondiente punto de la imagen. Para tratar cada punto de la imagen individualmente basta con hacer un recorrido completo, sin ninguna complicación. Por ejemplo, para contrastar la imagen y reducir todos los puntos gris claro a blanco y todos los grises oscuro a negro, bastará escribir:

FOR i := 1 TO Puntos DO
   FOR j := 1 TO Puntos DO
      IF imagen [ i, j ] <= Nivel THEN
         imagen [ i, j ] := Blanco
      ELSE
         imagen [ i, j ] := Negro
      END
   END
END;

Supongamos ahora que queremos recortar la imagen, esto es, eliminar aquellos puntos externos de la imagen que están en blanco, pero dejando los puntos blancos que son interiores y están rodeados de puntos negros. El tratamiento de cada punto exige examinar al mismo tiempo los puntos contiguos. El programa se simplifica si se garantiza que todo punto útil de la imagen tiene puntos contiguos en todas las direcciones, es decir, no hay situaciones excepcionales en los bordes.

Para ello lo mejor es que la matriz de la imagen sea una matriz orlada, por lo que se redefine de la siguiente forma:

TYPE Indice = [ 0 .. Puntos + 1 ];
         TipoImagen = ARRAY Indice, Indice OF Grises;

Para establecer el nivel de contorno se declara un valor de borde y se redefine la escala de grises de la siguiente forma:

CONST   Borde = -1;
TYPE   Grises = [ Borde .. Negro ];

Suponiendo que imagen está ya contrastada anteriormente y que su contorno (es decir, la orla) está inicializado al valor de Borde, el recorte se realizaría mediante sucesivos recorridos de toda la matriz en los que los puntos blancos que tienen algún punto Borde alrededor deben pasar también a puntos de Borde. El proceso de recorte se termina cuando en un recorrido completo de toda la imagen no hay ningún punto que cambie. Esta forma de operar se denomina de fuerza bruta, y puede ser poco eficiente, pero es muy sencilla de programar. El fragmento de programa que realiza ésto es el siguiente:

REPEAT
   fin := TRUE;
   FOR   i := 1 TO Puntos DO
      FOR j := 1 TO Puntos DO
         IF ( imagen [ i, j ] = Blanco ) AND (( imagen [ i-1, j ] = Borde )
             OR ( imagen [ i, j-1 ] = Borde )
             OR ( imagen [ i, j+1 ] = Borde )
             OR ( imagen [ i+1, j ] = Borde )
         THEN
            imagen [ i, j ] := Borde; fin := FALSE
         END
      END
   END
UNTIL fin

Este ejemplo es un fragmento de uno de los programas completos que figura como ejemplo al final del Tema.

11.5 Vector de caracteres: Ristra (String)

Debido a su frecuente uso, en el Tema 2 fueron ya presentadas las constantes de tipo ristra. Sin embargo, hasta ahora no hemos podido utilizar variables de este tipo. Esto se debe a que en realidad las ristras son vectores de caracteres y los vectores no han sido estudiados hasta este Tema. Sin embargo, en todos los lenguajes es habitual que las ristras tengan ciertas peculiaridades que no tienen el resto de los vectores y por esta razón son objeto de este apartado específico.

En Modula-2 cualquier vector cuya declaración sea de la forma:

ARRAY [ 0 .. N ] OF CHAR

se considera una ristra o string, con independencia de su longitud particular, esto es, del valor de N. Las características peculiares de las ristras son:

   a) El primer elemento de una ristra siempre es el índice igual a cero.

   b) En un vector de esta clase se pueden almacenar ristras de diferentes longitudes (si caben). Para distinguir la longitud útil en cada momento se reserva siempre espacio para un carácter más, y se hace que toda ristra termine con un carácter nulo (0C) situado al final.

Por tanto, para declarar una ristra de veinte caracteres se debe hacer de la siguiente forma:

TYPE
   Ristra20 = ARRAY [ 0 .. 20 ] OF CHAR;

La declaración de variables de este tipo se hace de la forma habitual:

VAR
   nombre, apellido: Ristra20;
   direccion: ARRAY [ 0 .. 40 ] OF CHAR;

La asignación de un valor a una variable de tipo ristra se realiza de la siguiente forma:

apellido := "Gonzalez";
direccion := "Paseo de la Castellana 345 – 6º";

Como se puede observar, no es necesario asignar una ristra con los veinte o cuarenta caracteres. Cuando el número de caracteres asignados es menor que los declarados, a continuación del último se sitúa el carácter nulo (0C) de final de ristra. Este carácter es especial y no se puede escribir. Lo que nunca se puede hacer es asignar más caracteres de los declarados pues se rebasarían los límites previstos y se provocaría un error. Al igual que con cualquier otro tipo de vector, para poder realizar asignaciones entre variables de tipo ristra es necesario que ambas sean del mismo tipo. Por ejemplo:

nombre := apellido;

Estas variables se pueden utilizar como argumento del procedimiento de escritura de ristras. Por ejemplo:

WriteString( "APELLIDO : " ); WriteString( apellido );

produce el siguiente resultado:

APELLIDO : Gonzalez

El procedimiento de escritura sólo escribe el contenido de la variable hasta el primer carácter nulo, aunque en versiones antiguas del lenguaje puede que se escriba el vector completo.

También es posible utilizar variables de tipo ristra con el procedimiento de lectura de ristras que suele estar disponible en el módulo InOut. Por ejemplo:

ReadString( nombre );

Las características y funcionamiento de este procedimiento dependen del compilador concreto y por tanto se debe consultar el manual correspondiente. En cualquier caso, el procedimiento guardará en la variable la ristra introducida por teclado.

11.6 Argumentos de tipo vector abierto

Una de las operaciones que se puede realizar con los vectores es pasarlos como argumento de un procedimiento o función. En su definición se tienen que indicar la estructura y tamaño del vector que se puede pasar como argumento. Por ejemplo:

TYPE TipoVector = ARRAY [ 1 .. 10 ] OF INTEGER;
. . . .
PROCEDURE LeerVector( VAR v: Vector )

Este procedimiento sólo permite operar con vectores de diez elementos de tipo INTEGER. Si dentro del mismo programa se necesita realizar un procedimiento idéntico para vectores de once elementos también de tipo INTEGER, sería necesario realizar un nuevo procedimiento para once elementos. En general, sería necesario realizar una versión distinta del procedimiento para cada tamaño diferente del vector con el que se quiera trabajar. Evidentemente ésto no es la solución más adecuada.

Una forma de trabajar con vectores de diferentes tamaños es definir un tipo único con capacidad para el mayor de todos los que se necesiten. Cuando no se utiliza todo el tamaño, es necesario indicar de alguna forma qué elementos se están empleando realmente. Esto se puede hacer, por ejemplo, almacenando en alguna parte el número de elementos en uso, o marcando el final con un valor nulo como sucede con las ristras. Esto se deberá tener en cuenta en la programación del procedimiento. Con esta solución todos los vectores que se pasen como argumento deben tener el mismo tamaño máximo, lo que supone un despilfarro de memoria en la mayoría de los casos.

Otra solución permitida en Modula-2 es emplear vectores abiertos como argumentos en la definición del procedimiento o función. Un vector abierto es aquél del que sólo se define el tipo de sus elementos, pero no el rango del índice. El tipo implícito de su índice es siempre un subrango comprendido entre 0 y un valor máximo. En Modula-2 se expresa en la forma:

PROCEDURE Muestra( X: ARRAY OF TipoElemento )

Esta definición indica que es posible pasar en la llamada cualquier vector con una estructura tal como la siguiente:

ARRAY [ P .. Q ] OF TipoElemento;

Por ejemplo, si tenemos la siguiente declaración de función:

PROCEDURE Simetrico( texto: ARRAY OF CHAR ): BOOLEAN;

es válido realizar cualquiera de las siguientes llamadas:

VAR nombre: ARRAY [0..20] OF CHAR;
        rotulo: ARRAY [1..10] OF CHAR;

(1)   IF Simetrico( rotulo ) THEN …
       …
(2)   IF Simetrico( nombre ) THEN …
       …
(3)   IF Simetrico( "abracadabra" ) THEN …

Para hacer referencia dentro de la función al tamaño del vector utilizado en cada llamada, se puede usar la función predefinida siguiente;

HIGH( X )

Esta función devuelve como resultado el valor superior del índice del vector pasado como argumento X en la llamada. Por ejemplo, HIGH( texto ) vale 9 en la llamada (1) del ejemplo anterior, 20 en la llamada (2), y 11 en la llamada (3). Nótese que internamente el rango del índice siempre se cuenta como si empezase en cero.

Un ejemplo típico de la utilidad de los vectores abiertos es el procedimiento predefinido WriteString. Este procedimiento se puede utilizar con ristras constantes o variables de cualquier tamaño. Su funcionamiento puede describirse basándose en el procedimiento Write para escribir un carácter, de la manera siguiente:

PROCEDURE WriteString( s: ARRAY OF CHAR );
   CONST   Nulo = 0C;
   VAR   k: INTEGER;
BEGIN
   k := 0;
   LOOP
      IF k > HIGH( s ) THEN EXIT END;
      IF s[ k ] = Nulo THEN EXIT END;
      Write( s[ k ] );
      INC( k )
   END
END WriteString;

De la misma forma, es posible definir un procedimiento para ordenar vectores de cualquier tamaño. Este era el problema que se planteaba al comenzar este tema. Por ejemplo, para ordenar vectores de enteros se puede definir un procedimiento con un argumento del tipo vector abierto, que aplique el método de ordenación por inserción. El vector pasado como argumento debe tener la primera posición reservada para usarla como centinela. El código sería:

PROCEDURE Ordenar( VAR v: ARRAY OF INTEGER );
   VAR i, j: Dimension;
           elemento: INTEGER;
BEGIN
   FOR  := 2 TO HIGH( v ) DO
      elemento := v[ i ];
      v[ 0 ] := elemento;
      j := i – 1;
      WHILE elemento < v[ j ] DO
         v[ j + 1 ] := v[ j ];
         j := j – 1
      END
      v[ j + 1 ] := elemento
   END
END Ordenar;

Finalmente, es importante resaltar que no se pueden utilizar matrices abiertas.

El juego del Half Life 2: Parte I

Este juego lleva ya algún tiempo en el mercado, recientemente ha aparecido a la venta la versión Half Life 2: Episodio 2, el cuál iremos viendo a medida que se vayan creando estas entradass de blog en la categoría de video blog. Comencemos por los videos;

 

 

Este video contiene la introducción del juego en la que se nos sumerge en el universo del half life. La historia comienza con la llegada en tren a una ciudadela, pulsar "play" para ver.

 

 

 

 

 

 

 

 

 

 

 

 

   Hemos avanzaó por la estación del tren y tras saltar por la ventana continuamos investigando por los pasillos, habitaciones, etc.

 

 

 

 

 

 

 

 

 

 

   Debemos conseguir alcanzar el tejado para escapar del asedio de los guardias.

 

 

 

 

 

 

 

 

 

 

 

   Hemos encontrado a la hija del doctor de Black Mesa, que nos lleva hasta un laboratorio en el que tomaremos el traje.

 

 

 

 

 

 

Y en próximas entregas seguiremos con la historia del juego…

Unas partidas en ICC

   A continuación mis 4 últimas partidas jugadas en este Portal de Internet.

                     

                    

LOS CUATRO PERROS

Un galgo, un dogo, un alano y un podenco. Éste último come más que el galgo, el alano come más que el galgo y menos que el dogo, pero éste come más que el podenco.

                          problema5

¿Cuál de los cuatro será más barato de mantener?


::SOLUCIÓN::
aquí

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

UNIDAD DIDÁCTICA III

 

 

Tema 11
Formaciones

Las estructuras de datos de tipo formación son quizá las más básicas, o al menos las que se introdujeron primero en los lenguajes de programación imperativos. Puede afirmarse que no hay ningún programa real interesante que no use estructuras de esta clase.

En este tema se introducen tanto estas estructuras en sí, como las operaciones típicas para su manpulación y las técnicas particulares que facilitan su programación, incluyendo centinelas y matrices orladas.

11.1 Necesidad de las formaciones

En el Tema 5 se realizó un programa para ordenar 3 datos. El interés de la ordenación de cualquier tipo de dato (números, nombres, fechas, etc.) resulta más evidente cuando la cantidad de datos a ordenar es de cientos o miles de datos, el trabajo de ordenación resulta tedioso y es más adecuado realizarlo utilizando un computador.

Si se quiere realizar un programa de ordenación con las estructuras de datos presentadas hasta este momento sería necesario declarar tantas variables del mismo tipo como datos se tratan de ordenar. En el programa del Tema 5 se necesitaron tres variables, valorUno, valorDos y valorTres. Además el tratamiento de cada variable se debe realizar por separado: dentro del texto del programa se tienen que hacer las correspondientes comparaciones e intercambios entre cada una de las parejas de variables. Por ejemplo, en el mencionado programa se tenía el siguiente fragmento:

(*– Primer Paso: Ordenar 2 primeros datos –*)
IF valorUno > valorDos THEN
   auxiliar := valorUno;
   valorUno := valorDos;
   valorDos := auxiliar
END;

(*– Segundo Paso: Situar el 3º dato –*)
IF valorTres < valorUno THEN
   auxiliar := valorTres;
   valorTres := valorDos;
   valorDos := valorUno;
   valorUno := auxiliar
ELSIF valorTres < valorDos THEN
   auxiliar := valorDos
   valorDos := valorTres;
   valorTres := auxiliar
END;

Evidentemente esta forma de realizar el programa es imposible de generalizar para la ordenación de un número cualquiera de datos. Además, este mismo problema se reproduce en cualquier programa en el que se trate de manejar una cantidad razonable de datos, todos del mismo tipo. Si tenemos en cuenta que uno de los primeros objetivos de los computadores fue precisamente manejar grandes cantidades de información, se comprende fácilmente porqué ya en los primeros lenguajes de programación se disponía de estructuras de datos para resolver estos problemas. Estas estructuras denominadas genéricamente formaciones, y permiten la generalización de la declaración, referencia y manipulación de datos del mismo tipo. En los siguientes apartados se estudian distintas clases de formaciones y las características de cada una.

11.2 Vectores

Como se muestra en la Figura 11.1, un vector está constituido por una serie de valores, todos ellos del mismo tipo, a los que se les da un nombre común que identifica a toda la estructura globalmente. Cada valor concreto dentro de la estructura se distingue por su índice o número de orden que ocupa en la serie.

Figura(11_1)
       Figura 11.1. Estructura Vector

Como se puede observar, esta estructura es análoga al concepto matemático de vector, en el que el vector completo se identifica por un nombre único y cada elemento particular mediante el correspondiente subíndice:

V = (V1, V2, V3, … , Vn-2, Vn-1, Vn )

En cuanto al aspecto de programación se puede establecer un paralelismo entre la estructura de programación en la que se repite la misma acción un número de veces determinado: sentencia FOR, y la estructura de datos vector en la que también se repiten un número de veces determinado el mismo tipo de dato. Como se verá posteriormente, la sentencia FOR es la que mejor se adecúa al manejo de vectores y en general de todo tipo de formaciones.

11.2.1 Declaración de vectores
En Modula-2, una estructura de tipo vector se declara de la siguiente forma:

TipoVector = ARRAY TipoIndice OF TipoElemento

donde TipoVector es el nombre del nuevo tipo de vector que se declara. El TipoIndice es el tipo al que pertenece el índice y puede ser un escalar enumerable, un subrango o cualquier de los tipos predefinidos CHAR o BOOLEAN. Finalmente TipoElemento puede ser cualquier tipo y corresponde al tipo de dato que constituye cada uno de los elementos del vector. A partir de los tipos siguientes:

TYPE Colores = ( Rojo, Azul, Amarillo );
Longitud = [0..Maximo];
Dimension = [1..Ultimo];
DiasSemana = ( Lunes, Martes, Miercoles, Jueves, Viernes, Sabado, Domingo );
HorarioDia = SET OF [0..23];
. . . .

Se pueden hacer las declaraciones de vectores siguientes:

. . . .
Intensidad = ARRAY Colores OF REAL;
TipoVector = ARRAY Dimension OF INTEGER;
Ristra = ARRAY Longitud OF CHAR;
HorarioSemana = ARRAY DiasSemana OF HorarioDia;

En muchos casos el tamaño del vector es un parámetro del programa que podría tener que cambiarse al adaptarlo a nuevas necesidades. Si es así, resulta aconsejable que en la declaración del tipo subrango que dimensiona un vector se declare previamente como constante el valor superior, como se ha hecho en el caso de los valores Maximo y Ultimo. Estas constantes podrían haber sido declaradas previamente de la siguiente forma:

CONST           Maximo = 100;
                      Ultimo = 10;

De esta manera, el programa queda parametrizado por dichas constantes. En las modificaciones posteriores, si se quiere adaptar el tamaño del vector sólo es necesario modificar esta constante. Además, como se verá posteriormente, es habitual utilizar el tamaño del vector en las operaciones de recorrido y búsqueda de los vectores, que se pueden entonces programar en función de la misma constante.

Para poder utilizar los tipos declarados es necesario declarar a su vez, posteriormente, las correspondientes variables. Por ejemplo:

VAR  horarioUno, horarioDos : HorarioSemana;
         frase : Ristra;
         vectorUno, vectorDos : TipoVector;

También es posible declarar una variable como vector, sin necesidad de haber declarado previamente el correspondiente tipo, poniendo la descripción del vector como tipo de la variable. En este caso el tipo es anónimo, es decir, no tiene nombre. Por ejemplo:

VAR   miVector : ARRAY [1..10] OF INTEGER;
          miFrase : ARRAY [0..100] OF CHAR;

En muchos casos es preferible realizar la declaración previa del tipo, dado que sólo serán compatibles aquellas variables que hayan sido declaradas como variables del mismo tipo. Por ejemplo la variable miVector no es compatible con las variables vectorUno y vectorDos, aunque estas últimas sí lo son entre ellas. Como se verá posteriormente, la compatibilidad fija las operaciones que se pueden realizar con los vectores. Por otro lado, resulta mucho más fácil de comprender un programa cuando para todas las variables que no son de un tipo predefinido se declara su tipo previamente.

11.2.2 Operaciones con vectores
La operación más sencilla entre vectores es la asignación de un vector a otro. Por ejemplo:

vectorDos := vectorUno;

Esta operación efectúa una copia de todos los elementos del vector VectorUno en el vector VectorDos. Los valores que tuvieran los elementos del vector VectorDos se pierden. Para poder realizar esta operación es necesario que ambos vectores sean de tipos compatibles. Como se indicó anteriormente, esto sólo se consigue cuando ambos son del mismo tipo, o se han declarado conjuntamente. Se produce un error cuando se trata de realizar una asignación entre vectores de distintos tipos como la siguiente:

miVector := vectorUno;

Habitualmente no se opera con todos los elementos de un vector de una manera global. La mayoría de las operaciones interesantes hay que realizarlas en Modula-2 operando con sus elementos uno por uno. La referencia a un elemento concreto de un vector se hace mediante el nombre del vector seguido, entre corchetes, del índice del elemento referenciado.
Por ejemplo:

miVector [3]
frase [23]
horarioUno [Lunes]

Un elemento de un vector puede formar parte de cualquier expresión con constantes, variables u otros elementos de vector. Para estas expresiones se tendrá en cuenta el tipo de los elementos del vector y las reglas de compatibilidad. Por ejemplo:

miVector[3] := 3*vectorUno[3] + 2*vectorDos[3]
frase[23] := "A"
horarioUno[Lunes] := HorarioDia{9..13, 15..17}

Aunque el vector miVector es incompatible con vectorUno y vectorDos, sus elementos son todos del mismo tipo INTEGER y por tanto, la primera de las expresiones anteriores es totalmente correcta.

Como índice para designar un elemento de un vector se puede utilizar una variable o expresión, siempre que sean compatibles con el tipo declarado para el índice de dicho vector. Por ejemplo:

miVector[j] := 3*vectorUno[i] + 2*vectorDos[i+3]
frase[origen+indice] := " "
horarioUno[dia] := horarioUno[Lunes]

para ello es necesario que las variables utilizadas hayan sido declaradas previamente. Por ejemplo:

VAR i, j : Dimension;
        origen, indice : INTEGER;
       dia : DiasSemana;

Las variables Origen e Indice son de tipo INTEGER, que es compatible con el subrango Dimension.

La posibilidad de utilizar variables o expresiones para el cálculo del índice de un vector es fundamental en cualquier programa que utilice vectores, como se verá a lo largo de este tema. Sin embargo, siempre se debe comprobar exhaustivamente que no existe la posibilidad de que por error el índice calculado por la expresión o guardado en la variable se salga fuera del subrango o tipo enumerado declarado para el vector. No obstante, si esto ocurre el resultado será totalmente impredecible dado que no estaremso haciendo referencia a un elemento del vector que no tiene existencia real. En esta situación, y dependiendo del compilador, se producirá un error de ejecución y/o la parada del programa.

Finalmente, otra operación que se puede realizar con los vectores es utilizarlos como argumentos de procedimientos o funciones. Por ejemplo, si tenemos unas declaraciones de procedimientos tales como las siguientes:

PROCEDURE LeerVector( VAR V: TipoVector )
. . . .
PROCEDURE EscribirVector( V: TipoVector )

para utilizar dichos procedimientos se debe emplear como argumento un vector del mismo tipo de la siguiente forma:

LeerVector( vectorUno )
. . . .
EscribirVector( vectorDos )

En el primer caso, el argumento se pasa por referencia y el procedimiento LeerVector utiliza directamente el vector vectorUno, por lo que puede modificar cualquiera de sus elementos.

En el segundo caso, el argumento se pasa por valor y el procedimiento EscribirVector no puede modificar ningún elemento del vectorDos. En este caso el efecto del procedimiento es equivalente a realizar una copia del vector y operar con dicha copia dentro del procedimiento. Hay que tener en cuenta que si el tamaño del vector es muy grande, la operación de copiar cientos o miles de datos cada vez que se llama al procedimiento puede necesitar más tiempo que la ejecución del propio procedimiento. Además, se necesita una cantidad de memoria adicional igual al tamaño del vector para guardar la copia. Debido a estas razones y por motivos de eficiencia, cuando el vector es muy grande se suele declarar como variable global a todos los procedimientos que los utilizan o se pasa siempre por referencia aunque no se necesite modificar ninguno de sus elementos.

11.3 Formaciones anidadas. Matrices

Según se indicó anteriormente, los elementos de un vector pueden ser de cualquier tipo. En los ejemplos anteriores se han utilizado vectores con elementos de tipo conjunto. Igualmente, es posible definir y utilizar vectores cuyos elementos sean a su vez otros vectores anidados dentro del primero, tal como se muestra en la Figura 11.2.

Figura(11_2)
     Figura 11.2. Formación anidada: Matriz

Estas formaciones anidadas constituyen las matrices y responden al concepto matemático del mismo nombre, en el que el grado de anidamientos expresa si la matriz es de 2, 3 o 4 o más dimensiones.

11.3.1 Declaración de matrices
Mediante vectores, la declaración de una matriz de 2 dimensiones se podría realizar de la siguiente forma:

TYPE MatrizColores = ARRAY Dimension OF ARRAY Colores OF REAL

Sin embargo, esto exige repetir las palabras claves ARRAY y OF con cada nuevo anidamiento. En Modula-2, y habitualmente en todos los lenguajes, se puede evitar esta repetición utilizando una forma genérica para la declaración de formaciones, en la que es posible indicar dos o más TipoIndice separados por comas de la siguiente forma:

TipoMatriz =
         ARRAY TipoIndice1, TipoIndice2, … OF TipoElemento

Esta forma de declaración es más simple y fácil de comprender, y por tanto resulta más aconsejable su empleo. La declaración anterior se realizaría de la siguiente forma:

TYPE MatrizColores = ARRAY Dimension, Colores OF REAL

Al igual que con los vectores, para manejar matrices es necesario declarar las correspodientes variables. Esta declaración también puede realizarse directamente sin la declaración previa del tipo. Por ejemplo:

VAR   matrizUno, matrizDos: MatrizColores;
          A, B, C: ARRAY [ 1..3 ], [ 1..3 ] OF INTEGER;

Como en el caso de los vectores, el programa resulta más flexible cuando se realizan todas las declaraciones de los tipos utilizados. Por ejemplo:

CONST   Mayor = 3;
TYPE
   TipoIndice = [ 1 .. Mayor ];
   TipoMatriz = ARRAY TipoIndice, TipoIndice OF INTEGER;
VAR A, B, C: TipoMatriz;

11.3.2 Operaciones con matrices
Con el requisito de compatibilidad de tipos, siempre es posible asignar una matriz completa a otra. Por ejemplo:

matrizDos := matrizUno;

Para referirse a un elemento de una matriz, hay que tener en cuenta cómo ha sido declarada. Si la matriz fue declarada como vector anidado, se tiene que hacer referencia a un elemento del vector principal, que es a su vez un vector, y dentro de él al elemento del vector anidado y así sucesivamente. Por ejemplo:

matrizUno[5] [Azul]

Si la declaración fue como formación genérica, la referencia a los elementos se realiza separando los índices por comas y encerrados todos ellos entre corchetes. En este caso tenemos:

matrizUno[ 5, Azul ]

Dentro de una matriz se puede hacer referencia a todo un vector o matriz como un único elemento. Por ejemplo:

matrizUno[ 5 ]

es un elemento vector, formado por los valores reales para cada uno de los tres colores (Rojo, Azul y Amarillo). Con estos elementos también es posible realizar asignaciones globales de vectores completos, siempre que sean compatibles. Por ejemplo:

matrizUno[ 3 ] := matrizDos[ 6 ];

Para cualquiera de los índices de una matriz se pueden emplear variables o expresiones, siempre que sean compatibles con el tipo declarado para el correspondiente índice. Al igual que en el caso de los vectores se debe comprobar que tales expresiones o variables nunca dan como resultado un valor que esté fuera del subrango o tipo enumerado declarado para los índices. Por ejemplo, si se ha declarado:

VAR   alfa: Dimension;
          color: Colores;
          i, j: TipoIndice;

será posible escribir

A [ i, j ] := 34
. . . .
matrizUno[ alfa, color ] := matrizDos[ alfa+3, color ]

Finalmente, el paso de una matriz como argumento de un procedimiento o función es totalmente semejante al paso de un vector. En este caso los problemas de eficiencia en el paso de matrices por valor pueden ser mayores al aumentar el número de elementos.

Para terminar este apartado se detallan a continuación las reglas sintácticas que definen la declaración de toda clase de formaciones en Modula-2:

Tipo_formación ::=
          ARRAY Tipo_índice { , Tipo_índice } OF Tipo_elemento
Tipo_índice ::= Tipo_simple

Para el uso de elementos, se tiene:

Variable_indexada ::=
          Varaible_tipo_formación [ Lista_de_expresiones ]
Lista_de_expresiones ::=
          Expresión { , Expresión }

11.4 Esquemas típicos de operación

En la utilización habitual de las formaciones se presentan de forma reiterada ciertas operaciones que responden a un mismo esquema. En este apartado se estudian algunos de los esquemas típicos de operación para el manejo de formaciones.

14.1.1 Recorrido
La operación de recorrido consiste en realizar la misma operación con todos y cada uno de los elementos de una formación. Para esta operación se deben emplear estructuras de tipo FOR. Las variables utilizadas como índices de los FOR deben ser de los mismos TipoIndice utilizados en la declaración de la formación y su rango de variación será desde un valor extremo al otro del rango de la misma declaración. Evidentemente, el recorrido se puede hacer desde el extremo inferior al superior o viceversa según interese en cada situación concreta. Por ejemplo, el esquema para un recorrido sobre el vector horarioUno sería el siguiente:

FOR dia := Lunes TO Domingo DO
   (*– Operaciones a realizar con cada elemento –*)
      horarioUno[ Dia ] := ….
END

Si la formación es de tipo matriz, se necesitan tantos FOR anidados como anidamientos tenga la formación. Por ejemplo, para la formación matrizUno empleando un recorrido descendente para el índice de tipo Dimension, se tiene el siguiente esquema:

FOR alfa := Ultimo TO 1 BY -1 DO
   FOR color := Rojo TO Amarillo DO
      (*– Operaciones a realizar con cada elemento –*)
         matrizUno[ alfa, color ] := ….
   END
END

El recorrido es la operación típica que se debe realizar con una formación cuando se quieren inicializar todos sus elementos. Por ejemplo, la inicialización a cero de todos los elementos de la matriz C, se realiza de la siguiente forma:

FOR i := 1 TO Mayor DO
   FOR j := 1 TO Mayor DO
      C [ i, j ] := 0
   END
END

Si se quieren escribir los valores de la matriz C, por filas, se puede utilizar el mismo esquema, en el que al finalizar cada fila se salta a una nueva línea:

FOR i := 1 TO Mayor DO
   FOR j := 1 TO Mayor DO
      WriteInt( C[ i, j ], 8 )
   END;
   WriteLN
END

La multiplicación de dos matrices A y B para dejar el resultado en la matriz C es un ejemplo muy interesante de recorrido. Primeramente, se inicializa cada elemento de la matriz C[ i, j ] a cero utilizando el esquema anterior. A continuación, al mismo elemento inicializado se le van sumando los productos de cada uno de los elementos de la fila i de la matriz A por los correspondientes elementos de la columna j de la matriz B. Este cálculo de los productos para cada elemento se consigue mediante otro recorrido parcial anidado al de inicialización, sobre los elementos de la fila/columna afectados:

FOR i := 1 TO Mayor DO
   FOR j := 1 TO Mayor DO
      C [ i, j ] := 0;
      FOR k := 1 TO Mayor DO
         C[ i, j ] := C[ i, j ] + A[ i, k ] * B[ k, j ]
      END
   END
END

ME RÍO DEL RÍO

Una tarde, Mario se montó en su barca y remó por el río desde su pueblo hasta el pueblo vecino. Después de hacer sus compras, Mario volvió a su pueblo por el mismo camino. El río estaba quieto como un plato. Al día siguiente, repitió el mismo recorrido, pero esta vez el río bajaba con cierta velocidad. Como el pueblo vecino estaba río arriba, Mario remó primero contra corriente, pero, durante el regreso, remaba a favor.

problema4

¿Invirtió mas, menos o el mismo tiempo que el día anterior en dar su acostumbrado paseo por el río?

::SOLUCIÓN::

aquí

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

Pruebas de
Evaluación a Distancia

 

En este apartado se enuncian los ejercicios que constituyen las prácticas y las pruebas de evaluación a distancia de la segunda unidad didáctica. Todos ellos deben ser realizados en Modula-2 utilizando la metodología explicada. El grado de dificultad de los ejercicios es creciente y conviene realizarlos siguiendo el orden de los enunciados.

Los enunciados de los ejercicios son los siguientes:

1.- Realizar una función que devuelva un valor booleano cierto o falso si el número que se le pasa como argumento es "perfecto". Para que un número sea "perfecto" es necesario que su valor sea igual a la suma de todos sus divisores incluyendo al 1 y sin incluirle a él mismo. Por ejemplo, los divisores de 6 son el 1, el 2  y el 3; su suma es igual a 6, luego el número 6 es "perfecto". Utilizando la función anterior realizar un programa que escriba la lista de números "perfectos" hasta uno dado, introducido como dato al programa.

2.- Realizar un procedimiento que lea una letra, compruebe que es una de las utilizadas para escribir los números romanos y devuelva su valor, según la siguiente tabla:

          I      –         1                               C          –          100
          V    –          5                               D         –           500
          X     –         10                              M         –          1000
          L     –         50                              Resto   –             0

Utilizando el procedimiento anterior, realizar otro procedimiento que lea un número romano y devuelva su valor entero correspondiente. Este procedimiento tendrá en cuenta las reglas de escritura de los números romanos. Finalmente, utilizando este último procedimiento realizar un programa que lea dos números romanos e indique cuál de ellos es mayor.

3.- Realizar un programa que escriba todas las permutaciones posibles que se pueden obtener a partir de las 4 letras: A, B, C y D. Se sugiere construir cada permutación añadiendo elementos de uno en uno a un conjunto. Esto evitará la repetición de un carácter en la misma permutación y permitirá verificar cuando se ha completado una nueva permutación.

4.- Realizar una función que devuelva el día de la semana cuando se le pasan como argumento el día, el mes y el año de una fecha cualquiera. Utilizando la función anterior escribir un programa al que se le introducen como datos el mes y el año y devuelve como resultado la hora del calendario de dicho mes. Por ejemplo:

¿Mes? 5
¿Año? 2000

                     MAYO     2000
LU      MA      MI      JU      VI      SA      DO
  1         2        3        4       5        6         7
  8         9       10      11     12      13        14
15       16      17      18     19       20        21
22       23      24      25     26       27        28
29       30      31

5.- Realizar un programa que analice un texto terminado en el carácter punto (.) y elabore las siguientes estadísticas:

– Número total de palabras del texto
– Número de palabras que utilizan N o más vocales diferentes
– Número de palabras que utilizan M o más consonantes diferentes

Los valores de N y M se leerán como datos del programa.

6.- Realizar un programa para controlar las plazas de un aparcamiento. El aparcamiento dispone de 24 plazas de dos tamaños diferentes: 14 pequeñas y 10 grandes con la disposición que se muestra a continuación:

Ejercicio6

La asignación se realizará automáticamente según el tamaño del vehículo que se quiere aparcar con el siguiente algoritmo:

– Cada vehículo solamente ocupará una plaza.
– Un vehículo pequeño siempre ocupará una plaza pequeña, salvo que estén todas ocupadas y exista alguna grande libre.
– Un vehículo grande sólo puede aparcar en una plaza grande. Si todas están ocupadas no podrá aparcar aunque estén todas las pequeñas libres.
– De todas las plazas libres, siempre se ocupará primero la de número menor.

El programa tendrá 3 opciones básicas:

Entrada: es necesario indicar el tamaño de coche ( P/G ).
Salida: es necesario indicar la plaza que se deja libre. Por ejemplo: P 5
Situación del aparcamiento: indicando las plazas libres y las ocupadas.