Hay n personas de pie en círculo esperando ser ejecutadas. El conteo comienza en algún punto del círculo y continúa alrededor del círculo en una dirección fija. En cada paso, se salta un cierto número de personas y se ejecuta a la siguiente. La eliminación avanza alrededor del círculo (que se hace cada vez más pequeño a medida que se eliminan las personas ejecutadas), hasta que solo queda la última persona, a quien se le da la libertad. Dado el número total de personas n y un número k que indica que se saltan k-1 personas y se mata a la k-ésima persona en el círculo. La tarea es elegir el lugar en el círculo inicial para que seas el último que quede y así sobrevivas.
Hemos discutido una solución generalizada en el siguiente conjunto 1.
Problema de Josefo | Conjunto 1 (Solución AO(n))
En este post, se discute un caso especial cuando k = 2
Ejemplos:
Input : n = 5 Output : The person at position 3 survives Explanation : Firstly, the person at position 2 is killed, then at 4, then at 1 is killed. Finally, the person at position 5 is killed. So the person at position 3 survives. Input : n = 14 Output : The person at position 13 survives
A continuación se presentan algunos datos interesantes.
- En la primera ronda, todas las personas en posición pareja mueren.
- Para segunda vuelta surgen dos casos
- Si n es par: Por ejemplo, n = 8. En la primera ronda, primero mueren 2, luego 4, luego 6, luego 8. En segunda ronda, tenemos 1, 3, 5 y 7 en las posiciones 1, 2, 3 y 4º respectivamente.
- Si n es impar: Por ejemplo, n = 7. En la primera ronda, primero mueren 2, luego 4, luego 6. En segunda ronda, tenemos 3, 5, 7 en las posiciones 1, 2 y 3 respectivamente.
Si n es par y una persona está en la posición x en la ronda actual, entonces la persona estaba en la posición 2x – 1 en la ronda anterior.
Si n es impar y una persona está en la posición x en la ronda actual, entonces la persona estaba en la posición 2x + 1 en la ronda anterior.
A partir de los hechos anteriores, podemos definir recursivamente la fórmula para encontrar la posición del sobreviviente.
Let f(n) be position of survivor for input n, the value of f(n) can be recursively written as below. If n is even f(n) = 2f(n/2) - 1 Else f(n) = 2f((n-1)/2) + 1
La solución de la recurrencia anterior es
f(n) = 2(n - 2floor(Log2n) + 1
= 2n - 21 + floor(Log2n) + 1
A continuación se muestra la implementación para encontrar el valor de la fórmula anterior.
C++
// C/C++ program to find solution of Josephus
// problem when size of step is 2.
#include <stdio.h>
// Returns position of survivor among a circle
// of n persons and every second person being
// killed
int josephus(int n)
{
// Find value of 2 ^ (1 + floor(Log n))
// which is a power of 2 whose value
// is just above n.
int p = 1;
while (p <= n)
p *= 2;
// Return 2n - 2^(1+floor(Logn)) + 1
return (2 * n) - p + 1;
}
// Driver Program to test above function
int main()
{
int n = 16;
printf("The chosen place is %d", josephus(n));
return 0;
}
Java
// Java program to find solution of Josephus
// problem when size of step is 2.
import java.io.*;
class GFG {
// Returns position of survivor among
// a circle of n persons and every
// second person being killed
static int josephus(int n)
{
// Find value of 2 ^ (1 + floor(Log n))
// which is a power of 2 whose value
// is just above n.
int p = 1;
while (p <= n)
p *= 2;
// Return 2n - 2^(1+floor(Logn)) + 1
return (2 * n) - p + 1;
}
// Driver Program to test above function
public static void main(String[] args)
{
int n = 16;
System.out.println("The chosen place is "
+ josephus(n));
}
}
// This Code is Contributed by Anuj_67
Python3
# Python3 program to find solution of
# Josephus problem when size of step is 2.
# Returns position of survivor among a
# circle of n persons and every second
# person being killed
def josephus(n):
# Find value of 2 ^ (1 + floor(Log n))
# which is a power of 2 whose value
# is just above n.
p = 1
while p <= n:
p *= 2
# Return 2n - 2^(1 + floor(Logn)) + 1
return (2 * n) - p + 1
# Driver Code
n = 16
print ("The chosen place is", josephus(n))
# This code is contributed by Shreyanshi Arun.
C#
// C# program to find solution of Josephus
// problem when size of step is 2.
using System;
class GFG {
// Returns position of survivor among
// a circle of n persons and every
// second person being killed
static int josephus(int n)
{
// Find value of 2 ^ (1 + floor(Log n))
// which is a power of 2 whose value
// is just above n.
int p = 1;
while (p <= n)
p *= 2;
// Return 2n - 2^(1+floor(Logn)) + 1
return (2 * n) - p + 1;
}
// Driver Program to test above function
static void Main()
{
int n = 16;
Console.Write("The chosen place is "
+ josephus(n));
}
}
// This Code is Contributed by Anuj_67
PHP
<?php
// PHP program to find solution
// of Josephus problem when
// size of step is 2.
// Returns position of survivor
// among a circle of n persons
// and every second person being
// killed
function josephus($n)
{
// Find value of 2 ^ (1 + floor(Log n))
// which is a power of 2 whose value
// is just above n.
$p = 1;
while ($p <= $n)
$p *= 2;
// Return 2n - 2^(1+floor(Logn)) + 1
return (2 * $n) - $p + 1;
}
// Driver Code
$n = 16;
echo "The chosen place is ", josephus($n);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to find solution of Josephus
// problem when size of step is 2.
// Returns position of survivor among
// a circle of n persons and every
// second person being killed
function josephus(n)
{
// Find value of 2 ^ (1 + floor(Log n))
// which is a power of 2 whose value
// is just above n.
let p = 1;
while (p <= n)
p *= 2;
// Return 2n - 2^(1+floor(Logn)) + 1
return (2 * n) - p + 1;
}
// Driver code
let n = 16;
document.write("The chosen place is " +
josephus(n));
// This code is contributed by susmitakundugoaldanga
</script>
The chosen place is 1
La complejidad temporal de la solución anterior es O (Log n).
Este artículo es una contribución de Rahul Jain .
Se puede dar otra solución interesante al problema, mientras que k = 2 se basa en una observación, que solo tenemos que girar a la izquierda la representación binaria de N para obtener la respuesta requerida. A continuación se proporciona un código de trabajo para
el mismo considerando que el número es un número de 64 bits.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find solution of Josephus
// problem when size of step is 2.
#include <bits/stdc++.h>
using namespace std;
// Returns position of survivor among a circle
// of n persons and every second person being
// killed
int josephus(int n)
{
// An interesting observation is that
// for every number of power of two
// answer is 1 always.
if (!(n & (n - 1)) && n) {
return 1;
}
// The trick is just to right rotate the
// binary representation of n once.
// Find whether the number shed off
// during left shift is set or not
bitset<64> Arr(n);
// shifting the bitset Arr
// f will become true once leftmost
// set bit is found
bool f = false;
for (int i = 63; i >= 0; --i) {
if (Arr[i] == 1 && !f) {
f = true;
Arr[i] = Arr[i - 1];
}
if (f) {
// shifting bits
Arr[i] = Arr[i - 1];
}
}
Arr[0] = 1;
int res;
// changing bitset to int
res = (int)(Arr.to_ulong());
return res;
}
// Driver Program to test above function
int main()
{
int n = 16;
printf("The chosen place is %d", josephus(n));
return 0;
}
Python3
# Python 3 program to find solution of Josephus
# problem when size of step is 2.
# Returns position of survivor among a circle
# of n persons and every second person being
# killed
def josephus(n):
# An interesting observation is that
# for every number of power of two
# answer is 1 always.
if (~(n & (n - 1)) and n) :
return 1
# The trick is just to right rotate the
# binary representation of n once.
# Find whether the number shed off
# during left shift is set or not
Arr=list(map(lambda x:int(x),list(bin(n)[2:])))
Arr=[0]*(64-len(Arr))+Arr
# shifting the bitset Arr
# f will become true once leftmost
# set bit is found
f = False
for i in range(63,-1,-1) :
if (Arr[i] == 1 and not f) :
f = True
Arr[i] = Arr[i - 1]
if (f) :
# shifting bits
Arr[i] = Arr[i - 1]
Arr[0] = 1
# changing bitset to int
res = int(''.join(Arr),2)
return res
# Driver Program to test above function
if __name__ == '__main__':
n = 16
print("The chosen place is", josephus(n))
The chosen place is 1
Complejidad de tiempo: O(log(n))
Espacio auxiliar: O(log(n))
Esta idea es aportada por Anukul Chand .
Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA