100 personas de pie en un círculo en un orden del 1 al 100. El número 1 tiene una espada. Él mata a la siguiente persona (es decir, el número 2) y le da la espada a la siguiente (es decir, el número 3). Todas las personas hacen lo mismo hasta que solo 1 sobrevive. ¿Qué número sobrevive al final? Quiero el programa C ++ para esto.

Answer 1

Recursión: Supongamos que hay n personas en el círculo, y sabemos la respuesta para todos los números más pequeños que n.

Si [math] n = 2k [/ math] es par, entonces cada segunda persona es asesinada, y nos quedan los números [math] k [/ math] [math] 1, 3, 5, \ dots, n – 1 [/ matemáticas]. Podemos reducir esto a un problema con las personas [matemáticas] k [/ matemáticas], mapeando los números [matemáticas] 1, 3, 5,…, n – 1 [/ matemáticas] en [matemáticas] 1, 2, 3, …, k [/ matemáticas]. Si la solución para [math] k [/ math] people es la persona numerada [math] i [/ math], entonces la solución para [math] n [/ math] people es [math] 2i – 1 [/ math] , dado que el número i-ésimo en la secuencia es [matemática] 2i – 1 [/ matemática].

Si [math] n = 2k + 1 [/ math] es impar, entonces nos quedan los números [math] k [/ math] [math] 3, 5, \ dots, n [/ math]. Si la solución para [math] k [/ math] people es la persona numerada [math] i [/ math], entonces una reducción similar muestra que la solución para [math] n [/ math] people es [math] 2i + 1 [/matemáticas].

Deje que [math] S_k [/ math] sea la solución para [math] k [/ math] personas.

Entonces [matemáticas] S_ {100} = 2S_ {50} – 1 [/ matemáticas]
[matemáticas] = 2 (2S_ {25} – 1) – 1 = 4S_ {25} – 3 [/ matemáticas]
[matemáticas] = 4 (2S_ {12} + 1) – 3 = 8S_ {12} + 1 [/ matemáticas]
[matemáticas] = 8 (2S_6 – 1) + 1 = 16S_6 – 7 [/ matemáticas]
[matemáticas] = 16 (2S_3 – 1) – 7 = 32S_3 – 23 [/ matemáticas]
[matemáticas] = 32 (2S_1 + 1) – 23 = 64S_1 + 9 [/ matemáticas]
[matemáticas] = 64 * 1 + 9 [/ matemáticas]
[matemáticas] = 73 [/ matemáticas]

(Gracias Shubham Gaurav por las correcciones)

Answer 2

Como el concepto es reducir primero el número a 2 ^ n, el primero sobrevivirá. Sravan Kumar lo ha resaltado y resuelto perfectamente. Me gustaría darle la alternativa. Escribe 100 en número binario que es 1100100 y toma el complemento que es 11011 y es 27. Resta el complemento del número original. Entonces 100-27 = 73.

Pruébalo para 50 personas.
50 = 110010 en binario.
El complemento es 1101 = 13.
Por lo tanto, 50-13 = 37.

Para el número en forma 2 ^ n, será la primera persona. Toma un ejemplo.
64 = 1000000
Complemento = 111111 = 63.
64-63 = 1.

Sigue resolviendo Es interesante.

Answer 3

Aquí hay un enfoque ligeramente diferente de las respuestas existentes.

Imagina un juego jugado con 128 personas. Como el héroe de la historia, asuma que comenzamos con la espada. Como se señaló en la respuesta de Sravan Kumar, estamos destinados a ganar porque 128 es una potencia perfecta de dos.

Después de que maten a 28 personas, la espada habrá sido pasada a la derecha 28 veces. Actualmente estás ubicado 28 posiciones a la izquierda del portador de la espada. Además, quedan 100 personas restantes. ¿Suena familiar?

El autor de la pregunta ha etiquetado a las 100 personas como No.1, No.2, No.3, … de modo que No.1 tiene la espada. ¿Dónde estamos? 28 personas a la izquierda. Si él está en [matemáticas] 1 [/ matemáticas], estamos en [matemáticas] 1-28 = -27 [/ matemáticas].

Por supuesto, esto corresponde al índice positivo [matemática] 100 – 27 [/ matemática], No. 73.

Answer 4

73 es la respuesta!

¿Cómo?

Considere un caso cuando hay 2 ^ números en círculo. Cada vez que el número se reduce a la mitad y finalmente en el último número 1 permanecerá.
ejemplo – 2 ^ 2 = 4
ronda 1 – 2 y 4 serán asesinados.
ronda 2 – 3 serán asesinados. Queda uno

Entonces, nuestro objetivo aquí debería ser alcanzar una cifra cuando llegue el número 2 ^ n y la persona que sostenga la espada en ese momento sobrevivirá.

cuando hay 100 personas – el número de armario 2 ^ será 64.
así que aquí nuestro objetivo es encontrar a la persona que sostiene la espada cuando quedan 64 personas.

64 personas restantes significan 36 personas asesinadas.
Como todas las personas alternativas están siendo asesinadas, el doble de 36, es decir, 72. Entonces, 72 personas fueron asesinadas en ese momento y la espada pasó de 73 a 73 después de matar a 72.

entonces, cuando quedaban 64 personas, 73 sostenían la espada,
¡Así que 73 sobrevivirán a los asesinatos!

Fuente – ¡Quién sobrevivirá a los asesinatos! Rompecabezas lógico!

Answer 5

Después de muchas explicaciones matemáticas serias, pensé en presentar una solución que podría funcionar para aquellos que entienden las explicaciones visuales.

1. En la primera ronda, el número 1 recoge la daga / espada y mata a la persona que está a su lado – # 2. Él procede a entregar la daga al # 3 que mata al # 4 y así sucesivamente.
Por lo tanto, todos los números pares mueren con el # 100 siendo el último en morir y la daga está con el # 1 para la ronda II.

2. En la Ronda II, el n. ° 1 comienza con el n. ° 3. Por lo tanto, los números que sobreviven corresponden a (1 + 4n) y, por lo tanto, el último que sobrevive a la ronda es (1 + 4 * 24), es decir, 97 que procede a superar el # 99 y entrega la daga al # 1.
¿Hasta ahora tan bueno?

3. En la ronda III, el n. ° 1 supera al n. ° 5 y entrega la daga al n. ° 9. Los sobrevivientes siguen el patrón (1 + 8n) con el # 97 siendo el último en la ronda (1 + 8 * 12). La persona que está a su lado es la número 1 y es su turno de ser despedido. La siguiente ronda comienza con el # 9

4. En la Ronda IV, los sobrevivientes son {1 + 8 * (2n + 1)} – comenzando con el # 9 que se enfrenta al # 17 (1 + 8 * 2) y entrega la daga al # 25 (1 + 8 * 3) . El último sobreviviente de esta ronda es (1 + 8 * 11) # 89 que mata al # 97 y entrega la daga al # 9.

5. En la Ronda V, los sobrevivientes son # 9 {(1 + 8 * 1)}, # 25 {(1 + 8 * 3)}, # 41, # 57 y # 73. Golpes alternativos y # 9 mata al # 25, daga al # 41 que mata al # 57 que da la daga al # 73 que mata al # 89 y entrega la daga al # 9.

6. En la Ronda VI, los sobrevivientes son # 9, # 41 y # 73. Entonces, una vez más, el # 9 golpea al # 41 y entrega la daga al # 73. Pero, lo que va, viene … el karma es una perra, etc.
El # 73 choca con el # 9 y emerge el ganador de esta ronda y de toda la serie.

El único sobreviviente en amigo mata a un amigo, el hombre mata al sórdido rompecabezas es el # 73 y, por supuesto, la daga omnipresente.

Answer 6

Para los perezosos y los amantes de python (probablemente estoy siendo redundante aquí), aquí hay un código en python …

