problema de Josefo | (Solución iterativa)

Hay N Los niños están sentados en N sillas dispuestas alrededor de un círculo. Las sillas están numeradas del 1 al N. El juego comienza yendo en círculos contando los niños a partir de la primera silla. Una vez que la cuenta llega a K, ese niño abandona el juego, retirando su silla. El juego comienza de nuevo, comenzando con la siguiente silla en el círculo. El último niño que queda en el círculo es el ganador. Encuentra al niño que gana el juego. Ejemplos:

Input : N = 5, K = 2
Output : 3
Firstly, the child at position 2 is out, 
then position 4 goes out, then position 1
Finally, the child at position 5 is out. 
So the position 3 survives.

Input : 7 4
Output : 2

Hemos discutido una solución recursiva para el Problema de Josefo . La solución dada es mejor que la solución recursiva de Josephus Solution, que no es adecuada para grandes entradas, ya que genera un desbordamiento de pila. La complejidad del tiempo es O(N). Enfoque : en el algoritmo, usamos la variable de suma para averiguar la silla que se eliminará. La posición actual de la silla se calcula sumando el número de sillas K a la posición anterior, es decir, la suma y el módulo de la suma. Finalmente devolvemos sum+1 ya que la numeración comienza de 1 a N. 

// Iterative solution for Josephus Problem
#include <bits/stdc++.h>
using namespace std;
 
// Function for finding the winning child.
long long int find(long long int n, long long int k)
{
    long long int sum = 0, i;
 
    // For finding out the removed
    // chairs in each iteration
    for (i = 2; i <= n; i++)
        sum = (sum + k) % i;
 
    return sum + 1;
}
 
// Driver function to find the winning child
int main()
{
    int n = 14, k = 2;
    cout << find(n, k);
    return 0;
}

// Iterative solution for Josephus Problem
class Test
{
 
    // Method for finding the winning child.
    private int josephus(int n, int k)
    {
        int sum = 0;
 
        // For finding out the removed
        // chairs in each iteration
        for(int i = 2; i <= n; i++)
        {
            sum = (sum + k) % i;
        }
 
        return sum+1;
    }
 
    // Driver Program to test above method
    public static void main(String[] args)
    {
        int n = 14;
        int k = 2;
        Test obj = new Test();
        System.out.println(obj.josephus(n, k));
    }
}
 
// This code is contributed by Kumar Saras

# Iterative solution for Josephus Problem
 
# Function for finding the winning child.
def find(n, k):
 
    sum = 0
 
    # For finding out the removed
    # chairs in each iteration
    for i in range(2,n+1):
        sum = (sum + k) % i
 
    return sum + 1
 
# Driver function to find the winning child
n,k = 14,2
print(find(n, k))
 
# This code is contributed by shinjanpatra

<script>
 
// Iterative solution for Josephus Problem
 
// Function for finding the winning child.
function find(n, k)
{
    let sum = 0, i;
 
    // For finding out the removed
    // chairs in each iteration
    for (i = 2; i <= n; i++)
        sum = (sum + k) % i;
 
    return sum + 1;
}
 
// Driver function to find the winning child
let n = 14, k = 2;
document.write(find(n, k),"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

13