En informática y matemáticas, el Problema de Josefo (o permutación de Josefo) es un problema teórico. El siguiente es el enunciado del problema:
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 k-1 personas se saltan y la k-ésima persona muere en un círculo. La tarea es elegir el lugar en el círculo inicial para que seas el último que quede y así sobrevivas.
Por ejemplo, si n = 5 y k = 2, entonces la posición segura es 3. Primero, la persona en la posición 2 muere, luego la persona en la posición 4 muere, luego la persona en la posición 1 muere. Finalmente, la persona en la posición 5 muere. Así que la persona en la posición 3 sobrevive.
Si n = 7 yk = 3, entonces la posición segura es 4. Las personas en las posiciones 3, 6, 2, 7, 5 y 1 mueren en orden y la persona en la posición 4 sobrevive.
C++
#include <iostream>
using namespace std;
int josephus(int n, int k)
{
if (n == 1)
return 1;
else
/* The position returned by josephus(n - 1, k)
is adjusted because the recursive call
josephus(n - 1, k) considers the
original position k % n + 1 as position 1 */
return (josephus(n - 1, k) + k - 1) % n + 1;
}
// Driver Program to test above function
int main()
{
int n = 14;
int k = 2;
cout << "The chosen place is " << josephus(n, k);
return 0;
}
// This code is contributed by shubhamsingh10
C
#include <stdio.h>
int josephus(int n, int k)
{
if (n == 1)
return 1;
else
/* The position returned by josephus(n - 1, k) is
adjusted because the recursive call josephus(n -
1, k) considers the original position
k%n + 1 as position 1 */
return (josephus(n - 1, k) + k - 1) % n + 1;
}
// Driver Program to test above function
int main()
{
int n = 14;
int k = 2;
printf("The chosen place is %d", josephus(n, k));
return 0;
}
Java
// Java code for Josephus Problem
import java.io.*;
class GFG {
static int josephus(int n, int k)
{
if (n == 1)
return 1;
else
/* The position returned by josephus(n - 1, k)
is adjusted because the recursive call
josephus(n - 1, k) considers the original
position k%n + 1 as position 1 */
return (josephus(n - 1, k) + k - 1) % n + 1;
}
// Driver Program to test above function
public static void main(String[] args)
{
int n = 14;
int k = 2;
System.out.println("The chosen place is "
+ josephus(n, k));
}
}
// This code is contributed by Prerna Saini
Python3
# Python code for Josephus Problem
def josephus(n, k):
if (n == 1):
return 1
else:
# The position returned by
# josephus(n - 1, k) is adjusted
# because the recursive call
# josephus(n - 1, k) considers
# the original position
# k%n + 1 as position 1
return (josephus(n - 1, k) + k-1) % n + 1
# Driver Program to test above function
n = 14
k = 2
print("The chosen place is ", josephus(n, k))
# This code is contributed by
# Sumit Sadhakar
C#
// C# code for Josephus Problem
using System;
class GFG {
static int josephus(int n, int k)
{
if (n == 1)
return 1;
else
/* The position returned
by josephus(n - 1, k) is
adjusted because the
recursive call josephus(n
- 1, k) considers the
original position k%n + 1
as position 1 */
return (josephus(n - 1, k) + k - 1) % n + 1;
}
// Driver Program to test above
// function
public static void Main()
{
int n = 14;
int k = 2;
Console.WriteLine("The chosen "
+ "place is " + josephus(n, k));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP code for
// Josephus Problem
function josephus($n, $k)
{
if ($n == 1)
return 1;
else
/* The position returned by
josephus(n - 1, k) is
adjusted because the
recursive call josephus
(n - 1, k) considers the
original position k%n + 1
as position 1 */
return (josephus($n - 1, $k) +
$k - 1) % $n + 1;
}
// Driver Code
$n = 14;
$k = 2;
echo "The chosen place is ", josephus($n, $k);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript code for Josephus Problem
function josephus(n, k)
{
if (n == 1)
return 1;
else
/* The position returned
by josephus(n - 1, k) is
adjusted because the
recursive call josephus(n
- 1, k) considers the
original position k%n + 1
as position 1 */
return (josephus(n - 1, k)
+ k-1) % n + 1;
}
let n = 14;
let k = 2;
document.write("The chosen " + "place is " + josephus(n, k));
</script>
C++
#include <bits/stdc++.h>
using namespace std;
void Josh(vector<int> person, int k, int index)
{
// Base case , when only one person is left
if (person.size() == 1) {
cout << person[0] << endl;
return;
}
// find the index of first person which will die
index = ((index + k) % person.size());
// remove the first person which is going to be killed
person.erase(person.begin() + index);
// recursive call for n-1 persons
Josh(person, k, index);
}
int main()
{
int n = 14; // specific n and k values for original
// josephus problem
int k = 2;
k--; // (k-1)th person will be killed
int index
= 0; // The index where the person which will die
vector<int> person;
// fill the person vector
for (int i = 1; i <= n; i++) {
person.push_back(i);
}
Josh(person, k, index);
}
Java
import java.util.*;
class GFG{
static void Josh(List<Integer> person, int k, int index)
{
// Base case , when only one person is left
if (person.size() == 1) {
System.out.println(person.get(0));
return;
}
// find the index of first person which will die
index = ((index + k) % person.size());
// remove the first person which is going to be killed
person.remove(index);
// recursive call for n-1 persons
Josh(person, k, index);
}
// Driver code
public static void main(String [] args)
{
int n = 14; // specific n and k values for original
// josephus problem
int k = 2;
k--; // (k-1)th person will be killed
int index
= 0; // The index where the person which will die
List<Integer> person = new ArrayList<>();
// fill the person vector
for (int i = 1; i <= n; i++) {
person.add(i);
}
Josh(person, k, index);
}
}
// This code is contributed by umadevi9616
Python3
# Python code for Josephus Problem def Josh(person, k, index): # Base case , when only one person is left if len(person) == 1: print(person[0]) return # find the index of first person which will die index = ((index+k)%len(person)) # remove the first person which is going to be killed person.pop(index) # recursive call for n-1 persons Josh(person,k,index) # Driver Program to test above function n = 14 # specific n and k values for original josephus problem k = 2 k-=1 # (k-1)th person will be killed index = 0 # fill the person vector person=[] for i in range(1,n+1): person.append(i) Josh(person,k,index) # This code is contributed by # Gaurav Kandel
C#
using System;
using System.Collections.Generic;
class GFG {
static void Josh(List<int> person, int k, int index)
{
// Base case , when only one person is left
if (person.Count == 1) {
Console.WriteLine(person[0]);
return;
}
// find the index of first person which will die
index = ((index + k) % person.Count);
// remove the first person which is going to be killed
person.RemoveAt(index);
// recursive call for n-1 persons
Josh(person, k, index);
}
// Driver code
static void Main()
{
int n = 14; // specific n and k values for original
// josephus problem
int k = 2;
k--; // (k-1)th person will be killed
int index
= 0; // The index where the person which will die
List<int> person = new List<int>();
// fill the person vector
for (int i = 1; i <= n; i++) {
person.Add(i);
}
Josh(person, k, index);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
function Josh( person , k , index) {
// Base case , when only one person is left
if (person.length == 1) {
document.write(person[0]);
return;
}
// find the index of first person which will die
index = ((index + k) % person.length);
// remove the first person which is going to be killed
if (index > -1) {
person.splice(index, 1);
}
// recursive call for n-1 persons
Josh(person, k, index);
}
// Driver code
var n = 14; // specific n and k values for original
// josephus problem
var k = 2;
k--; // (k-1)th person will be killed
var index = 0; // The index where the person which will die
var person = [];
// fill the person vector
for (var i = 1; i <= n; i++) {
person.push(i);
}
Josh(person, k, index);
// This code is contributed by umadevi9616
</script>
C++
#include <bits/stdc++.h>
using namespace std;
int Josephus(int, int);
int Josephus(int n, int k)
{
k--;
int arr[n];
// Makes all the 'n' people alive by
// assigning them value = 1
for (int i = 0; i < n; i++) {
arr[i] = 1;
}
int cnt = 0, cut = 0,
// Cut = 0 gives the sword to 1st person.
num = 1;
// Loop continues till n-1 person dies.
while (cnt < (n - 1)) {
// Checks next (kth) alive persons.
while (num <= k) {
cut++;
// Checks and resolves overflow
// of Index.
cut = cut % n;
if (arr[cut] == 1) {
// Updates the number of persons
// alive.
num++;
}
}
// Refreshes value to 1 for next use.
num = 1;
// Kills the person at position of 'cut'
arr[cut] = 0;
// Updates the no. of killed persons.
cnt++;
cut++;
// Checks and resolves overflow of Index.
cut = cut % n;
// Checks the next alive person the
// sword is to be given.
while (arr[cut] == 0) {
cut++;
// Checks and resolves overflow
// of Index.
cut = cut % n;
}
}
// Output is the position of the last
// man alive(Index + 1);
return cut + 1;
}
// Driver code
int main()
{
int n = 14, k = 2;
cout << Josephus(n, k);
return 0;
}
// THIS CODE IS PRESENTED BY SHISHANK RAWAT
Java
// Java code to implement the above approach
import java.io.*;
class GFG {
public static void main(String[] args)
{
int n = 14, k = 2;
System.out.println(Josephus(n, k));
}
public static int Josephus(int n, int k)
{
k--;
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = 1; // Makes all the 'n' people alive by
// assigning them value = 1
}
int cnt = 0, cut = 0,
num
= 1; // Cut = 0 gives the sword to 1st person.
while (
cnt
< (n
- 1)) // Loop continues till n-1 person dies.
{
while (num
<= k) // Checks next (kth) alive persons.
{
cut++;
cut = cut
% n; // Checks and resolves overflow
// of Index.
if (arr[cut] == 1) {
num++; // Updates the number of persons
// alive.
}
}
num = 1; // refreshes value to 1 for next use.
arr[cut] = 0; // Kills the person at position of
// 'cut'
cnt++; // Updates the no. of killed persons.
cut++;
cut = cut % n; // Checks and resolves overflow
// of Index.
while (arr[cut]
== 0) // Checks the next alive person the
// sword is to be given.
{
cut++;
cut = cut
% n; // Checks and resolves overflow
// of Index.
}
}
return cut
+ 1; // Output is the position of the last
// man alive(Index + 1);
}
}
// This code is contributed by Shubham Singh
Python3
def Josephus(n, k): k -= 1 arr = [0]*n for i in range(n): arr[i] = 1 # Makes all the 'n' people alive by # assigning them value = 1 cnt = 0 cut = 0 num = 1 # Cut = 0 gives the sword to 1st person. while (cnt < (n - 1)): # Loop continues till n-1 person dies. while (num <= k): # Checks next (kth) alive persons. cut += 1 cut = cut % n # Checks and resolves overflow # of Index. if (arr[cut] == 1): num+=1 # Updates the number of persons # alive. num = 1 # refreshes value to 1 for next use. arr[cut] = 0 # Kills the person at position of 'cut' cnt += 1 # Updates the no. of killed persons. cut += 1 cut = cut % n # Checks and resolves overflow of Index. while (arr[cut] == 0): # Checks the next alive person the # sword is to be given. cut += 1 cut = cut % n # Checks and resolves overflow # of Index. return cut + 1 # Output is the position of the last # man alive(Index + 1) # Driver Code n, k = 14, 2 #map (int, input().splut()) print(Josephus(n, k)) # This code is contributed by ShubhamSingh
C#
// C# code to implement the above approach
using System;
using System.Linq;
public class GFG{
public static void Main ()
{
int n = 14, k = 2;
Console.Write(Josephus(n, k));
}
public static int Josephus(int n, int k)
{
k--;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = 1; // Makes all the 'n' people alive by
// assigning them value = 1
}
int cnt = 0, cut = 0,
num = 1; // Cut = 0 gives the sword to 1st person.
while (
cnt
< (n - 1)) // Loop continues till n-1 person dies.
{
while (num <= k) // Checks next (kth) alive persons.
{
cut++;
cut = cut % n;
// Checks and resolves overflow
// of Index.
if (arr[cut] == 1)
{
num++; // Updates the number of persons
// alive.
}
}
num = 1; // refreshes value to 1 for next use.
arr[cut]
= 0; // Kills the person at position of 'cut'
cnt++; // Updates the no. of killed persons.
cut++;
cut = cut
% n; // Checks and resolves overflow of Index.
while (arr[cut]
== 0) // Checks the next alive person the
// sword is to be given.
{
cut++;
cut = cut % n; // Checks and resolves overflow
// of Index.
}
}
return cut + 1; // Output is the position of the last
// man alive(Index + 1);
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// Javascript code to implement the above approach
let n = 14, k = 2;
document.write(Josephus(n, k));
function Josephus(n, k)
{
k--;
let arr = new Array(n);
for (let i = 0; i < n; i++)
{
// Makes all the 'n' people alive by
// assigning them value = 1
arr[i] = 1;
}
// Cut = 0 gives the sword to 1st person.
let cnt = 0, cut = 0,
num = 1;
// Loop continues till n-1 person dies.
while (cnt < (n - 1))
{
// Checks next (kth) alive persons.
while (num <= k)
{
cut++;
cut = cut % n;
// Checks and resolves overflow
// of Index.
if (arr[cut] == 1)
{
// Updates the number of persons
// alive.
num++;
}
}
// refreshes value to 1 for next use.
num = 1;
arr[cut] = 0; // Kills the person at position of 'cut'
// Updates the no. of killed persons.
cnt++;
cut++;
// Checks and resolves overflow of Index.
cut = cut % n;
// Checks the next alive person the
// sword is to be given.
while (arr[cut] == 0)
{
cut++;
// Checks and resolves overflow
// of Index.
cut = cut % n;
}
}
// Output is the position of the last
// man alive(Index + 1);
return cut + 1;
}
// This code is contributed by decode2207.
</script>
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