Especificar un problema: entrada, salida y pasos
Antes de escribir código, describe el problema con exactitud. Eso es la especificación.
- Entrada: qué datos recibimos, de qué tipo y con qué límites (por ejemplo, "n números enteros, 1 ≤ n ≤ 1000").
- Salida: qué debemos devolver (por ejemplo, "el mayor de ellos").
- Condiciones: qué es cierto antes (precondición) y después (postcondición).
Escribir los pasos
Un algoritmo es una lista finita de pasos claros que convierte cualquier entrada válida en la salida correcta. Se puede escribir como:
- lenguaje natural: "Mira cada número; si es mayor que el mejor hasta ahora, recuérdalo."
- una lista numerada de pasos: 1. mejor ← primer número. 2. Para cada número siguiente x: si x > mejor, entonces mejor ← x. 3. Dar como salida mejor.
- pseudocódigo o diagrama de flujo, si quieres más precisión.
Pruébalo a mano con entradas pequeñas, incluidas las difíciles (todos iguales, números negativos, un solo número).
Diseño descendente y ascendente
Descendente (top-down, refinamiento por pasos): empieza con la tarea completa, divídela en unos pocos pasos grandes y vuelve a dividir cada paso hasta que cada parte sea fácil de programar. Ejemplo: "Hacer un boletín de notas" → leer las notas → calcular los promedios → asignar las calificaciones → imprimir.
Ascendente (bottom-up): construye y prueba primero piezas pequeñas y reutilizables (una función que halla el máximo, otra que ordena) y luego únelas en el programa completo.
Los proyectos reales mezclan ambos: se planifica de arriba abajo y se construye y prueba de abajo arriba.
Divide y vencerás, y el método de la mitad
Divide y vencerás tiene tres movimientos: dividir el problema en partes más pequeñas del mismo tipo, resolver cada parte (muchas veces con recursión) y combinar las respuestas.
- Búsqueda binaria (mitad): en una lista ordenada, compara con el elemento del medio y descarta la mitad. n elementos necesitan unas log₂ n comprobaciones: 16 → 4, 1 000 000 → 20.
- Ordenación por mezcla (merge sort): divide la lista en dos, ordena cada mitad y mézclalas: O(n log n).
- Potencia rápida: a⁸ = ((a²)²)²: 3 multiplicaciones en lugar de 7.
- Hallar una raíz por bisección: parte por la mitad un intervalo en el que la función cambia de signo.
Algoritmos voraces
Un algoritmo voraz (greedy) toma la decisión que parece mejor en este momento y nunca la cambia.
- Dar el cambio con 50, 20, 10, 5, 2, 1: primero la moneda más grande. Es óptimo para este tipo de sistema de monedas.
- Elegir el mayor número de actividades en un día: escoge siempre la que termina antes. Es óptimo.
- Mochila fraccionaria: toma primero los objetos con mejor valor por kg. Es óptimo.
Pero el método voraz no siempre acierta: con monedas 1, 3, 4, pagar 6 de forma voraz da 4 + 1 + 1 (3 monedas), mientras que 3 + 3 usa 2. Para fiarte de un método voraz debes demostrarlo o compararlo con un método seguro.
Programación dinámica y vuelta atrás
Programación dinámica (PD)
Cuando los mismos problemas pequeños se repiten, resuelve cada uno una sola vez y guarda la respuesta en una tabla. Mínimo de monedas para la cantidad a: mejor[a] = 1 + min(mejor[a - c]) sobre las monedas c ≤ a, empezando con mejor[0] = 0. Para monedas 1, 3, 4: mejor = 0, 1, 2, 1, 1, 2, 2. Llenar la tabla de pequeño a grande es ascendente (bottom-up); la recursión con memoria es descendente (memoización). Mira la lección aparte de Programación dinámica para saber más.
Vuelta atrás (backtracking)
Construye una solución tomando una decisión cada vez. Si una decisión rompe una regla o lleva a un callejón sin salida, deshazla y prueba la siguiente opción. Se usa en laberintos, sudokus, el problema de las N reinas y para listar todos los subconjuntos. Es una fuerza bruta con cuidado: se salta ramas enteras que no pueden funcionar.
Fuerza bruta
Probar todas las respuestas posibles. Siempre es correcta, pero muchas veces es demasiado lenta (2ⁿ subconjuntos, n! órdenes).
Elegir una técnica: corrección, eficiencia y estructuras de datos
| Técnica | Se usa cuando | Ejemplo | Tiempo típico |
|---|---|---|---|
| Fuerza bruta | la entrada es diminuta | probar todas las claves de 3 dígitos | a menudo 2ⁿ o n! |
| Divide y vencerás | las partes son independientes | búsqueda binaria, ordenación por mezcla | O(log n), O(n log n) |
| Voraz | se ha demostrado que la mejor elección local es segura | selección de actividades, cambio | O(n log n) |
| Programación dinámica | los subproblemas se repiten | cambio de monedas, caminos más cortos | tamaño de la tabla |
| Vuelta atrás | búsqueda con reglas | laberinto, sudoku | exponencial, pero con podas |
Justifícalo
Corrección: demuestra que el algoritmo siempre termina y da la salida correcta (un invariante de bucle, una demostración o pruebas con casos extremos). Eficiencia: cuenta los pasos cuando n crece (notación O grande) y compáralo con otros métodos.
Las estructuras de datos ayudan
Arreglos para las tablas (PD), pilas para la vuelta atrás (recuerdan adónde volver), colas para buscar nivel por nivel. Un árbol binario guarda los elementos de modo que cada nodo tiene como mucho dos hijos; en un árbol binario de búsqueda las claves menores van a la izquierda y las mayores a la derecha, así que buscar reduce el trabajo a la mitad en cada nivel, igual que la búsqueda binaria.
Pruébalo: monedas y un juego de adivinar
- Juega con un amigo a adivinar un número del 1 al 100. Pregunta siempre por el del medio. ¿Puedes ganar siempre en 7 preguntas? (2⁷ = 128.)
- Con monedas 1, 3, 4, escribe en papel la tabla de PD para las cantidades de 0 a 10. ¿Dónde falla el método voraz?
- Abre el último paso 3D. Prueba monedas 1, 7, 10 y la cantidad 14. El voraz da 10 + 1 + 1 + 1 + 1; la PD da 7 + 7.
- Escribe una lista de pasos para "hallar el menor número de una lista" y pruébala con 5, 5, 5 y con un solo número.
Fórmulas y definiciones clave
- Especificación = entrada + salida + condiciones
- Mitad: unos log₂ n pasos (16 → 4, 1024 → 10)
- PD de monedas: mejor[0] = 0; mejor[a] = 1 + min mejor[a - c]
- Divide y vencerás = dividir + resolver + combinar
- El método voraz es rápido pero hay que demostrar que es óptimo
Ejemplos resueltos
1. Escribe una especificación y una lista de pasos para hallar el mayor de n números.
Entrada: n ≥ 1 números. Salida: el mayor. Pasos: 1. mejor ← primer número. 2. Para cada otro número x: si x > mejor, mejor ← x. 3. Dar como salida mejor. Para 4, 9, 2, 7, 12, 5, 10, 3 la salida es 12 después de 7 comparaciones.
2. ¿Cuántas preguntas necesita el método de la mitad para hallar un número del 1 al 1000?
Cada pregunta reduce el rango a la mitad: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Son 10 preguntas (2¹⁰ = 1024 ≥ 1000).
3. Paga 87 de forma voraz con monedas 50, 20, 10, 5, 2, 1.
50 (quedan 37), 20 (17), 10 (7), 5 (2), 2 (0): 50 + 20 + 10 + 5 + 2 = 5 monedas.
4. Llena la tabla de PD para monedas 1, 3, 4 hasta la cantidad 7.
mejor[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(mejor4, mejor2, mejor1)+1=2, [6]=min(mejor5, mejor3, mejor2)+1=2, [7]=min(mejor6, mejor4, mejor3)+1=2 (3 + 4).
5. Actividades (inicio-fin): A 9-11, B 10-12, C 11-13, D 12-14, E 13-15. Elige el mayor número de actividades que no se solapen.
Voraz por fin más temprano: A (termina a las 11), luego C (empieza a las 11, termina a las 13), luego E (empieza a las 13). 3 actividades: A, C, E.
6. Planifica de arriba abajo un programa que diga a una clase su nota media y quién es el mejor alumno.
Nivel 1: leer datos → calcular → imprimir. Nivel 2: leer nombres y notas en listas; calcular el total y la media; hallar la nota máxima y su nombre; imprimir ambos. Después cada pieza se programa y se prueba de abajo arriba.
Errores comunes
- Empezar a programar sin decir cuál es la entrada y la salida. Muchos "errores" son en realidad una especificación poco clara.
- Creer que el método voraz siempre es óptimo. Solo funciona cuando lo puedes demostrar (las monedas 1, 3, 4 lo rompen).
- Usar búsqueda binaria en una lista sin ordenar. Partir por la mitad necesita datos ordenados.
- Confundir la PD con divide y vencerás. La PD sirve para subproblemas que se solapan y se guardan; divide y vencerás divide en partes independientes.