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

 

Tema 6
Metodología de Desarrollo de Programas (II)

 

El objetivo de este Tema es múltiple. En primer lugar se amplía la técnica de refinamientos sucesivos presentada en el Tema 4 con la posibilidad de usar estructuras de selección e iteración.

En segundo lugar se introduce la idea de verificación formal de programas, aunque de una manera muy simplificada, en forma de razonamientos intuitivos sobre las estructuras utilizadas hasta el momento.

Finalmente se trata por primera vez el problema de la eficiencia, y se introduce en forma igualmente simplificada el concepto de complejidad algorítmica.


6.1 Desarrollo por refinamientos usando selección y bucles

En este apartado se ilustra el empleo de la técnica de refinamientos sucesivos explicada en el Tema 4, ampliada ahora con la posibilidad de emplear las nuevas estructuras de selección o bucle. Con ello se tienen tres posibilidades a la hora de refinar una acción compuesta:

  • estructurarla como secuencia de acciones
  • estructurarla como selección de acciones alternativas
  • estructurarla como iteración de acciones

En el Tema 4 se ha presentado ya la metodología para desarrollar esquemas secuenciales. A continuación se amplía la metodología con recomendaciones para desarrollar esquemas de selección y bucles.

6.1.1 Metodología de desarrollo de un esquema de selección
Recordaremos que un esquema de selección consiste en plantear una acción compuesta como la realización de una acción entre varias posibles, dependiendo de ciertas condiciones. Es decir, se trata de elegir para realizar una sola entre varias posibles alternativas.

Para desarrollar un esquema de selección debemos identificar sus elementos componentes. Por tanto habrá que:

a) Identificar cada una de las alternativas del esquema, y las acciones correspondientes.
b) Identificar las condiciones para seleccionar una alternativa u otra.

Como ejemplo, aplicaremos estas recomendaciones al desarrollo de una acción compuesta para calcular cuántos días tiene el mes de Febrero de un cierto año. Reconoceremos que:

a) Las alternativas son que tenga 28 días o que tenga 29. Las acciones serán asignar dicho valor a una variable que almacene el número de días.
          dias := 28      o bien       dias := 29
b) La condición para elegir una acción u otra es que el año sea bisiesto. En forma simplificada (pero válida para años entre 1901 y 2099) expresaremos la condición como equivalente a que el año sea múltiplo de cuatro.
         (anno MOD 4) = 0

Colocando cada elemento identificado en el lugar correspondiente del esquema, tendremos:

IF (anno MOD 4) = 0 THEN
   dias := 29
ELSE
   dias := 28
END

De manera similar se pueden desarrollar esquemas de selección simplificados, con sólo una acción condicionada, o esquemas de selección en cascada en que haya un número más o menos grande de alternativas. Por ejemplo, el esquema anterior podría replantearse realizando primero el tratamiento más común, es decir, que Febrero tenga 28 días, y luego corrigiendo este valor si es necesario.

dias := 28;
IF (anno MOD 4) = 0 THEN
   dias := 29
END

Como ejemplo de selección en cascada, desarrollaremos el cálculo de los días del mes, para cualquier mes del año. Las alternativas son:
31 días: Enero, Marzo, Mayo, Julio, Agosto, Octubre, Diciembre.
30 días: Abril, Junio, Septiembre, Noviembre.
29 días: Febrero (año bisiesto).
28 días: Febrero (año normal).

Para simplificar las expresiones de condición, dejaremos para la última alternativa aquella en que la condición sea más compleja. En este caso sería la de los meses de 31 días, que son los más numerosos. Las otras alternativas podemos situarlas en un orden arbitrario. Al escribir las condiciones debemos tener en cuenta que si hay que evaluar una de ellas es que todas las anteriores han resultado falsas:

IF (mes = 2) AND (anno MOD 4 = 0) THEN
   dias := 29
ELSIF mes=2 THEN
   dias := 28
ELSIF (mes= 4) OR (mes=6) OR (mes=9) OR (mes=11) THEN
   dias := 30
ELSE
   dias := 31
END

6.1.2 Metodología de desarrollo de un esquema de iteración
Una iteración o bucle consiste en la repetición de una acción o grupo de acciones hasta conseguir el resultado deseado. Para desarrollar un esquema de iteración dentro de un programa deberemos identificar cada uno de sus elementos componentes. Al hacerlo hay que identificar simultáneamente las variables adecuadas para almacenar la información necesaria.

En líneas generales se podría proceder de la siguiente manera:

