Algoritmos: ejemplos resueltos y pruebas de ejecución
Practica con tres ejemplos de algoritmos: máximo de una lista, búsqueda lineal y máximo común divisor. Sigue entradas, pasos y resultados.
En pocas palabras
- Cada ejemplo necesita un contrato que defina entradas y salida.
- El estado de la ejecución permite localizar errores de pasos y actualización.
- Probar casos y justificar una propiedad general cumplen funciones complementarias.
En este artículo
Los ejemplos de algoritmos deben permitir seguir entradas, pasos y resultado, además de explicar por qué funciona el procedimiento. Una secuencia de instrucciones se comprende mejor al ejecutarla con datos concretos y revisar casos que podrían hacerla fallar. Aquí se desarrollan máximo de una lista, búsqueda lineal y máximo común divisor.
El NIST define algoritmo mediante pasos computables orientados a un resultado. Para practicar, escriba primero el contrato: qué entradas se aceptan y qué salida se espera. Cambiar el contrato puede exigir modificar la solución, aunque el ejemplo inicial siga funcionando.
Ejemplo 1: mayor valor de una lista
| Etapa | Valor examinado | Mayor guardado |
|---|---|---|
| Inicio | 4 | 4 |
| Comparación 1 | −2 | 4 |
| Comparación 2 | 9 | 9 |
- Etapa
- Inicio
- Valor examinado
- 4
- Mayor guardado
- 4
- Etapa
- Comparación 1
- Valor examinado
- −2
- Mayor guardado
- 4
- Etapa
- Comparación 2
- Valor examinado
- 9
- Mayor guardado
- 9
Después de cada comparación, el valor guardado es el mayor de la parte ya recorrida. Al terminar, se examinó toda la lista. Inicializar con cero sería incorrecto para una lista formada solo por negativos. La entrada vacía requiere una decisión adicional y no pertenece al contrato de este ejemplo.
Ejemplo 2: búsqueda lineal
La búsqueda lineal recorre elementos hasta encontrar el objetivo o agotar la lista. Usaremos posiciones que comienzan en cero. Para [7, 12, 5] y objetivo 5, la posición esperada es 2. La clase de algoritmos de CS50 permite estudiar búsquedas y sus costos.
Pasos de la búsqueda
- Comience en la posición cero.
- Mientras quede una posición válida, compare el elemento con el objetivo.
- Si coincide, devuelva la posición y termine.
- Si no coincide, avance una posición.
- Si se agota la lista, devuelva una señal explícita de no encontrado.
| Posición | Elemento | Decisión |
|---|---|---|
| 0 | 7 | No coincide; avanzar |
| 1 | 12 | No coincide; avanzar |
| 2 | 5 | Coincide; devolver 2 |
- Posición
- 0
- Elemento
- 7
- Decisión
- No coincide; avanzar
- Posición
- 1
- Elemento
- 12
- Decisión
- No coincide; avanzar
- Posición
- 2
- Elemento
- 5
- Decisión
- Coincide; devolver 2
En este caso hay tres comparaciones. Con objetivo 7, basta la primera; con objetivo 8, se recorren los tres y se informa ausencia. Defina también qué hacer con repeticiones: este procedimiento devuelve la primera coincidencia. Buscar todas exige continuar y almacenar o comunicar más posiciones.
Ejemplo 3: máximo común divisor
El algoritmo de Euclides calcula el máximo común divisor mediante restos sucesivos. Para enteros positivos a y b, reemplaza el par por b y el resto de dividir a entre b, hasta que el segundo valor sea cero. El último primer valor es el resultado. La explicación de Cornell fundamenta la conservación del divisor común.
| a | b | Resto de a entre b | Nuevo par |
|---|---|---|---|
| 48 | 18 | 12 | 18 y 12 |
| 18 | 12 | 6 | 12 y 6 |
| 12 | 6 | 0 | 6 y 0 |
- a
- 48
- b
- 18
- Resto de a entre b
- 12
- Nuevo par
- 18 y 12
- a
- 18
- b
- 12
- Resto de a entre b
- 6
- Nuevo par
- 12 y 6
- a
- 12
- b
- 6
- Resto de a entre b
- 0
- Nuevo par
- 6 y 0
El resultado es 6. Cada par conserva los divisores comunes pertinentes, mientras el segundo componente disminuye hasta cero. La operación de resto es esencial: sustituirla por una división ordinaria cambia el algoritmo. El ejemplo utiliza enteros positivos; otras entradas necesitan reglas explícitas sobre signo y el caso de ambos ceros.
Qué enseñan los tres ejemplos
| Ejemplo | Qué debe conservarse | Error frecuente |
|---|---|---|
| Máximo | Mayor de lo ya examinado | Inicialización incompatible con valores negativos |
| Búsqueda | No omitir posiciones antes de declarar ausencia | Confundir posición con número de comparaciones |
| Euclides | Divisores comunes del par | Usar cociente donde se necesita resto |
- Ejemplo
- Máximo
- Qué debe conservarse
- Mayor de lo ya examinado
- Error frecuente
- Inicialización incompatible con valores negativos
- Ejemplo
- Búsqueda
- Qué debe conservarse
- No omitir posiciones antes de declarar ausencia
- Error frecuente
- Confundir posición con número de comparaciones
- Ejemplo
- Euclides
- Qué debe conservarse
- Divisores comunes del par
- Error frecuente
- Usar cociente donde se necesita resto
Las pruebas con ejemplos ayudan a encontrar fallos; la explicación de una propiedad general aporta una justificación más amplia. También debe distinguirse resultado correcto de eficiencia. Máximo y búsqueda lineal recorren hasta una cantidad proporcional al tamaño de la lista, pero realizan tareas diferentes y no son intercambiables.
Cómo continuar la práctica
Ejercicios de variación
- Pruebe el máximo con un solo elemento y con todos los valores negativos.
- Busque un objetivo repetido y defina qué posición debe devolver.
- Realice Euclides con 18 y 48 para observar cómo se reorganiza el par.
- Describa una entrada fuera del contrato y una respuesta adecuada.
Consulte qué es la programación para pasar a implementación y diagrama de flujo en programación para representar decisiones. El artículo de Dijkstra ofrece un problema de grafos cuando estas bases ya resultan claras.
Referencias
- NIST. Dictionary of Algorithms and Data Structures. Algorithm. https://xlinux.nist.gov/dads/HTML/algorithm.html
- HARVARD UNIVERSITY. CS50x. Lecture 3: Algorithms. https://cs50.harvard.edu/x/notes/3/
- CORNELL UNIVERSITY. Euclid’s algorithm for computing GCD. https://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec11-gcd.html
Autoría
Study Mais
Sigue estudiando
Diagrama de flujo en programación: ciclo y ejemplo
Construye e interpreta un diagrama de flujo en programación con condición, actualización y salida. Incluye un ciclo de suma y su prueba de mesa.
Bases de datos: ejemplos y modelos para cada problema
Compara ejemplos de bases de datos relacionales, documentales, clave-valor y de grafos mediante reservas, catálogos, caché y prerrequisitos.
Qué es la programación: proceso y ejemplo práctico
Entiende qué es programar, la diferencia entre algoritmo y programa y cómo convertir una necesidad en una solución comprobable con un ejemplo.