El problema de Josefo en Haskell
El problema de Josefo hace referencia a Flavio Josefo, un historiador judío que vivió en el siglo I. Según lo que cuenta Josefo, él y cuarenta soldados camaradas fueron capturados por los romanos. Antes que rendirse, decidieron acabar ellos mismos con sus vidas. Para hacerlo, se dispusieron en un círculo y acordaron que irían contando de tres en tres, de forma que cada tercer soldado sería ejecutado por la persona de su izquierda. El último hombre que quedara con vida tendría que suicidarse. Según cuenta la leyenda, Josefo calculó rápidamente cuál sería la posición del último hombre en morir para colocarse allí, y una vez hubieron muerto sus compatriotas, se entregó a los romanos.
El enunciado del problema de Josefo de orden (n,m) es el siguiente: Se tienen n personas entorno a un círculo, ordenadas y numeradas desde la primera a la n-ésima. Empezando por la persona número 1, se saltan m-1 personas y se mata a la m-ésima. A continuación se saltan otras m-1 personas y se ejecuta a la siguiente. El proceso continúa hasta que sólo quede una. El objetivo es, dados n y m, encontrar el lugar inicial en el círculo para sobrevivir.
A continuación muestro una relación de ejercicios (elaborada para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) en la que se presentan distintas soluciones y se compara su eficiencia.