Implementación de Josephus Circle usando la lista STL

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>
Producción

12

Complete Interview Preparation - GFG

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *