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. Existen cuatro etapas.

Análisis

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

• abstracción 抽象 — conservar 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, utilizando a menudo la descomposición. Se pueden mostrar las partes como sub-sistemas 子系统 en un diagrama de estructura 结构图 (un gráfico que divide un sistema en cajas más pequeñas).

Codificación y pruebas

En la codificación se escribe el código del programa. Se utiliza la 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 entran;
• procesamiento 处理 — el trabajo realizado sobre los datos;
• salida 输出 — el resultado que sale.

Esto se llama descomposición en entradas, procesos y salidas. Por ejemplo, para "encontrar el promedio de tres notas": las entradas son las tres notas; el procesamiento es 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 lógicos y sigan las reglas. No puede verificar que los datos sean verdaderos, solo que estén permitidos.

La verificación 核实 verifica que los datos fueron copiados o ingresados correctamente (sin errores mientras se tecleaban). Dos métodos:

• verificación visual 目视检查 — una persona compara los datos tecleados con el original;
• doble entrada 双重输入 — los datos se ingresan dos veces y se comparan las dos copias.

Una tabla de trazado 追踪表 registra el valor de cada variable a medida que un algoritmo se ejecuta, 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.

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

Debe conocer estos algoritmos comunes.

Búsqueda lineal

Una búsqueda lineal 线性查找 revisa cada elemento de una lista, uno por uno, hasta que encuentra el valor deseado o llega al final.

Found ← FALSE
FOR I ← 0 TO 9
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
NEXT I
OUTPUT Found

Ordenamiento burbuja

Un ordenamiento burbuja 冒泡排序 coloca una lista en orden. Compara cada par de elementos adyacentes y los intercambia si están en el orden incorrecto. Repite esto hasta que no se necesiten más intercambios.

FOR I ← 0 TO 8
    IF List[I] > List[I + 1]
      THEN
        Temp ← List[I]
        List[I] ← List[I + 1]
        List[I + 1] ← Temp
    ENDIF
NEXT I

Sumatoria y conteo

• sumatoria 求和 — seguir sumando valores a un total acumulado (Total ← Total + Value).
• conteo 计数 — sumar 1 a un contador cada vez que ocurre algo (Count ← Count + 1).

Máximo, mínimo y promedio

• para encontrar el máximo 最大值: guardar el valor más grande visto hasta ahora.
• para encontrar el mínimo 最小值: guardar el valor más pequeño visto hasta ahora.
• para encontrar el promedio 平均值: dividir el total por cuántos valores hay.

Total ← 0
FOR I ← 0 TO 9
    Total ← Total + List[I]
NEXT I
Average ← Total / 10
OUTPUT Average

• Aprenda las cuatro etapas del ciclo de vida: análisis → diseño → codificación → pruebas. La abstracción conserva solo los detalles importantes; la descomposición divide un problema en partes más pequeñas.
• 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 más grande/más pequeño aún permitido), límite/borde (los valores a ambos lados de un límite).
• Para averiguar qué hace un algoritmo, complete una tabla de trazado — anote el valor de cada variable en cada paso.
• 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).