31 octubre 2016

El problema de Josephus

Problema de Josephus o Flavio Josefo

El problema de Flavio Josefo es un problema teórico que se encuentra en matemática y ciencias de la computación. El nombre hace referencia a Flavio Josefo, un historiador judío que vivió en el siglo I. Según lo que cuenta Josefo, él y 40 soldados camaradas se encontraban atrapados en una cueva, rodeados de romanos. Prefirieron suicidarse antes que ser capturados y decidieron que echarían a suertes quién mataba a quién. Los últimos que quedaron fueron él y otro hombre. Entonces convenció al otro hombre que debían entregarse a los romanos en lugar de matarse entre ellos. Josefo atribuyó su supervivencia a la suerte o a la Providencia. 

El planteamiento general del problema, presupone cualquier número de soldados, n,  y un valor k que indica el salto en cada "asesinato". Por ejemplo, si empieza en el número 1 y k = 3, el primero en desaparecer sería el número 4.

Es un claśico problema que se resuelve en los estudios de Programación en cualquier lenguaje.

La forma general de atacar el problema consiste en saber dónde debe colocarse Josephus para salvarse (caso general, que dependerá del número n de soldados, del valor de k,  del inicio del proceso y de la posición de Josephus).

Si n = 41, k = 3, el resultado final nos dice que Josephus debería ponerse en posicion 31, como puede verse en el siguiente gráfico:

Hy varias versiones  (barca con personas de diferentes religiones...). El juego es bueno para programación y tiene un alto interés y aplicabilidad en el aula

Si quieres ver una simulación interactiva con geogebra,  en la que puedes modificar n y k, visita la siguiente web (de la que he tomado la imagen anterior)

Simulación del problema de Josephus.

Aquí puedes ver otra simulación: visita este enlace.

No hay comentarios: