Un grupo de monos tiene números, y los números son 1, 2, 3...m m. Este grupo de monos (m) se sientan en un círculo del orden de 1. -m, a partir de 1 conteo, cada vez que se cuenta el enésimo número, el mono abandonará el círculo, y así sucesivamente, hasta que solo quede el último mono en el círculo, entonces el mono es el rey.
Joseph
Problema de contraseña
Descripción del problema: N números son 1, 2, 3,..., n se sientan en un círculo en el sentido de las agujas del reloj, cada uno La persona toma una contraseña (un número entero positivo). La persona cuyo nombre es
cuenta en el sentido de las agujas del reloj comenzando desde 1 y se detiene cuando se alcanza el número designado M. La persona que informa a M será retirada de la cola y
como la nueva M. valor, su contraseña comienza con la siguiente persona en el sentido de las agujas del reloj, contando hacia atrás desde 1, y así sucesivamente hasta todos.
Hasta que todos estén fuera de la cola. Diseñe un programa para encontrar el orden de la lista, donde N≤30, my el valor de la contraseña se ingresan desde el teclado.
Dos. Requisitos básicos:
(1) Datos de entrada: ingrese m, n m, n es un número entero, n (2) Las indicaciones chinas siguen el método de m monos, cuente N Número, el número que genera el mono es el rey. Cree una función para implementar esta función y resuelva el problema de Joseph escribiéndola. Cuando m es pequeño, se puede resolver mediante cálculo escrito. M=2 En otras palabras, n personas forman un círculo, 1, 2, 1, 2, y reportan la muerte a 2 hasta que solo queda una persona. Cuando n = 2 k, la primera persona en informar el número es la última en morir. Para cualquier número natural, n se puede expresar como n = 2 k+t, donde t Entonces, cuando t personas mueran, solo quedarán 2 k personas. k personas El primero en morir es el último. La primera persona en informar el número entre estas 2k personas es 2t+1. Así que encontré la solución al problema de Joseph cuando M=2: Encuentra la potencia entera más grande de 2 no mayor que n, registrada como 2 k, y la última persona en morir. es 2(n-2k)+1. M=3 Es decir, n personas forman un círculo. Cuando 1, 2, 3, 1, 2, 3 cuentan hasta 3, morirán hasta que solo quede una persona. izquierda. . Esto es mucho más complicado que cuando M=2. Tomemos N=2009 como ejemplo. Cuando N=2009, M=3, la última persona asesinada se registra como F(2009, 3), o simplemente F(2009). Suponiendo que quedan n personas en esta situación, [n/3] personas morirán en la siguiente ronda, [] significa redondeo, y quedarán n-[n/3] personas. Supongamos que n personas son A1, A2,..., A(N-1), An. Empieza a contar desde a1. Después de un círculo, las personas restantes son A1, A2, A4, A5,...A (n-n mod 3-1), A (n-n mod 3+1),..., An. Entonces puedes obtener: 1.a(n-n mod 3) es el último en morir en esta ronda, y a(n-n mod 3+1) es el primero en la siguiente ronda Contando. 2. Si 3|n, la última persona en morir es la nueva ronda de F(n-[n/3]) personas. Si n mod 3≠0 y f (n-[n/3]) Si n mod 3≠0 y f(n-[n/3])& gt ;N mod 3, la última persona en morir es la persona F(n-[n/3])-(n mod 3) en la nueva ronda. 3. La nueva persona Kth corresponde a la persona original 3 *[(K-1)/2]+(K-1)mod 2+1. Combinando 1, 2 y 3, podemos obtener: F(1)=1, F(2)=2, F(3)=2, F(4 ) =1, F(5)=4, F(6)=1, Cuando f (n-[n/3]) Cuando f (n-[n /3])>: En n mod 3, k=F(n-[n/3])-(n mod 3), F(n)= 3 *[(k-1)/2]+(k - 1)módulo 2+1. Este algoritmo requiere cálculos [log(3/2)2009] veces, el número no excede 22 y se puede calcular con un bolígrafo. Entonces: En el primer círculo, 669 personas serán asesinadas. La última persona asesinada en este círculo fue en 2007, dejando un saldo de 1.340 personas. En la segunda vuelta murieron 446 personas y quedaron 894 personas. En la tercera ronda murieron 298 personas y quedaron 596 personas. En el cuarto asalto murieron 198 personas, quedando 398 personas. 132 personas murieron en la quinta ronda, quedando 266 personas. 88 personas murieron en la sexta ronda, quedando 178 personas. En la séptima ronda, 59 personas fueron asesinadas, quedando 119 personas. En la octava vuelta murieron 39 personas y quedaron 80 personas. En el noveno asalto, 26 personas fueron asesinadas, quedando 54 personas. En el décimo asalto, 18 murieron, quedando 36 personas. En once asaltos, 12 personas murieron, quedando 24 personas. Doce disparos, 8 personas murieron y 16 personas quedaron. Trece disparos, 5 personas muertas, 11 personas abandonadas. Después de catorce asaltos, tres personas murieron y ocho quedaron. Quince vueltas después, dos murieron y seis quedaron. F(1)=1, F(2)=2, F(3)=2, F(4)=1, F(5)=4, F(6)=1, Luego empuja hacia atrás. F(8)= 7 F(11)= 7 F(16)= 8 F(24)= 11 F(36)= 16 F(54)= 23 F(80)= 31 (119)= 43 F(178 F(596)= 191 F(894)= 286 F(1340)= 425 F(2009)= 634