¿Cuál es la mejor solución para el algoritmo del problema Josephus?

Answer 1

El problema de Josephus [1] es un rompecabezas matemático clásico en el que hay [matemática] n [/ matemática] personas paradas en un círculo y un verdugo mata cada [matemática] k [/ matemática] La persona viva y esto continúa hasta que solo queda una persona en el círculo. El objetivo es encontrar la posición inicial de la última persona viva.

Por ejemplo, si [matemática] n = 5 yk = 2 [/ matemática]

El orden en que las personas son asesinadas es (los números indican el número de serie de la persona asesinada al principio)

[matemáticas] 2, 4, 1, 5 [/ matemáticas]

la persona que vive es [matemática] 3 [/ matemática] tercera persona.

Esto se puede resolver mediante recursividad y la solución recursiva se puede mejorar mediante la programación dinámica.

Aquí hay un enfoque de complejidad [matemática] O (n) [/ matemática] para [matemática] n [/ matemática] y [matemática] k> 2 [/ matemática]

Si [matemática] n = 2 [/ matemática] entonces hay otro enfoque que es de [matemática] O (logn) [/ matemática] complejidad.

---

El enfoque recursivo es el siguiente:

Suponga que [matemática] f (n, k) [/ matemática] es la solución al problema y que él es el tipo afortunado que finalmente vive.

tipo con suerte (a partir de la primera iteración) = tipo con suerte (a partir de la segunda iteración)

El tipo con suerte no cambia de iteración a iteración, pero su índice de ronda a ronda cambia.

Cambiemos el sistema de indexación de [matemática] [1 a n] [/ matemática] a [matemática] [0 a n-1] [/ matemática] para simplificar la programación y la comprensión.

ahora en la primera iteración [matemática] (k-1) la persona [/ matemática] es asesinada, el número restante de personas es [matemática] n-1. [/matemáticas]

Ahora, para la segunda iteración de matar, veamos el cambio en el sistema de indexación (primera iteración [matemática] N [/ matemática] personas vivas, segunda iteración [matemática] N-1 [/ matemática] personas vivas)

primera iteración —-> [matemáticas] 0, 1, 2, 3, …, k-1, k, k + 1, …, N-2, N-1 [/ matemáticas] ( k-1ª persona asesinada)

para la segunda iteración, la indexación comienza desde [math] k. [/ math]

La quinta persona en la primera iteración será la quinta persona en la segunda iteración.

[matemática] k + 1 [/ matemática] la primera iteración de la persona estará en la 1ª posición en la segunda iteración.

de manera similar, si [math] f (n-1, k) [/ math] es la solución y el índice del tipo afortunado en la segunda iteración, entonces su índice en la primera iteración sería [math] ((k + f (n-1, k))% N) [/ matemáticas]

(el resto se toma para limitar los índices por debajo de N)

[matemática] (a% b [/ matemática] es el resto obtenido cuando [matemática] a [/ matemática] se divide por [matemática] b [/ matemática]).

Así obtenemos la relación recursiva

[matemáticas] f (n, k) = (f (n-1, k) + k)% n [/ matemáticas]

esto da la solución en 0 sistema de indexación, para obtener respuesta en 1 sistema de indexación agregue 1 a la solución.

---

solución recursiva:

int JosephusHelper (int n, int k)
{
if (n == 1) devuelve 0; // si solo hay una persona, su índice es 0
return ((JosephusHelper (n-1, k) + k)% n);
}
int Josefo (int n, int k)
{
devuelve 1 + JosephusHelper (n, k); // agregando 1 para cambiar la indexación
}

Solución de programación dinámica:

int Josefo (int n, int k)
{
int resultado = 0; // para n = 1
para (int i = 2; i <= n; i ++)
{
resultado = (k + resultado)% i;
}
retorno (resultado + 1); // agregando 1 para cambiar la indexación;
}

Gracias 🙂

Sharath

Notas al pie

[1] Problema de Josefo – Wikipedia

Answer 2

Gracias por el A2A.

Habría abordado este problema de manera recursiva:

int josephus (int numberOfPrisoners, int kIndexPrisonerToBeKilled) {

if (numberOfPrisoners == 1)

retorno 1;

más

return (josephus (numberOfPrisoners – 1, kIndexPrisonerToBeKilled) + kIndexPrisonerToBeKilled-1)% numberOfPrisoners + 1;

}

Answer 3

Uno de los problemas interesantes que surgen del escenario Josephus involucra operaciones de rango.

1. Mata a una persona en el círculo.
2. Encuentre el número de personas vivas desde el índice izquierdo al índice derecho.

A continuación se muestra el video tutorial que hice para este problema.

Answer 4

Usaré [math] n [/ math] como el tamaño del grupo y [math] k [/ math] como el tamaño del paso.

Supongo que está buscando soluciones para un caso general y no para valores específicos de [math] k [/ math].

La solución más clásica se ejecuta en [math] O (n) [/ math] y es muy intuitiva. Si [math] n [/ math] es mucho más grande que [math] k [/ math], entonces también tiene una solución con complejidad [math] O (k * log (n)) [/ math] que usa una idea similar pero requiere un poco más de matemáticas. Estoy omitiendo los detalles de cada solución ya que ya están muy bien explicados en línea (por ejemplo: algo :: Задача Иосифа).

Para algunos valores específicos de [math] k [/ math] se pueden obtener mejores soluciones.

Answer 5

No sé si este es el mejor método, pero es relativamente bueno.

Supongamos que comenzamos con N legionarios y cada K-ésimo es asesinado. En ese caso, podemos enmarcar el problema de la siguiente manera. Eliminaremos cada legionario K-ésimo en una primera pasada alrededor del círculo. Luego, si L ha sido asesinado, volveremos a preguntar el problema recursivamente en los legionarios restantes de la Liga Nacional.

Si en algún momento durante la ejecución de nuestro algoritmo K> N (donde N es el número restante de legionarios), usaremos K mod N en lugar de K para asegurarnos de que al menos un legionario muere en cada pase, de modo que nos acerquemos al solución.

En base a estas ideas, podemos llegar al siguiente código de Python:

Cálculo de legionario sobreviviente indexado # 0
def josephus (n, k):
# caso especial, k = 1
si k == 1:
retorno n-1
# caso base, si solo queda un legionario, ganan
si n == 1:
volver 0
numDead = n / k si k <= n más 1
#primeros y últimos legionarios en morir en curr. redondo
#the mod n se aplica en caso de que k> n
firstDeadIndex = (k-1)% n
lastDeadIndex = firstDeadIndex + k * (numDead-1)
# cual legionario comienza la próxima ronda contando
nextRoundStart = lastDeadIndex + 1
# averiguar quién es el ganador en la próxima ronda
winnerInNextRound = josephus (n – numDead, k)
#traducir eso a la numeración de la ronda actual
#los legionarios en [nextRoundStart, n) están todos vivos
if nextRoundStart + winnerInNextRound volver nextRoundStart + winnerInNextRound
# mira a [0, nextRoundStart). Algunos pueden estar muertos, ajustarse.
más:
winnerInNextRound – = (n – nextRoundStart)
# cada legionario K-th está muerto
blockNum = winnerInNextRound / (k-1)
indexWithinBlock = winnerInNextRound% (k-1)
return blockNum * k + indexWithinBlock

#algunos ejemplos
imprimir josephus (100, 2)
imprimir josephus (5, 2)
imprimir josephus (13, 5)

El análisis de este algoritmo es el siguiente. Cada ronda solo toma O (1) para simular. Cuando solo quedan k legionarios, habrá k rondas con 1 legionario muriendo en cada uno, por lo tanto, se requerirá tiempo O (k). Antes de eso, los legionarios morirán 1 por ronda entre k y 2k legionarios, 2 por ronda entre 2k y 3k legionarios, 3 por ronda entre 3k y 4k, y así sucesivamente.

Eso significa que el número requerido de rondas será: k + k / 2 + k / 3 +… + k / (n / k) = k (1 + 1/2 + 1/3 + 1 / (n / k) ) = O (k log (n / k)).

Cuando k es una constante pequeña, la complejidad del tiempo es O (log n). Cuando k = ~ n, el tiempo de ejecución es O (n).