a) Identificar las acciones útiles a repetir, y las variables necesarias. Precisar el significado de estas variables al comienzo y final de cada repetición.
b) Identificar cómo actualizar la información al pasar de cada iteración a la siguiente. Puede ser necesario introducir nuevas variables.
c) Identificar la condición de terminación. Puede ser necesario introducir nuevas variables e incluso acciones adicionales para mantenerlas actualizadas.
d) Identificar los valores iniciales de las variables, y si es necesaria alguna acción para asignárselos antes de entrar en el bucle.

Además de los elementos anteriores, puede ser necesaria alguna acción adicional al comienzo o al final del bucle. Si son acciones muy simples, pueden considerarse parte del esquema de iteración como tal. Si son algo complejas será mejor considerarlas como acciones anteriores o posteriores, siguiendo un esquema secuencial.

El método explicado corresponde al caso general. En bastantes casos el desarrollo de un bucle es mucho más sencillo. Esto ocurre en particular cuando se programan bucles con contador, si las acciones a repetir pueden expresarse directamente en función del contador del bucle. En este caso los pasos b), c) y d) se refunden en uno sólo, consistente en determinar los valores inicial, final y el incremento del contador del bucle.

Desarrollaremos con la técnica indicada un fragmento de programa que imprima los términos de la serie de Fibonacci. Cada término de esta serie se obtiene sumando los dos anteriores. La serie comienza con los términos 0 y 1, que se suponen ya impresos antes del bucle. Se trata de calcular e imprimir tantos términos como sea posible.

Procediendo paso a paso, describiremos cada elemento del desarrollo de manera informal, seguido de su codificación en Modula-2.

a) Acciones útiles a repetir: Imprimir un término.
         WriteInt( termino, 10); WriteLn
   Variables necesarias: El término a imprimir.
         termino: INTEGER;
   Valor al empezar la repetición: Último término impreso hasta el momento.

b) Actualizar las variables al pasar de una repetición a la siguiente:
   Antes de imprimir, calcular el término actual a partir de los dos anteriores (se necesita tener almacenado el penúltimo término).
         aux := termino + anterior;
         anterior := termino;
         termino := aux
   Variables adicionales: El penúltimo término, y una variable temporal.
         anterior: INTEGER;
         aux: INTEGER;

c) Condición de terminación: El término siguiente excedería del rango de los enteros. Hay que evaluar la condición sin calcular explícitamente el valor de dicho término, porque se produciría "overflow".
         MAX(INTEGER)-termino < anterior
(Obsérvese que esta expresión equivale a MAX(INTEGER) < termino + anterior)

d) Valores iniciales de las variables: Los dos primeros términos, 0 y 1.
         anterior := 0;
         termino := 1

El bucle completo sería:

VAR
   termino, anterior, aux: INTEGER;
….

anterior := 0;
termino := 1;
WHILE MAX(INTEGER)-termino >= anterior DO
   aux := termino + anterior;
   anterior := termino;
   termino := aux;
   WriteInt( termino, 10 );
   WriteLN
END


6.2 Ejemplos de desarrollo de programas

A continuación se ilustra la técnica de desarrollo por refinamientos sobre algunos ejemplos típicos.

6.2.1 Ejemplo: Imprimir el borde de un triángulo
Se trata de imprimir con asteriscos el perímetro de un triángulo aproximadamente equilátero, tal como se indica a continuación:

      *
     * *
    *   *
   *     *
  *       *
 *         *
* * * * * * *

Como parámetro del problema se especificará la altura del triángulo. Si la altura es N, habrá que imprimir N líneas, cada una con la configuración de asteriscos que corresponda. El triángulo anterior tiene altura 7. Se pretende además que el triángulo aparezca ajustado a la izquierda; es decir, el primer asterisco de la línea inferior deberá empezar exactamente en la primera posición de esa línea. Las otras líneas empezarán con el espacio en blanco apropiado.

El planteamiento inicial del programa será:

     Imprimir el borde de un triángulo

El primer paso de refinamiento consistirá en decidir si esta acción compuesta debe plantearse como una secuencia de acciones simples, o como selección entre alternativas, o como bucle. Observando que hay tres clases de líneas a imprimir, según el número de asteriscos que contienen, elegiremos la primera opción, y escribiremos:

     Imprimir el borde de un triángulo —>
          Imprimir el vértice superior
          Imprimir los bordes laterales
          Imprimir el borde inferior

El orden en que deben realizarse las acciones viene determinado por el hecho de que la impresora va imprimiendo las líneas sucesivas de arriba a abajo.

A continuación refinaremos cada una de estas acciones. Para ello examinaremos en detalle los caracteres que hay que imprimir en cada línea, en función de la altura del triángulo. Marcando con puntos los espacios en blanco, tendremos:

Línea 1   ……*         N-1 blancos
Línea 2   …..*.*        N-2 blancos, 1 blanco
Línea 3   ….*…*       N-3 blancos, 3 blancos
          …*…..*   
Línea K   ..*…….*     N-k blancos, 2k-3 blancos
          .*………*
Línea N   *.*.*.*.*.*.*   N asteristos espaciados

El refinamiento de la primera acción será en forma de secuencia:

         Imprimir el vértice superior —>
              Imprimir N-1 blancos
              Imprimir un asterisco
              Saltar a la línea siguiente

La acción de imprimir los blancos será una iteración, que podemos escribir directamente mediante un bucle con contador:

          Imprimir N-1 blancos —>
               FOR k := 1 TO N-1 DO
                  Write( ‘ ‘ )
               END

Las acciones de imprimir un asterisco y saltar a la línea siguiente se escriben inmediatamente:

         Imprimir un asterisco —>
              Write( ‘*’ )

         Saltar a la línea siguiente —>
              WriteLn

En el siguiente paso de refinamiento detallaremos la impresión de los bordes laterales. Intuitivamente podemos establecer una estructura de iteración mediante un bucle con contador:

         Imprimir los bordes laterales —>
              FOR k := 2 TO N-1 DO
                 Imprimir los bordes de la línea k
              END

Observaremos que la línea k-esima va precedida de N-k blancos, y tiene 2k-3 blancos entre los bordes:

          Imprimir los bordes de la línea k —>
                  Imprimir N-k blancos
                  Imprimir un asterisco
                  Imprimir 2k-3 blancos
                  Imprimir un asterisco
                  Saltar a la línea siguiente

Todas estas acciones han sido ya refinadas en sentencias de Modula-2. Finalmente falta por plantear la impresión del borde inferior. Podremos distinguir la impresión del primer asterisco y la del resto, y escribir:

           Imprimir el borde inferior —>
                 Imprimir un asterisco
                 Imprimir N-1 asteriscos precedidos de blanco
                 Saltar a la línea siguiente

La acción central se escribirá como un bucle con contador:

          Imprimir N-1 asteriscos precedidos de blanco —>
                FOR k := 1 TO N-1 DO
                   Write( ‘ ‘ ); Write( ‘*’ )
                END

Reuniendo todos los fragmentos, añadiendo la parte declarativa necesaria, y documentando cada elemento importante del programa, tendremos el programa completo, tal como se recoge en el listado que se muestra a continuación.

Este programa puede compilarse y ejecutarse, obteniendo el resultado puesto anteriormente como ejemplo. Sin embargo no puede considerarse totalmente terminado. Una deficiencia es que la altura del triángulo aparece como constante, cuando en realidad sería más razonable leerla como dato en cada ejecución del programa. La solución será definir N como variable y leer su valor al comienzo.

Otra deficiencia es que no se tienen en cuenta algunos casos especiales, en que el triángulo degenera y no tiene todos los elementos identificados. Esto ocurre cuando la altura del triángulo es 0, 1 ó 2. En el primer caso se omiten todas las líneas; en el segundo sólo existe el vértice superior, y en el tercero no existen bordes laterales.

(******************************************************************
*
*    Programa: Triángulo (Versión inicial)
*
*    Descripción:
*      Este programa imprime el borde de un triángulo
*      aproximadamente equilátero, usando asteriscos.
*
******************************************************************)
MODULE Triangulo;

(*=================================================================
    IMPORTACIÓN Y DECLARACIONES DEL PROGRAMA
=================================================================*)
  FROM InOut IMPORT Write, WriteLn;

(*=================================================================
    PARÁMETROS GENERALES   
=================================================================*)
  CONST N = 7;        (* altura del triángulo *)
  VAR j, K: INTEGER;    (* contadores *)

BEGIN

(*=================================================================
    PARTE EJECUTABLE LE PROGRAMA
=================================================================*)
  (*– Imprimir el vértice superior –*)
    FOR K := 1 TO N-1 DO
      Write( ‘ ‘ )
    END;
    Write( ‘*’ );
    WriteLn;

  (*– Imprimir los bordes laterales –*)
    FOR K := 2 TO N-1 DO
      FOR j := 1 TO N-K DO
        Write( ‘ ‘ )
      END;
      Write( ‘*’ );
      FOR j := 1 TO 2*K-3 DO
        Write( ‘ ‘ )
      END;
      Write( ‘*’ );
      WriteLn
    END;

  (*– Imprimir el borde inferior –*)
    Write( ‘*’ );
    FOR K := 1 TO N-1 DO
      Write( ‘ ‘ ); Write( ‘*’ )
    END;
    WriteLn