# find the survivor n = 100 peeps = range(1, n+1) idx = 0 while len(peeps) > 1: peeps.pop((idx + 1) % len(peeps)) # Trivia: because of changing index and len(peeps), # the code below is not exactly equal to "idx = (idx + 1) % len(peeps)" idx = 0 if (idx >= len(peeps)-1) else (idx + 1) print peeps[0] 

Salida: 73

Lo bueno de este código es que viene con un dial giratorio llamado ‘n’. Echale un vistazo.

Answer 7

Queda el número 73.

Aquí hay dos métodos para resolver esto

1. Si lo haces manualmente, encontrarás que solo queda el número 73 después de 7 rondas de asesinatos (pruébalo en papel).

2. (Método generalizado para cualquier número de personas)

Este es en realidad un problema clásico de Josephus.
El problema original de Josephus es así;
“El problema lleva el nombre de Flavio Josefo, un historiador judío que vivió en el siglo primero. Según el relato de Josefo sobre el asedio de Yodfat, él y sus 40 soldados quedaron atrapados en una cueva, cuya salida fue bloqueada por romanos. Eligieron el suicidio sobre la captura y decidieron que formarían un círculo y comenzarían a suicidarse usando un paso de tres. Josefo afirma que por suerte o posiblemente por la mano de Dios, él y otro hombre siguieron siendo los últimos y se rindieron ante los romanos “.
Solución al enigma utilizando el enfoque del problema Josephus:
La solución requiere obtener el número más cercano que es la potencia de 2, que es menor que el número total de soldados, en este caso 64 y restarlo con el número dado. 1-64 = 36.
Ahora aplicamos la fórmula;

2n + 1 = 2 * 36 + 1 = 72 + 1 = 73.

PD: Gracias por la edición de Ritesh Bansal.

Answer 8

OKAY.

Le apliqué algunas matemáticas y se me ocurrió la siguiente fórmula:

Para N personas, etiquetadas como 1,2, .. N,
El último hombre en pie, L se da como:

[matemática] L = 2 * (N – (2 ^ {piso (log2 (N))}) + 1 [/ matemática].

En palabras, el último hombre en pie siempre será el sucesor del doble de la diferencia entre (N) y (la mayor potencia de 2 menor que igual a N).

Así que probémoslo.

Digamos que solo hay una persona. N = 1
Entonces, L = 2 * (1 – 1) + 1 = 1 (VERDADERO)

Digamos N = 5
Entonces, L = 2 * (5-4) + 1 = 3 (VERDADERO)

Tomar N = 100
Entonces, L = 2 * (100-64) + 1 = 73 VERDADERO ?? Trabajar y comprobar! 😉

¡Salud!

Algunos hechos que rodean esta fórmula:

1. Si N es una potencia de 2, el último hombre en pie es siempre 1.
2. Si N es uno menos que el poder de dos, el último hombre en pie es siempre el último hombre (N).

Answer 9

Este es el famoso problema de Josefo.

La 73a persona sobrevivirá.
Considere el caso cuando hay 2 ^ n números en el círculo. Cada vez que el número se reduce a la mitad y el número 1 permanece hasta el final.
En la pregunta dada,
1 mata a 2,
3 mata a 4 y así sucesivamente hasta que 71 mata a 72.
36 personas han sido asesinadas hasta ahora.
Quedan 64 personas en el círculo.
64 es una potencia de 2. Entonces, el primer hombre después de 72 será el nuevo número 1 en un círculo de 2 ^ 6.
Entonces 73 sobrevivirán.

EXPLICACIÓN
Problema de Josefo – Matanza de espadas y rompecabezas de supervivencia

Answer 10

Antes de pasar a la respuesta: normalmente no prefiero entender un rompecabezas de programación solo en términos matemáticos. Este tipo de preguntas se hacen para verificar 2 cosas; su habilidad en “Resolución de rompecabezas” y “Estructuras de datos”.

Dicho esto, pasemos a la solución.

Si ve esta pregunta y conoce algunos de sus resultados (diferentes respuestas para diferentes personas), entonces podemos formular un algoritmo muy simple para ella.

Por ejemplo: tomemos el número de personas como N y el 1 que sobrevive sea S.

1. Si N = 100; S = 73.
2. Si N = 1000; S = 977
3. Si N = 3; S = 3
4. Si N = 4; S = 1
5. Si N = 127; S = 127
6. Si N = 123; S = 119 (es decir, 127 – {(127–123) * 2} )

Creo que con estos resultados debes ver una relación entre N y S; que se une por “Una potencia de 2”.

Algoritmo

PASO 1: Obtenga N.
PASO 2: Encuentre el “Poder de 2” inmediatamente mayor que N. Llamemos P.
PASO 3: Restar N de (P-1). Llámalo M.
PASO 4: Multiplica M por 2. es decir, M * 2 .
PASO 5: Restar M * 2 de P-1. Eso es S.

A continuación se muestra el código para el algoritmo anterior:

  clase pública PeopleAndGuns {

	 public static void main (String [] args) {
		 Scanner sc = nuevo escáner (System.in);
		 int N = sc.nextInt ();
		 si (N == 0) {
			 System.out.println ("Lo siento");
		 }
		 más si (N == 1 || N == 2) {
			 System.out.println ("Survivor es:" +1);
		 }
		 más{

			 valor int = findSurvive (N);
			 System.out.println ("Survivor es:" + valor);
		 }
	 }

	 private static int findSurvive (int n) {
		
		 para (int i = 2; i <= n / 2; i ++) {
			 int num = (int) Math.pow (2, i);
			 if (num> = n) {
				 if (num == n) {
					 retorno 1;
				 }
				 if (num == n + 1) {
					 retorno num;
				 }
				 más{
					 int temp = ((num-1) - (n)) * 2;
					 return (num-1) -temp;
				 }
			 }
		 }
		
		 devuelve 0;
	 }
	
	
 }

#Paz.

Answer 11

CÓDIGO LÓGICO CAMINO

La respuesta es 73.

  $ números = rango (1,100);  // define una matriz con 100 elementos a partir de 1 a 100
 $ ronda = 1;  // define una variable para tener en cuenta cuántas rondas se requieren para obtener la respuesta (esto es opcional)
 $ temp = 1;  // Solo una variable booleana para eliminar el elemento alternativo

 // Como eliminar elementos de la matriz será una tarea repetitiva, definimos una función que eliminará elementos.
 función remove_elements () {
     $ números globales, $ ronda, $ temp;  // Usa las variables dentro de la función definiéndolas global
     foreach ($ números como $ clave => $ valor) {// itera el ciclo para cada elemento de una matriz
         if ($ temp == 0) {
             sin establecer ($ números [$ clave]);  // eliminar elemento alternativo
             $ temp = 1;
         }
         más {
             $ temp = 0;
         }
     }
     echo "Round $ round:" .implode (',', $ números). "
";  // imprime el número redondo y los elementos permanecieron después de eliminar elementos en esa ronda
     $ round ++;  // aumenta el número de ronda para cada iteración
     if (cuenta ($ números)! = 1) {
         remove_elements ();  // estamos llamando a la función remove_elements de forma recursiva hasta que nos quedemos con un solo elemento en nuestra matriz
     }
 }
 remove_elements ();  // Llama a la función

El resultado de este programa sería el siguiente:

Round 1: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99

Round 2: 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97

Round 3: 1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97

Round 4: 9, 25, 41, 57, 73, 89

Round 5: 9, 41, 73

Round 6: 9, 73

Round 7: 73

CAMINO MATEMÁTICO

Primero 1,3,5,7,9,11,13,15,17; 19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49 51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99 (consiguió espada, pasó a 1)

Entonces 1,5,9,13,17,21,25,29,33,37,41,45,49,53,57,61,65,69,73,77,81,85,89,93,97 (espada pasó a otra vez)

Luego 1,9,17,25,33,41,49,57,65,73,81,89,97 (espada pasó a 9)

Luego 9,25,41,57,73,89 (la espada pasó a 9 otra vez)

Luego 9,41,73 (la espada pasó a 9 otra vez)

Luego 9,73 (73 obtuvieron espada y mataron a 9)

Por lo tanto, la respuesta es “73”

Espero que ambas formas ayuden …

Answer 12

La forma más rápida de resolver estos problemas manualmente y el algoritmo de eficiencia energética para programarlo es el método de desplazamiento circular a la izquierda.

• Hay 100 personas.
• 100 en binario es 1100100.
• Desplazamiento circular a la izquierda 1100100.
• Obtenemos 1001001.
• Conviértalo de nuevo a la base 10.
• [matemáticas] 73 [/ matemáticas] [matemáticas] ^ {rd} [/ matemáticas] Es el último hombre en pie.

Para el código, debe definir una función de desplazamiento a la izquierda circular a nivel de bit. Es mejor que la recursividad o iteración en términos de tiempo y complejidad espacial.

Estoy realmente desconcertado por este descubrimiento. No sé por qué funciona, pero lo intenté varias veces y sigue funcionando. Me pregunto, ¿si hubieran matado a cada tercera persona, circular a la izquierda cambiando dos veces el trabajo?

Answer 13

El problema se discute bien en “Matemáticas concretas de Graham, Knuth y Patashnik”

La solución más simple es: desplazamiento cíclico a la izquierda un bit de la representación binaria de [math] 100 [/ math]. Es decir [matemática] 100 = 1100100_ {2} [/ matemática], desplazamiento cíclico a la izquierda un bit [matemática] 1001001_ {2} = 73 [/ matemática], punto.

¿Pero por qué? Es fácil de ver antes de que termine el primer círculo, todas esas personas eliminadas son números pares. Otra observación como la discutió Sravan Kumar es que después de alcanzar el número restante para ser el poder de 2, las siguientes personas serán el sobreviviente (tenga en cuenta que habrá [math] 100100_ {2} [/ math] personas eliminadas antes del recordatorio se convierte en el poder de 2). Entonces, ¿cuál es el número del sobreviviente? Es solo dos veces el número de personas que se ha eliminado hasta ahora, pulse uno, es el desplazamiento a la izquierda de [matemáticas] 100100_ {2} [/ matemáticas] + el siguiente número [matemáticas] 1_ {2} [/ matemáticas], o [matemáticas] 1001001_ {2} [/ matemáticas]. Eso prueba que la solución es el desplazamiento cíclico a la izquierda un bit de la representación binaria de [math] 100 [/ math].

Answer 14

La mayoría de las respuestas dadas aquí son correctas.

Pero creo que la explicación no es tan fácil de entender aquí. Me gustaría que sea un poco simple de entender aquí.

Punto 1 . Si tiene un número total de personas son como 2 (2 ^ 1), 4 (2 ^ 2), 8 (2 ^ 3), 16 (2 ^ 4), 32 (2 ^ 5), 64 (2 ^ 6) , … y así sucesivamente … En todos esos casos, el sobreviviente será quien sostenga la espada en el comienzo.

por ejemplo, si el total de personas son 32 y las personas numeradas como 11 sostienen la espada al comienzo, él sobrevivirá en el último.

Ahora llega al problema dado aquí, el número total de personas es 100. Comenzó con personas numeradas como 1. Nota: aquí tenemos que vigilar el número de personas restantes cuando están teñiendo una por una, en el momento en que las restantes El total de personas llegó a 64 que está sosteniendo la espada en el punto del tiempo.

Si miramos de cerca cuando murieron 36 personas (que son 2,4,6,8, …, 70,72) y el recuento restante es 64 ( las personas numeradas como 73 sostienen la Espada ) y según el punto 1 anterior si el número total es 64, entonces el sobreviviente será quien sostenga la espada / comenzó con el asesinato.

Eso concluye que el sobreviviente tendrá 73 años aquí.

Answer 15

El número 73 sobrevive.

Considere el caso cuando hay 2 ^ n números en el círculo. Cada vez que el número se reduce a la mitad y el número 1 permanece hasta el final.

En la pregunta dada, 1 mata a 2, 3 mata a 4 y así sucesivamente hasta que 71 mata a 72. 36 personas han sido asesinadas hasta ahora. Quedan 64 personas en el círculo. 64 es una potencia de 2. Entonces, el primer hombre después de 72 será el nuevo número 1 en un círculo de 2 ^ 6. Entonces 73 sobrevivirán.

Answer 16

A continuación se muestra una solución al problema anterior utilizando la lista circular vinculada en C.

#include

#include

nodo de estructura {

int pos;

struct node * next;

};

struct node * kill_the_victim (struct node * killer)

{struct node * victim = (struct node *) malloc (sizeof (struct node));

if (asesino == NULL)

{

printf (“\ nNinguna persona en el círculo”);

devuelve NULL;

}

si no (asesino-> siguiente == asesino)

{

asesino de retorno;

}

más{

víctima = asesino-> siguiente;

asesino-> siguiente = víctima-> siguiente;

libre (víctima);

asesino de retorno-> siguiente;

}

}

struct node * create_the_circle (int número_de_personas)

{struct node * first_man = (struct node *) malloc (sizeof (struct node)) ;;

struct node * new_person = (struct node *) malloc (sizeof (struct node));

struct node * temp;

int i;

new_person-> pos = 1;

first_man = new_person;

new_person-> next = first_man;

para (i = 2; i <= número_de_personas; i ++)

{

temp = (nodo de estructura *) malloc (sizeof (nodo de estructura));

temp-> pos = i;

new_person-> next = temp;

new_person = new_person-> next;

new_person-> next = first_man;

}

return first_man;

}

int main ()

{struct node * killer = (struct node *) malloc (sizeof (struct node));

unsigned int número_de_personas;

printf (“\ nTotal de personas en el círculo:”);

scanf (“% d”, y número_de_personas);

asesino = create_the_circle (número_de_personas);

while (killer-> next! = killer)

{

asesino = kill_the_victim (asesino);

}

printf (“Sobreviviente:% d \ n”, asesino-> pos);

devuelve 0;

}

Answer 17

Se han proporcionado numerosas explicaciones, creo que agregar una implementación de C ++ sería útil para algunos.

Acercarse:

Como sugiere la pregunta, si consideramos que hay n = 100 personas de tal manera que estén en círculo. Esto significa que si el último elemento en la iteración i- ésima no se mata, volverá a la primera persona (nota: era un círculo) y lo matará. De lo contrario, la primera persona tiene la espada y mata a la segunda persona en la lista actual. Esto continúa y para nuestra entrada actual (es decir, n = 100) la última persona en pie es 73.

Ahora, demos un paso atrás e intentemos resolver las entradas generalizadas. Pruebe para n = 1 (trivial), n = 2 y así sucesivamente. Observará que cada vez que el número es el poder de 2, la última persona en sobrevivir será quien lo inició. (es decir, para n = 2,4,8,16 .., la última persona en pie siempre será 1). Usando esta lógica, podemos tomar la potencia de 2 que está más cerca de n, digamos 2 [matemática] ^ k [/ matemática] (Observe el ciclo while). En nuestro ejemplo, 64 es la mayor potencia de 2 que es menor que el número.

100 – 64 = 36

Usando la inducción matemática,

36 personas son asesinadas como 2, 4, 6, …, 72. Por lo tanto, la espada ahora se le dará a la 73a persona. Ahora es la primera persona en comenzar en las 64 personas restantes. Así él será el que sobreviva.

Código C ++:

  #include 
 #include 

 usando el espacio de nombres estándar;

 int main ()
 {
     int i, tot_people;
  		 cout << "ingrese el número de personas =";
         cin >> tot_people;
         i = 0;
         while (pow (2, i) <= tot_people) {
             i ++;
         }
         yo--;
         int survivor = (tot_people- (pow (2, i + 1) -1-tot_people));
         cout << "el último en pie es =" << sobreviviente << endl;
		
    

 }

Answer 18

La forma directa de resolver esto podría ser escribir manualmente del 1 al 100 y luego tachar los números según el problema.

En tal escenario, sería así;

Ronda 1: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47 , 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97 99
Ronda 2: 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93 97
Ronda 3: 1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97
Ronda 4: 9, 25, 41, 57, 73, 89
Ronda 5: 9, 41, 73
Ronda 6: 9, 73
Ronda 7:73
entonces la respuesta es 73

¿Y si fueran 1000 soldados?

¿Sería posible resolverlo por este método?

Sí, pero consumiría mucho tiempo.

Aquí está la forma correcta de resolver este enigma.

Este es en realidad un problema clásico de Josephus.

El problema original de Josephus es así;

“El problema lleva el nombre de Flavio Josefo, un historiador judío que vivió en el siglo primero. Según el relato de Josefo sobre el asedio de Yodfat, él y sus 40 soldados quedaron atrapados en una cueva, cuya salida fue bloqueada por los romanos. Eligieron el suicidio sobre la captura y decidieron que formarían un círculo y comenzarían a suicidarse usando un paso de tres. Josefo afirma que por suerte o posiblemente por la mano de Dios, él y otro hombre siguieron siendo los últimos y se rindieron ante los romanos “.

Solución al enigma utilizando el enfoque del problema Josephus:
La solución requiere obtener el número más pequeño más cercano que sea la potencia de 2, en este caso 64 y restarlo con el número dado.100-64 = 36.

Ahora aplicamos la fórmula;
2n + 1 = 2 * 36 + 1 = 72 + 1 = 73.

Por lo tanto, respuesta = 73

Answer 19

Si 2 ^ n personas están en círculo, entonces la primera persona siempre sobrevivirá. Para mayor claridad, intente con no. 2, 4, 8, 16 .. cada vez que no 1 sobrevivirá por fin. Esto se debe a que con cada ronda de asesinatos impares, ninguna persona restante sobrevivirá y, finalmente, no 1 solo será un sobreviviente.

Ahora, después de unos pocos asesinatos iniciales en la primera ronda, habrá una instancia en la que un total de 2 ^ n personas estarán allí y la segunda persona tendrá la espada. Esta enésima persona se convertirá en primera persona en series de 2 ^ n personas y siempre sobrevivirá. Nuestro objetivo es descubrir a esta enésima persona.

Si hay un total de N personas en círculo, de modo que 2 ^ n ≤ N <2 ^ (n + 1). Entonces la enésima persona:

(r-1) / 2 + N – (r-1) = 2 ^ n

r = 2N – 2 ^ ( n + 1 ) + 1

Si N = 100 entonces n = 6

=> r = 73

Answer 20

Solo quiero señalar otra cosa interesante sobre la solución. Ahora que sabemos cómo llegar a la solución para cualquier número inicial ‘n’ de personas del resto de las respuestas aquí, quiero mencionar que básicamente está calculando la potencia más cercana de dos más pequeñas que ‘n’ (llame es ‘m’), y luego haciendo (nm) * 2 + 1.
En su ejemplo, n = 100, por lo tanto m = 64. (nm) * 2 + 1 = 73.
Ahora eche un vistazo a esta operación con cuidado. ¿Qué estamos haciendo exactamente?
Echemos un vistazo en binario:
100 = 1100100
La potencia más cercana de dos será: 1000000
Cuando restamos esto del número, obtenemos un número que es el número original cuyo bit MSD se elimina, es decir, 100100 (36). Multiplicamos esto por 2 que se desplaza a la izquierda y luego sumamos 1 para obtener la respuesta. (nm * 2 + 1).
Eso significaría que podríamos tener el número original desplazado a la izquierda y agregarle 1. Ahora, como sabemos que el bit mSD es 1 de todos modos, esto no es más que ROTACIÓN IZQUIERDA.
Por lo tanto, para obtener la respuesta para cualquier ‘n’, simplemente GIRE A LA IZQUIERDA el número 🙂

(Por supuesto, como programador, siempre quiero usar una lista enlazada circular para simular esto. Comenzando desde la cabeza, continúe eliminando nodos intermedios hasta la izquierda con solo un nodo).