Diseño de algoritmos y resolución de problemas

El ciclo de vida del desarrollo de programas es el conjunto de etapas utilizadas para crear un programa. Hay cuatro etapas.

Análisis

En el análisis se comprende el problema. Dos habilidades clave ayudan:

• abstracción — mantener solo los detalles importantes e ignorar el resto;
• descomposición — dividir un problema grande en partes más pequeñas y fáciles.

Diseño

En el diseño se planifica la solución, a menudo utilizando descomposición. Se pueden representar las partes como sub-sistemas en un diagrama de estructura (un gráfico que divide un sistema en cajas más pequeñas).

Ejemplo resuelto. Un estacionamiento tiene una máquina de pago. El conductor introduce la matrícula del automóvil, la máquina calcula cuánto tiempo ha permanecido estacionado y el importe, el conductor paga en efectivo o con tarjeta y se imprime un recibo. Dibuja un diagrama de estructura.

El sistema completo va en el cuadro superior. Cada cuadro del siguiente nivel representa una tarea que realiza el sistema, y un cuadro puede volver a dividirse (el pago se divide en efectivo y tarjeta). Lee cada nivel de izquierda a derecha, en el orden en que ocurren las tareas. Un diagrama de estructura muestra las partes, no el orden de las decisiones ni de los bucles: para eso se utiliza un diagrama de flujo o pseudocódigo.

Codificación y pruebas

En la codificación se escribe el código del programa. Se utiliza prueba iterativa — probar pequeñas partes repetidamente a medida que se construyen. En las pruebas se ejecuta todo el programa con datos de prueba para verificar que funcione.

Se puede planificar una solución de tres formas principales.

• un diagrama de estructura — muestra las partes de un sistema y cómo se integran;
• un diagrama de flujo — un diagrama que usa cajas y flechas para mostrar los pasos en orden;
• pseudocódigo — pasos escritos en inglés simple similar al código (no un lenguaje real).

Un algoritmo es un conjunto de pasos, en el orden correcto, que resuelve un problema. Todo algoritmo se puede dividir en tres partes:

• entrada — los datos que se introducen;
• procesamiento — el trabajo realizado sobre los datos;
• salida — el resultado que se obtiene.

Esto se llama descomposición en entradas, procesos y salidas. Por ejemplo, para «hallar el promedio de tres calificaciones»: las entradas son las tres calificaciones; el procesamiento consiste en sumarlas y dividirlas entre 3; la salida es el promedio.

Cuando se ingresan datos, se verifican para reducir errores.

La validación verifica que los datos sean razonables y sigan las reglas. No puede verificar si los datos son verdaderos, solo si están permitidos.

La verificación comprueba que los datos se han copiado o introducido correctamente (sin errores durante la escritura). Dos métodos:

• comprobación visual — una persona compara los datos escritos con el original;
• entrada doble — los datos se introducen dos veces y se comparan las dos copias.

Cómo escribir una rutina de validación

Un examen suele pedirte que escribas el código de una comprobación. Utiliza un bucle que vuelva a preguntar hasta que la entrada sea aceptable y muestra un mensaje al usuario cuando no lo sea.

Ejemplo resuelto. Escribe pseudocódigo para introducir la calificación de una prueba, que debe ser un número entero de 0 a 100 (una comprobación de rango), y para seguir preguntando hasta que se introduzca una calificación válida.

DECLARE Mark : INTEGER
REPEAT
    OUTPUT "Enter a mark from 0 to 100"
    INPUT Mark
    IF Mark < 0 OR Mark > 100
      THEN
        OUTPUT "Invalid: the mark must be from 0 to 100"
    ENDIF
UNTIL Mark >= 0 AND Mark <= 100

La condición UNTIL es el rango aceptado y la condición IF es su opuesto. Observa OR en IF: una calificación no puede ser inferior a 0 y superior a 100 al mismo tiempo, por lo que AND nunca sería verdadero allí.

Otras comprobaciones siguen el mismo patrón, con una condición diferente:

Por lo general, el propio lenguaje realiza una comprobación de tipo, por ejemplo, cuando una entrada se almacena en una variable INTEGER.

Una tabla de trazado registra el valor de cada variable a medida que se ejecuta un algoritmo, paso a paso. Ayuda a:

• verificar que un algoritmo funciona correctamente;
• averiguar qué hace un algoritmo siguiéndolo con datos dados.

Ejemplo: tracee este algoritmo con la entrada 5.

INPUT N
Total ← 0
FOR I ← 1 TO N
    Total ← Total + I
NEXT I
OUTPUT Total

El trazado muestra que el algoritmo suma del 1 a n. Con la entrada 5, la salida es 15.

Ejemplo resuelto. Tracee este algoritmo y dé la salida.

X ← 20
Count ← 0
WHILE X > 1
    X ← DIV(X, 2)
    Count ← Count + 1
ENDWHILE
OUTPUT Count

DIV devuelve solo la parte de número entero de una división. Tome una fila por pasada: x se convierte en 10 (count 1), luego 5 (count 2), luego 2 (count 3), luego 1 (count 4). Ahora x > 1 es falso, así que el bucle se detiene y la salida es 4. Dos hábitos protegen estas calificaciones: probar la condición antes de cada pasada en lugar de después, y escribir una nueva fila para cada pasada — intentar retener los valores en su cabeza es lo que hace que los trazados fallen.

Detección y corrección de errores

Una pregunta habitual presenta un algoritmo con errores y te pide que los encuentres y corrijas. Léelo línea por línea y pregúntate: ¿se asigna un valor inicial a cada variable? ¿Tiene cada bucle la longitud correcta? ¿Se realiza cada comparación en el sentido correcto? ¿Está la salida en el lugar adecuado?

Ejemplo resuelto. Este algoritmo debe introducir 10 números y mostrar el mayor. Encuentra los tres errores y corrígelos.

Largest ← 1000
FOR Count ← 1 TO 9
    INPUT Number
    IF Number < Largest
      THEN
        Largest ← Number
    ENDIF
    OUTPUT Largest
NEXT Count

• Línea 1: Largest ← 1000 comienza con un valor demasiado alto, por lo que ningún número lo reemplazaría. Corrección: Largest ← -1000 (o introduce el primer número y úsalo como valor inicial).
• Línea 2: el bucle solo se ejecuta 9 veces. Corrección: FOR Count ← 1 TO 10.
• Línea 4: < encuentra el menor. Corrección: IF Number > Largest.

También hay un problema con OUTPUT: dentro del bucle muestra el mayor hasta ese momento después de cada entrada. Si se mueve después de NEXT Count, solo se muestra la respuesta final. Para cada error, indica la línea, explica qué está mal y escribe la línea corregida completa.

Los datos de prueba 测试数据 son los datos que usa para probar un programa. Hay cuatro tipos que debe conocer.

Ejemplo resuelto. Un programa acepta el número de personas que reservan una mesa, de 1 a 12. Da datos de prueba de cada tipo, con el resultado esperado.

Indica siempre el resultado esperado junto con los datos: una prueba solo es útil si sabes qué debería ocurrir. Un dato extremo es el propio valor del límite; los datos límite son un par, con un valor a cada lado del límite.

Debe conocer estos algoritmos comunes.

Búsqueda lineal

Una búsqueda lineal compara cada elemento con el objetivo, comenzando desde el principio. Deténgase cuando se encuentre el valor o termine la lista. La lista no necesita estar ordenada. El siguiente ejemplo usa posiciones 1 a 4.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, SearchValue : INTEGER
DECLARE Found : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
INPUT SearchValue
Found ← FALSE
I ← 1
WHILE I <= 4 AND NOT Found
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
    I ← I + 1
ENDWHILE
OUTPUT Found

Comparación resuelta. Buscar 5 compara 8, 3 y luego 5: tres comparaciones, con Found convirtiéndose en TRUE. El cuarto elemento no se verifica. Buscar 9 compara los cuatro valores; Found permanece en FALSE. Deténgase antes de intentar leer la posición 5, que está fuera de este array.

Ordenamiento burbuja

Un ordenamiento burbuja coloca una lista en orden. Compare valores adyacentes e intercámbielos si el valor izquierdo es mayor. Un solo recorrido no suele ser suficiente. Esta versión completa repite recorridos hasta que uno entero no realiza ningún intercambio.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Temp : INTEGER
DECLARE Swapped : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
REPEAT
    Swapped ← FALSE
    FOR I ← 1 TO 3
        IF List[I] > List[I + 1]
          THEN
            Temp ← List[I]
            List[I] ← List[I + 1]
            List[I + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT I
UNTIL NOT Swapped
OUTPUT List[1], ", ", List[2], ", ", List[3], ", ", List[4]

Paso resuelto. Comienza con 8, 3, 5, 1. En el primer paso la lista se convierte en 3, 8, 5, 1, luego en 3, 5, 8, 1, después en 3, 5, 1, 8. Esto coloca el valor más grande al final pero deja el resto desordenado. El segundo paso termina en 3, 1, 5, 8; el tercero en 1, 3, 5, 8. El cuarto no realiza intercambios y confirma que esta versión puede detenerse. Restablece Swapped a FALSE al inicio de cada paso; ajústalo a TRUE en cualquier intercambio.

Sumatoria y conteo

Sumatoria suma cada valor requerido a un total acumulado: Total ← Total + Value. Conteo suma 1 por cada artículo requerido: Count ← Count + 1. Inicialice ambos a cero antes de procesar los valores.

Ejemplo resuelto. Cuatro intentos de entrada son −20, 4, 50 y 6. Acepte un valor solo si es mayor que −20 y menor que 50. Este ejemplo procesa cuatro intentos, no cuatro valores aceptados.

DECLARE I, Count : INTEGER
DECLARE Value, Total : REAL
Total ← 0
Count ← 0
FOR I ← 1 TO 4
    INPUT Value
    IF Value > -20 AND Value < 50
      THEN
        Total ← Total + Value
        Count ← Count + 1
    ENDIF
NEXT I
IF Count > 0
  THEN
    OUTPUT Total, ", ", Count, ", ", Total / Count
  ELSE
    OUTPUT "No accepted values"
ENDIF

Los límites estrictos rechazan −20 y 50. Ambas actualizaciones pertenecen dentro de la prueba de aceptación, por lo que los intentos rechazados no cambian ni el total ni el conteo. El promedio de los valores aceptados es:

No divida por cuatro: solo se agregaron dos valores. Si no se acepta ningún valor, el conteo es cero y no se puede calcular un promedio; emita un mensaje en lugar de dividir por cero.

Transferir a un número fijo de valores aceptados. Si una tarea solicita 50 valores aceptados, en lugar de cuatro intentos, reemplace el bucle fijo FOR por WHILE Count < 50 y ciérrelo con ENDWHILE. Mantenga la misma entrada y prueba de aceptación dentro del bucle. Las entradas rechazadas dejan Count sin cambios, por lo que se solicita otra entrada. Al completar, Count es 50, aunque el número de intentos puede ser mayor. Emita el total y calcule el promedio como Total / Count.

Máximo, mínimo y promedio

El máximo es el valor más grande y el mínimo es el más pequeño. El promedio es el total dividido por el número de valores. Para una lista no vacía, inicialice ambos desde su primer elemento. Para cada elemento restante, reemplace el máximo si el nuevo valor es mayor, y reemplace el mínimo si es menor.

Ejemplo resuelto. La lista es −8, −3, −12, −5. Iniciar el máximo en cero fallaría: ningún elemento de la lista es mayor que cero, por lo que el algoritmo emitiría un número que no está en la lista. Iniciar desde −8 funciona sin asumir que los datos son positivos.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Maximum, Minimum, Total : INTEGER
List[1] ← -8
List[2] ← -3
List[3] ← -12
List[4] ← -5
Maximum ← List[1]
Minimum ← List[1]
Total ← List[1]
FOR I ← 2 TO 4
    IF List[I] > Maximum
      THEN
        Maximum ← List[I]
    ENDIF
    IF List[I] < Minimum
      THEN
        Minimum ← List[I]
    ENDIF
    Total ← Total + List[I]
NEXT I
OUTPUT Maximum, ", ", Minimum, ", ", Total / 4

El máximo es −3 y el mínimo es −12. El promedio utiliza los cuatro valores:

El promedio se encuentra entre el mínimo y el máximo; esto es una comprobación útil, pero no prueba que el cálculo sea correcto. Inicializar desde el primer elemento requiere una lista no vacía. Maneje una lista vacía por separado antes de intentar leer ese elemento.

• Las cuatro etapas del ciclo de vida: análisis → diseño → codificación → prueba. Abstracción retiene solo lo importante; descomposición divide un problema en partes.
• La validación verifica que los datos sean lógicos (verificaciones de rango, longitud, tipo, presencia, formato); la verificación verifica que fueron copiados correctamente (una verificación visual o doble entrada).
• Aprenda los cuatro tipos de datos de prueba: normal (aceptado), anormal (rechazado), extremo (el valor más grande/más pequeño aún permitido), límite (ambos lados de un umbral).
• Una tabla de trazado (valor de cada variable en cada paso) muestra lo que hace un algoritmo.
• Para escribir una rutina de validación, coloca la entrada en un bucle REPEAT … UNTIL cuya condición UNTIL sean los datos válidos.
• Cuando corrijas un error, cita la línea y escribe la línea corregida completa.
• Conozca los algoritmos estándar: búsqueda lineal (revisar cada elemento por turno) y ordenamiento burbuja (intercambiar pares adyacentes hasta que no se necesiten más intercambios).