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 el círculo. La tarea es elegir el lugar en el círculo inicial para que seas el último que quede y así sobrevivas. (indexación basada en 0) .
Ejemplos:
Input : Length of circle : n = 4
Count to choose next : k = 2
Output : 0
Input : n = 5
k = 3
Output : 3
Ya hemos discutido diferentes soluciones a este problema ( here , here y here ). En esta publicación, se analiza una solución basada en STL de C++ que utiliza un contenedor de lista que utiliza la idea de una lista circular.
Implementación:
C++
// CPP program to find last man standing
#include <bits/stdc++.h>
using namespace std;
int josephusCircle(int n, int k){
list<int>l; //creates a doubly linked list using stl container//
for(int i=0;i<n;i++)
l.push_back(i); //pushes i to the end of the doubly linked list//
auto it = l.begin();
while(l.size()>1){
for(int i=1;i<k;i++){
it++;
if(it==l.end()){
//if iterator reaches the end,then we change it to begin of the list//
it = l.begin();
}
}
it = l.erase(it);
if(it==l.end()){
//if iterator reaches the end,then we change it to begin of the list//
it = l.begin();
}
}
return l.front(); //returns front element of the list//
}
/* Driver program to test above functions */
int main()
{
int n=14,k=2;
cout<<josephusCircle(n,k)<<"\n";
return 0;
}
Java
// Java Code to find the last man Standing
public class GFG {
// Node class to store data
static class Node
{
public int data ;
public Node next;
public Node( int data )
{
this.data = data;
}
}
/* Function to find the only person left
after one in every m-th node is killed
in a circle of n nodes */
static void getJosephusPosition(int m, int n)
{
// Create a circular linked list of
// size N.
Node head = new Node(1);
Node prev = head;
for(int i = 2; i <= n; i++)
{
prev.next = new Node(i);
prev = prev.next;
}
// Connect last node to first
prev.next = head;
/* while only one node is left in the
linked list*/
Node ptr1 = head, ptr2 = head;
while(ptr1.next != ptr1)
{
// Find m-th node
int count = 1;
while(count != m)
{
ptr2 = ptr1;
ptr1 = ptr1.next;
count++;
}
/* Remove the m-th node */
ptr2.next = ptr1.next;
ptr1 = ptr2.next;
}
System.out.println ("Last person left standing " +
"(Josephus Position) is " + ptr1.data);
}
/* Driver program to test above functions */
public static void main(String args[])
{
int n = 14, m = 2;
getJosephusPosition(m, n);
}
}
Python3
# Python3 program to find last man standing
# /* structure for a node in circular
# linked list */
class Node:
def __init__(self, x):
self.data = x
self.next = None
# /* Function to find the only person left
# after one in every m-th node is killed
# in a circle of n nodes */
def getJosephusPosition(m, n):
# Create a circular linked list of
# size N.
head = Node(1)
prev = head
for i in range(2, n + 1):
prev.next = Node(i)
prev = prev.next
prev.next = head # Connect last
#node to first
#/* while only one node is left in the
#linked list*/
ptr1 = head
ptr2 = head
while (ptr1.next != ptr1):
# Find m-th node
count = 1
while (count != m):
ptr2 = ptr1
ptr1 = ptr1.next
count += 1
# /* Remove the m-th node */
ptr2.next = ptr1.next
# free(ptr1)
ptr1 = ptr2.next
print("Last person left standing (Josephus Position) is ", ptr1.data)
# /* Driver program to test above functions */
if __name__ == '__main__':
n = 14
m = 2
getJosephusPosition(m, n)
# This code is contributed by mohit kumar 29
C#
// C# Code to find the last man Standing
using System;
public class GFG {
// Node class to store data
class Node
{
public int data ;
public Node next;
public Node( int data )
{
this.data = data;
}
}
/* Function to find the only person left
after one in every m-th node is killed
in a circle of n nodes */
static void getJosephusPosition(int m, int n)
{
// Create a circular linked list of
// size N.
Node head = new Node(1);
Node prev = head;
for(int i = 2; i <= n; i++)
{
prev.next = new Node(i);
prev = prev.next;
}
// Connect last node to first
prev.next = head;
/* while only one node is left in the
linked list*/
Node ptr1 = head, ptr2 = head;
while(ptr1.next != ptr1)
{
// Find m-th node
int count = 1;
while(count != m)
{
ptr2 = ptr1;
ptr1 = ptr1.next;
count++;
}
/* Remove the m-th node */
ptr2.next = ptr1.next;
ptr1 = ptr2.next;
}
Console.WriteLine ("Last person left standing " +
"(Josephus Position) is " + ptr1.data);
}
/* Driver program to test above functions */
static public void Main(String []args)
{
int n = 14, m = 2;
getJosephusPosition(m, n);
}
}
//contributed by Arnab Kundu
Javascript
<script>
// javascript Code to find the last man Standing
// Node class to store data
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/*
* Function to find the only person left after one in every m-th node is killed
* in a circle of n nodes
*/
function getJosephusPosition(m , n) {
// Create a circular linked list of
// size N.
var head = new Node(1);
var prev = head;
for (i = 2; i <= n; i++) {
prev.next = new Node(i);
prev = prev.next;
}
// Connect last node to first
prev.next = head;
/*
* while only one node is left in the linked list
*/
var ptr1 = head, ptr2 = head;
while (ptr1.next != ptr1) {
// Find m-th node
var count = 1;
while (count != m) {
ptr2 = ptr1;
ptr1 = ptr1.next;
count++;
}
/* Remove the m-th node */
ptr2.next = ptr1.next;
ptr1 = ptr2.next;
}
document.write("Last person left standing " + "(Josephus Position) is " + ptr1.data);
}
/* Driver program to test above functions */
var n = 14, m = 2;
getJosephusPosition(m, n);
// This code is contributed by umadevi9616
</script>
12
Complejidad del tiempo: O(k * n), ya que estamos usando bucles anidados para atravesar el tiempo k*n.
Espacio auxiliar: O(n), ya que estamos usando espacio extra para la lista enlazada.
Este artículo está mejorado por Mechanizer . 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.
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