c idioma Rey Mono Josefo

Hoy me di cuenta de que Josephus todavía tenía un algoritmo tan bueno. Este es un proceso de explicación que vi, que solo explicaba la situación de M = 3, pero después de leerlo, de repente me di cuenta.

Hay n personas en un círculo, numeradas en orden. Empiece a contar desde la primera persona (del 1 al 3). Quien informe 3 será eliminado del círculo y se le preguntará quién fue el último en salir.

Ingrese un número entero n (2)

Exprima el número restante de personas.

Entrada de muestra 4 Salida de muestra 1

Análisis:

p>

1) Cuando alguien sale, se puede utilizar para asignar un nuevo valor al número original. Entonces, en la segunda ronda, 1 y 2 se convierten en n 1, n 2 y 3 quedan fuera, por lo que 4 y 5 se convierten en n 4-1=n 3 y n 5-1=n 4, 6 quedan respectivamente. . . , y así sucesivamente;

3k 1 y 3k 2 se convierten en n 3k 1-k=n 2k 1 y n 3k 2-k=n 2k 2 respectivamente.

2) Según el método de numeración anterior, el número de la k-ésima persona que sale debe ser 3k, por lo que el número final de la última persona que sale es 3n.

Solución:

3) Si la cantidad es N gtn, entonces la persona con el número n debe tener otro número delante de él. (Porque el número original es 1...n) ¿Cómo encontramos el número anterior correspondiente al número n? Porque N=n 2k 1 o N=n 2k 2, k=(N-n-1)/2. Los números anteriores son 3k 1 y 3k 2 respectivamente (N=n 2k 1 o N=n 2k 2 da 1=N-n-2k, 2=N-n-2k) lo que significa 3k (N-N-2k)= 1.