END Triangulo.

En esta versión inicial, para la altura igual a 2 no se obtienen resultados erróneos, ya que el bucle de líneas de los bordes laterales tal como está escrito se ejecutaría 0 veces (pero esto se debe más a la casualidad que a un razonamiento previo del comportamiento del programa). Por ejemplo, si cambiásemos el parámetro de altura al valor 1:

              CONST N = 1;

obtendríamos el resultado erróneo:

*
*

este mismo resultado se obtiene para N = 0. La solución general será convertir en esquema condicional la impresión del vértice superior y del borde inferior:

           Imprimir el vértice superior —>
                IF N>0 THEN
                     Imprimir N-1 blancos
                     Imprimir un asterisco
                     Saltar a la línea siguiente

                END

            Imprimir el borde inferior —>
                IF N>1 THEN
                     Imprimir un asterisco
                     Imprimir N-1 asteriscos precedidos de blanco
      
          END

La versión corregida del programa aparece en el siguiente listado:

(***********************************************************************
*
*    Programa: Triangulo (Versión corregia)
*
*    Descripción:
*      Este programa imprime el borde de un triángulo
*      aproximadamente equilátero, usando asteriscos.
*      La altura del triángulo, en líneas de texto, se lee como dato.
*
***********************************************************************)
MODULE Triangulo;

(*======================================================================
    IMPORTACIÓN Y DECLARACIONES DEL PROGRAMA
======================================================================*)
  FROM InOut IMPORT Write, WriteLn, WriteString, ReadInt;

  VAR N: INTEGER;        (* altura del triángulo *)
  VAR j, k: INTEGER;        (* contadores *)

BEGIN

(*======================================================================
    PARTE EJECUTABLE DEL PROGRAMA
======================================================================*)
  (*– Leer la altura deseada –*)
    WriteString( "Altura: " );
    ReadInt( N );
    WriteLn;

  (*– Imprimir el vértice superior –*)
    IF N>0 THEN
      FOR k := 1 TO N-1 DO
        Write( ‘ ‘ )
      END;
      Write( ‘*’ );
      WriteLn
    END;

  (*– Imprimir los bordes laterales –*)
    FOR k := 2 TO N-1 DO
      FOR j:= 1 TO N-k DO
        Write( ‘ ‘ )
      END;
      Write( ‘*’ );
      FOR j := 1 TO 2*k-3 DO
        Write( ‘ ‘ )
      END;
      Write( ‘*’ );
      WriteLn
    END;

  (*– Imprimir el borde inferior –*)
    IF N>1 THEN
      Write( ‘*’ );
      FOR k := 1 TO N-1 DO
        Write( ‘ ‘ ); Write( ‘*’ )
      END;
      WriteLn
    END
END Triangulo.
   

Algunos ejemplos de ejecución serian los siguientes:

Altura: 7
      *
     * *
    *   *
   *     *
  *       *
 *         *
* * * * * * *

Altura: 1
*

6.2.2 Ejemplo: Imprimir el triángulo de Floyd
Se trata de desarrollar un programa que imprima el llamado triángulo de Floyd. Este "triángulo" se forma imprimiendo los sucesivos números naturales 1, 2, 3, … en filas sucesivas, colocando 1 número en la primera línea, 2 en la segunda, 3 en la tercera, etc. Si fijamos un límite arbitrario de la serie de números (p. ej. 12), tendremos el triángulo

              1
              2     3
              4     5     6
              7     8     9     10
              11   12

Es fácil darse cuenta de que en general la línea k tiene k números, excepto la última línea, que puede quedar incompleta. El programa de este ejemplo deberá leer como dato el límite de la serie.

El primer paso de refinamiento será:

            Imprimir el triángulo de Floyd —>
                     Leer el límite N de la serie
                     Imprimir el triángulo hasta N

La primera acción puede desarrollarse en sentencias de Modula-2 en forma inmediata:

           Leer el límite N de la serie —>
                     WriteString( "Límite de la serie: ");
                     ReadInt( N );
                     WriteLn;

La parte principal del programa es la impresión del triángulo. Habremos de refinarla en forma de un esquema de secuencia, alternativa o iteración. Puesto que se trata de imprimir un número variable de líneas y valores, con acciones similares para todos ellos, parece razonable usar un esquema de iteración. La decisión a tomar será si plantear la iteración como un bucle de números o de líneas. Según la elección que hagamos tendremos esquemas de programa diferentes, que desarrollaremos por separado.

6.2.2.1 Escritura mediante bucle de números
Elegiremos en primer lugar esta posibilidad, que facilita la codificación del bucle, ya que puede plantearse como un bucle con contador:

               Imprimir el triángulo hasta N —>
                    FOR k := 1 TO N DO
                        imprimir el número k
                    END

La impresión del número requiere acciones adicionales, ya que debe incluir el saltar de línea al comienzo de cada nueva línea del triángulo. Puede plantearse como secuencia de acciones, en la forma:

                imprimir el número k —>
                      saltar de línea, si es necesario
                      WriteInt( k, 5 );

En este planteamiento los saltos de línea no se producen en cuanto se llega al final de la línea, sino cuando se va a escribir el siguiente valor. Esto quiere decir que el último número impreso dentro del bucle no irá seguido de salto de línea, y que habrá que completar la última línea como acción de terminación, fuera del bucle; es decir, la escritura del triángulo terminará con una acción adicional:

                 Completar la última línea

Refinaremos la acción de saltar de línea en forma de esquema condicional:

                  saltar de línea, si es necesario —>
                      IF el número anterior fue el último de su línea THEN
                         WriteLn
                      END

El refinamiento de la condición va a exigir introducir nuevos elementos. Para expresar dicha condición como una expresión en Modula-2 necesitaremos mantener actualizada la indicación de cuál es el último valor de cada línea. En todo caso necesitaremos conocer cuántos números han de imprimirse en la línea en curso (recordemos que en la línea k habrá k números).

Usaremos una variable linea como contador de líneas, y otra variable ultimo para contener el último número de la línea. Estas variables habrán de actualizarse cada vez que se cambie de línea. Reescribiremos el refinamiento anterior en la forma:

                  saltar de línea, si es necesario —>
                      IF k>ultimo THEN
                         WriteLn;
                          linea := linea+1;
                          ultimo := ultimo + linea
                      END

Al mismo tiempo hay que ampliar la inicialización del bucle de escribir números incluyendo dar valores iniciales a las nuevas variables, en concreto:

                   linea := 1;
                   ultimo := 1;

Esta inicialización es la adecuada incluso en el caso de escribir 0 números, ya que los valores corresponden al primer número que completa línea, y tras el cual habrá que saltar de línea si se imprimen más números.

No hay que olvidar desarrollar la acción de saltar de línea al final de la última línea del triángulo. Esta acción será condicional si hemos de considerar el caso de que se manden escribir 0 números, en cuyo caso no existe esa última línea.

                  Completar la última línea —>
                     IF N>0 THEN WriteLn END

Con todo ello podemos ya redactar el programa Floyd1 completo, tal como aparece a continuación, documentándolo en la forma habitual.

(**********************************************************************************************
*
*    Programa: Floyd1
*
*    Descripción:
*      Este programa imprime el triángulo de Floyd con los
*      números correlativos de 1 a N.
*      El valor de N se lee como dato.
*
**********************************************************************************************)
MODULE Floyd1;

(*=============================================================================================
    IMPORTACIÓN Y DECLARACIONES DEL PROGRAMA
=============================================================================================*)
  FROM InOut IMPORT WriteLn, WriteString, ReadInt, WriteInt;
  VAR
    N: INTEGER;            (* último número a imprimir *)
    k: INTEGER;            (* contador de números *)
    linea: INTEGER;        (* contador de líneas *)
    ultimo: INTEGER;        (* último número de la línea *)

BEGIN

(*=============================================================================================
    PARTE EJECUTABLE DEL PROGRAMA
=============================================================================================*)
  (*– leer el límite de la serie –*)
    WriteString( "Límite de la serie: " );
    ReadInt( N );
    WriteLn;

  (*– imprimir el triángulo mediante un bucle de número –*)
    linea := 1;
    ultimo := 1;
    FOR k := 1 TO N DO
      (*– imprimir el número k –*)
         (*– saltar de línea, si es necesario –*)
       IF k>ultimo THEN
         WriteLn;
         linea := linea + 1;
         ultimo := ultimo + linea
       END;
        WriteInt( k,5 )            (* imprimir el número *)
    END;
    IF N>0 THEN WriteLn END        (* acabar última línea *)
END Floyd1.

Un ejemplo de la ejecución del programa sería la siguiente:

Límite de la serie: 12
    1
    2    3
    4    5    6
    7    8    9   10
   11   12

Anuncios

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