Dado que N personas están de pie en un círculo y un número entero K. Si inicialmente comienza desde la primera posición, la K -ésima persona viva en el sentido de las agujas del reloj desde la posición actual muere, y luego la posición actual se desplaza a la posición de (K+1) ª persona viva y se realiza el mismo paso hasta que solo quede una persona, la tarea es imprimir la posición de la última persona viva.
Ejemplos:
Entrada: N = 5, K = 2
Salida: 3
Explicación:
Una forma de realizar las operaciones es:
- Paso 1: Inicialmente, el conteo comienza desde la posición 1. Por lo tanto, la k -ésima persona viva en la posición 2 muere, por lo que las personas vivas restantes están en las posiciones {1, 3, 4, 5}.
- Paso 2: Ahora, el conteo comienza desde la posición 3. Por lo tanto, la K -ésima persona viva en la posición 4 muere, por lo que las personas vivas restantes están en las posiciones {1, 3, 5}.
- Paso 3: Ahora, el conteo comienza desde la posición 5. Por lo tanto, el Kthla persona viva en la posición 1 muere, por lo que las personas vivas restantes están en las posiciones {3, 5}.
- Paso 4: Ahora, el conteo comienza desde la posición 3. Por lo tanto, el Kthla persona viva en la posición 5 muere, por lo que la última persona viva está en la posición 3.
Por lo tanto, la última persona que queda viva está en la posición 3.
Entrada: N = 10, K = 4
Salida: 5
Los diferentes enfoques para resolver este problema se analizan en el Conjunto 1 y el Conjunto 2 de este artículo.
Enfoque 1 (usando el vector): el problema anterior se conoce como el problema de Josefo . El problema se puede resolver utilizando la recursión y la estructura de datos vectoriales de la biblioteca STL .
- Inicialice un vector , por ejemplo, arr[] para almacenar las posiciones de todas las personas.
- Iterar en el rango [1, N] usando la variable i y en cada iteración agregar i al vector arr[] .
- Defina una función recursiva, digamos RecursiveJosephus(vector<int>:: iterator it, vector<int>arr), donde apunta a la persona viva actual desde donde se contarán los elementos K.
- Si el tamaño del vector arr es 1, devuelva el valor en arr[0].
- Iterar en el rango [1, K-1] y luego, en cada iteración, incrementarlo en 1 y si se vuelve igual, arr. end() luego asígnele arr.begin ( ) .
- Ahora, si está apuntando al último elemento del vector arr, extraiga el último elemento del vector , arr , y luego actualícelo con la posición de (K+1) la persona viva, es decir, arr.begin() .
- De lo contrario, borra la posición de la persona señalada por él . Después de la eliminación, ahora apunta a la posición de la (K+1) ésima persona.
- Finalmente, después de completar los pasos anteriores, llame a la función RecursiveJosephus(arr.begin(), arr) e imprima el valor devuelto como la posición de la última persona viva.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Recursive auxiliary function to find
// vthe position of thevlast alive person
int RecursiveJosephus(vector<int>& arr, int K,
vector<int>::iterator it)
{
// If size of arr is 1
if (arr.size() == 1) {
return arr[0];
}
// Iterate over the range [1, K-1]
for (int i = 1; i < K; i++) {
// Increment it by 1
it++;
// If it is equal to arr.end()
if (it == arr.end()) {
// Assign arr.begin() to it
it = arr.begin();
}
}
// If it is equal to prev(arr.end())
if (it == prev(arr.end())) {
// Assign arr.begin() to it
it = arr.begin();
// Remove the last element
arr.pop_back();
}
else {
// Erase the element at it
arr.erase(it);
}
// Return the last alive person
return RecursiveJosephus(arr, K, it);
}
// Function to find the position of the
// last alive person
int Josephus(int N, int K)
{
// Stores positions of every person
vector<int> arr;
for (int i = 1; i <= N; i++)
arr.push_back(i);
// Function call to find the position
// of the last alive person
return RecursiveJosephus(arr, K, arr.begin());
}
// Driver Code
int main()
{
// Given Input
int N = 5;
int K = 2;
// Function Call
cout << Josephus(N, K);
}
Producción
3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque 2 (usando SET): el problema se puede resolver usando recursividad y una estructura de datos establecida de la biblioteca STL .
- Inicialice un conjunto , digamos, arr para almacenar las posiciones de todas las personas.
- Iterar en el rango [1, N] usando la variable i , y en cada iteración insertar i en el conjunto arr .
- Defina una función recursiva, digamos RecursiveJosephus(set<int>:: iterator it, set<int>arr), donde apunta a la posición de la persona viva actual desde donde se contarán los elementos K.
- Si el tamaño del set arr es 1, devuelva el valor señalado por el iterador, it.
- Iterar en el rango [1, K-1] y luego, en cada iteración, incrementarlo en 1 y si llega a ser igual a arr. end(), luego asígnele arr.begin ( ) .
- Ahora, si está apuntando a la posición del último elemento del conjunto , arr , elimine el último elemento del conjunto, arr , y luego actualícelo con la posición de la (K+1) th , persona, es decir , arr.begin( ).
- De lo contrario, almacene el valor del siguiente iterador en una variable, diga val y luego borre la posición señalada por él .
- Después de la eliminación, deja de ser válido. Por lo tanto, ahora encuentre el valor de val en el conjunto, arr , y luego asígneselo . Ahora apunta a la posición de la ( K+1) -ésima persona viva.
- Finalmente, después de completar los pasos anteriores, llame a la función RecursiveJosephus(arr.begin(), arr) e imprima el valor devuelto como la posición de la última persona viva.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Recursive auxiliary function to find
// the position of the last alive person
int RecursiveJosephus(set<int>& arr, int K,
set<int>::iterator it)
{
// If size of arr is 1
if (arr.size() == 1) {
return *it;
}
// Iterate over the range [1, K-1]
for (int i = 1; i < K; i++) {
// Increment it by 1
it++;
// If it is equal to arr.end()
if (it == arr.end()) {
// Assign arr.begin() to it
it = arr.begin();
}
}
// If it is equal to prev(arr.end())
if (it == prev(arr.end())) {
// Assign arr.begin() to it
it = arr.begin();
// Remove the last element
arr.erase(prev(arr.end()));
}
else {
// Stores the value pointed
// by next iterator of it
int val = (*next(it));
// Erase the element at it
arr.erase(it);
// Update it
it = arr.find(val);
}
// Return the position of
// the last alive person
return RecursiveJosephus(arr, K, it);
}
// Function to find the position
// of the last alive person
int Josephus(int N, int K)
{
// Stores all the persons
set<int> arr;
for (int i = 1; i <= N; i++)
arr.insert(i);
// Function call to find the position
// of the last alive person
return RecursiveJosephus(arr, K, arr.begin());
}
// Driver Code
int main()
{
// Given Input
int N = 5;
int K = 2;
// Function Call
cout << Josephus(N, K);
}
Producción
3
Complejidad de tiempo: O(N*K+N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por amulshaturia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA