Problemas clásicos de programación
Hay problemas que aparecen en todos los libros, exámenes y entrevistas técnicas porque cada uno enseña una idea que luego sirve en muchos otros: la mochila enseña programación dinámica; las torres de Hanói, a confiar en la recursividad; las permutaciones, a generar todas las combinaciones con backtracking.
Cada ficha plantea el problema con un ejemplo concreto, prueba primero la solución ingenua para ver por qué no basta y llega a la buena paso a paso, con una tabla o un árbol de llamadas que puedes seguir con el dedo.
Código en Java, Python, JavaScript, C# y PHP.
Los algoritmos
Problema de la mochila (0/1)
Elegir qué objetos meter en una mochila con un peso máximo para que su valor sea el mayor posible. Probarlo todo es exponencial; la programación dinámica lo resuelve con una tabla.nivel avanzado2 ejerciciosDistancia de edición (Levenshtein)
El mínimo de letras que hay que sustituir, borrar o insertar para convertir una palabra en otra. Se calcula con una tabla de prefijos y es la base de los correctores y del diff.nivel avanzado2 ejerciciosTorres de Hanói
Mover una torre de discos de un poste a otro sin poner nunca uno grande sobre uno pequeño. El ejemplo perfecto de recursividad: tres líneas lo resuelven en 2ⁿ − 1 movimientos.nivel intermedio2 ejerciciosPermutaciones (backtracking)
Generar todas las ordenaciones de unos elementos eligiendo uno de los libres en cada posición y deshaciendo la elección al volver. Hay n! y el backtracking las recorre sin repetir ninguna.nivel intermedio2 ejerciciosSubarray de suma máxima (Kadane)
Encontrar el tramo de un array cuya suma es la mayor. Kadane lo hace en una sola pasada decidiendo en cada posición si seguir con el tramo o empezar uno nuevo.nivel intermedio2 ejercicios