Forma general del problema de Joseph
El problema de Joseph es un problema famoso: N personas se reúnen en un círculo y comienzan a contar desde la primera. La enésima persona será asesinada, la última que quede será asesinada y el resto será asesinado. Por ejemplo, N=6, M=5, el orden de muerte es: 5, 4, 6, 2, 3, 1.
Análisis:
(1) Dado que solo hay dos estados de muerte y vida para cada persona, el estado de cada persona se puede marcar con una matriz marrón. Verdadero significa muerto y. falso significa vivir.
(2) Todos están vivos al principio, por lo que todos los valores iniciales de la matriz se asignan a falso.
(3) Simula el proceso de matanza hasta que todos mueran.
código Pascal
var a: matriz [1..20] de número entero;
n, m, i, j, k, n1, m1: entero;
comenzar
readln(m, n);
para i：=1 a m hacer
a[i] :=i;
m1:=m;
n1:=1;
mientras m1gt;0
comienza p>
j:=(n n1-1-1) mod m1 1;
n1:=j;
m1:=m1-1;
writeln(a[j]);
para k：=j a m1 hacer
a[k]：=a[k 1];
end;
end.
Código C: #includelt;iostreamgt;usingnamespacestd;main(){bool?a[101]={0};intn,m ,i , f=0, t=0, s=0; cingt; gt; ngt; gt; // Enumerar todas las posiciones en el círculo una por una. // Array Simula un anillo, el último está conectado al primero if(!a[t])s // Si hay alguien en la posición t-ésima, se informará el número if(s==m) //El número reportado actualmente es m{s= 0; //Borra el contador coutlt;lt;tlt;lt;'';//Muestra el número de personas asesinadas a[t]=1; muerto, establecido en vacío f; // Número de muertes 1} } while(f!=n);// Hasta que todos mueran} Ya sea que se implemente con una lista vinculada o una matriz, tienen una cosa en común: Simule todo el proceso del juego, no solo es más problemático escribir el programa, sino que la complejidad del tiempo es tan alta como O (nm). Cuando n y m son muy grandes (como millones o decenas de millones), es. Es casi imposible producir resultados en poco tiempo. Observamos que la pregunta original solo requiere el número de serie del ganador final, en lugar de pedirle al lector que simule todo el proceso. Entonces, si quieres ser eficiente, rompe las reglas e implementa una pequeña estrategia matemática.
Para facilitar la discusión, cambiemos ligeramente la pregunta sin afectar el significado original:
Descripción del problema: n personas (numeradas 0~(n-1)), comience a informar desde 0 Contando, sale la persona que reporta (m-1), y las personas restantes siguen contando desde 0. Encuentra el número del ganador.
Sabemos que después de que la primera persona (el número debe ser (m-1)) sale de la cola, las n-1 personas restantes forman un nuevo anillo de Joseph (el número es k=m mod n (Empieza con la persona):
k k 1 k 2... n-2, n-1, 0, 1, 2,... k-2
Y comenzar desde k Informe 0.
Convirtamos sus números:
k --gt; 0
k 1 --gt 1
k 2 -- gt; 2
...
...
k-2 --gt; n-2
Después de la transformación, se convierte completamente en un subproblema de (n-1) informes personales. Si conocemos la solución a este subproblema: por ejemplo, x es el ganador final, entonces no es correcto cambiar este x de acuerdo con lo anterior. tabla. ¿Es la solución a la situación de n individuos? ! ! La fórmula para volver atrás es muy simple. Creo que todos pueden deducirla: x'=(x k) mod n
¿Cómo saber la solución al problema de (n-1) informes personales? Sí, siempre y cuando conozcas las soluciones de (n-2) personas. (n-2) ¿Qué pasa con las soluciones personales? Por supuesto, es el caso de encontrar (n-3) primero ---- ¡esto es obviamente un problema de razonamiento hacia atrás! Bien, la idea ya no existe, escribamos la fórmula de recursividad a continuación:
Dejemos que f represente el número del ganador cuando un jugador abandona el juego, y el resultado final es, naturalmente, f[n]
Fórmula de recursión
f[1]=0;
f=(f m) mod i; (igt; 1)
Con esta fórmula, lo que tenemos que hacer es calcular el valor de f secuencialmente de 1-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
Debido a la recursividad paso a paso, no es necesario guardar cada f, y el programa también es extremadamente simple:
c #include?lt;iostreamgt;using?namespace?std;const?int?m?=?3;int?main(){int?n,?f?=?0; cin?gt;gt;?n ;for?(int?i?=?1;?i?lt;=?n;?i )?f?=?(f? ?m)??i;cout?lt ;lt;?f? ?1 ?lt;lt;?endl;}pascal var?n, m, i, s: entero; empezar a escribir('N?M?='); i:=2?to?n ?dos:=(s m)?mod?i; writeln('The?winner?is?', s 1); Es mucho mejor que la mejora del algoritmo de simulación. Si n y m son iguales a un millón, el caso de diez millones ya no es un problema. Se puede observar que el uso apropiado de estrategias matemáticas no solo facilita la programación, sino que a menudo también mejora exponencialmente la eficiencia de ejecución del algoritmo.
El problema de José Edición 10e100 (de vijios)
Descripción Descripción
N personas se alinean en círculo. Comenzando con una determinada persona, numérela en el sentido de las agujas del reloj. A partir de la persona con el número 1, el número se cuenta en el sentido de las agujas del reloj "uno, dos, uno", y la persona que informa 2 sale del círculo. Si este ciclo continúa, el número de personas en el círculo seguirá disminuyendo. Dado que el número de personas es limitado, eventualmente quedará una persona. Preguntemos el número inicial de la última persona que queda.
Formato de entrada
Un número entero positivo n, que representa el número de personas. Los datos de entrada garantizan que el número n no supere los 100 dígitos.
Formato de salida
Un número entero positivo. Representa el número de la última persona que queda después del conteo "uno, dos, uno".
Entrada de muestra
9
Salida de muestra
3
Límite de tiempo Limitación de tiempo
Cada punto de prueba 1s
Sugerencia de comentario
Descripción de muestra
Cuando n=9, el número de la persona que salió del círculo El orden es:
2 4 6 8 1 5 9 7
La última persona restante tiene el número 3
Cuando vea esta pregunta por primera vez, puede pensar en una simulación. ¡Pero los datos son demasiado grandes! !
Primero hagamos el cálculo. Podemos ver que cuando n es 1, 2, 3, 4, 5, 6, 7, 8..., los resultados son 1, 1, 3, 1,. 3, 5. , 7, 1...
Existen las siguientes reglas: del 1 al siguiente 1 es un grupo, cada grupo es un número impar que aumenta a partir de 1, y el número de elementos en cada grupo es 1, 2, 4...
¡Esto es fácil de hacer! !
La idea general es la siguiente:
①read(a)
②b:=1, c:=1{b es el número de elementos en un cierto grupo, c Para el número acumulado agregado}
③mientras clt; a do (b: = b*2, c: = b c) {dejar de agregar cuando se excede el objetivo}
⑥c: =c-b{Volver al grupo anterior}
⑦x：=a-c{Calcular qué elemento del grupo es el objetivo}
⑧ans：=x*2-1{ Buscar este elemento}
⑨write(ans)
Solo tenga una idea y agregue alta precisión. El código que escribí es relativamente engorroso, porque primero escribí las ideas anteriores, luego escribí el proceso y luego integré algunos procesos simples en el programa principal, por lo que fue un poco complicado y engorroso.
Está perfectamente bien proporcionar ideas ~~~ vara, b, c: array[1..105]ofinteger; la, lb, lc, i: integer; s: procedimientoincc; vari: integer; =1to105doc：= c b；fori：=1to104doifcgt；9thenbeginc：=c cdiv10；c：=cmod10；end；end；functioncxiaoa：boolean；vari：integer；begincxiaoa：=false；fori：=105downto1doifclt；athenbegincxiaoa：=true；break seifcgt;thenbreak ;end;proceduredoubleb;vari:integer;beginfori:=1to105dob:=b*2;fori:=1to104doifbgt;9thenbeginb:=b bdiv10;b:=bmod10;end;end;proceduredecc;vari,j:integer ;beginfori:= 1to104doifcgt;=bthenc:=c-belsebeginj:=i 1;mientrasc[j]=0doinc(j);mientrasjgt;idobeginc[j]:=c[j]-1;c[j-1]: =c[j -1] 10;dec(j);end;c:=c-b;end;end;procedurefua;vari:integer;beginfori:=1to104doifagt;cthena:=a-celsebegina:=a-1;a: =a 10; a:=a-c;end;end;procedureoutit;vari,j:integer;beginfori:=1to105doa:=a*2;fori:=1to104doifagt;9thenbegina:=a adiv10;a:=amod10;end;ifa [1]gt ;0thena[1]:=a[1]-1elsebeginj:=2; whilea[j]=0doinc(j); whilejgt;1dobegina[j]:=a[j]-1;a[j- 1]:= a[j-1] 10;dec(j);end;a[1]:=a[1]-1;end;fori:=105downto1doifagt;0thenbeginj:=i;break;end;fori: =jdownto1dowrite(a );end;beginreadln(s);la:=longitud(s);fori:=ladownto1doa:=ord(s[la 1-i])-ord('0');b[1]: =1;c [1]:=1; whilecxiaoadobegindoubleb;incc;end;decc;fua;outit;end.