El número de programación del teléfono móvil está cerrado

x? =?0;

¿Para qué? ¿I? =?1:20

x? =?mod(x+5,?I);

Fin

disp(x+1);

¿Se imprimirá %? 7 Ingrese a la columna del blog de CSDN-cs_zlg de la siguiente manera:

Pregunta planteada:

n personas (numeradas del 1 al n) forman un círculo, comienzan a contar desde 1 y reportan M filas , y el resto sigue contando desde 1 (empezando por la siguiente persona que acaba de salir de la fila). Encuentre el número de la última persona (ganador)

Para facilitar la discusión, sin afectar la intención original, primero cambiemos un poco el problema:

Descripción del problema: N personas (0 No. ~(n-1)), comienza a contar desde 0, inicia sesión (m-1) y sale, y continúa contando desde 0 para el resto. Descubra el número del ganador.

¿Conocemos a la primera persona (el número debe ser m%n-1)? Después de quitar la cola, las n-1 personas restantes forman un nuevo anillo de Joseph (a partir del número k=m%n personas):

K k+1 k+2...n-2, n- 1, 0, 1, 2,...k-2, informando 0 de k.

Ahora cambiemos sus números:

k? ->0

k+1->;1

k+2 ->2

...

k - 2 ->n-2

Después de la transformación, se convierte en el subproblema del número personal (n-1). Si la solución a este subproblema: X es la ganadora, entonces encuentre el valor correspondiente a Fórmula reemplazada: x' = (x+k)% n = (x+m)% n.

¿Cómo saber la solución al problema de (n-1) cuenta personal? Sí, siempre y cuando conozcas las soluciones de (n-2) personas. (n-2) ¿Qué pasa con las soluciones personales? Por supuesto, ¿en el caso de (n-3) primero? - ?Esta es obviamente una pregunta al revés.

Supongamos que f[i] significa que juego, M abandona con el último número ganador y el resultado final es, naturalmente, f[n].

Fórmula de recursión

f[1]= 0;

f[I]=(f[I-1]+m)%I ( I>1; )

Con esta fórmula lo único que tenemos que hacer es calcular el valor de f[i] de 1 a n, y el resultado final es f[n]. Debido a que la numeración siempre comienza desde 1 en la vida real, generamos f[n]+1.

La complejidad temporal de este algoritmo es O(n).