Проблема Иосифа | Набор 2 (простое решение при k = 2)

Опубликовано: 20 Января, 2022

В кругу стоят n человек, ожидающих казни. Отсчет начинается в некоторой точке круга и продолжается по кругу в фиксированном направлении. На каждом шаге пропускается определенное количество людей, и выполняется следующий человек. Устранение продолжается по кругу (который становится все меньше и меньше по мере удаления казненных людей), пока не останется только последний человек, которому дается свобода. Учитывая общее количество людей n и число k, которое указывает, что k-1 человек пропускается, а k-й человек убит в круге. Задача - выбрать место в начальном круге, чтобы вы остались последними и выжили.
Мы обсудили обобщенное решение в наборе 1 ниже.
Проблема Иосифа | Набор 1 (Решение AO (n))
В этом посте обсуждается особый случай, когда k = 2

Примеры :

 Ввод: n = 5
Результат: Человек на позиции 3 выживает.
Пояснение: Во-первых, человек на позиции 2 убит, 
затем на 4, затем на 1 убивается. Наконец, человек в 
позиция 5 убита. Таким образом, человек в позиции 3 выживает.

Ввод: n = 14
Результат: Человек на позиции 13 выживает.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Вот несколько интересных фактов.

В первом раунде убиваются все даже расположенные лица.
Для второго раунда возникают два случая
1. Если n четно: например, n = 8. В первом раунде убиты сначала 2, затем 4, затем 6, затем 8. Во втором раунде у нас есть 1, 3, 5 и 7 в позициях 1, 2, 3 и 4-е соответственно.
2. Если n нечетное: Например, n = 7. В первом раунде убиваются сначала 2, затем 4, затем 6. Во втором раунде у нас 3, 5, 7 в позициях 1, 2 и 3 соответственно.

Если n четно и человек находится в позиции x в текущем раунде, то человек был в позиции 2x - 1 в предыдущем раунде.
Если n нечетное и человек находится в позиции x в текущем раунде, значит, человек был в позиции 2x + 1 в предыдущем раунде.
Из приведенных выше фактов мы можем рекурсивно определить формулу для определения положения выжившего.

 Пусть f (n) будет позицией выжившего для входа n, 
значение f (n) может быть рекурсивно записано 
как показано ниже.

Если n четно
   f (n) = 2f (n / 2) - 1
Еще
   f (n) = 2f ((n-1) / 2) + 1

Решение вышеуказанного повторения

f(n) = 2(n - 2^floor(Log_²ⁿ⁾ + 1
     = 2n - 2^{1 + floor(Log}_²ⁿ⁾ + 1

Below is the implementation to find value of above formula.

C++

// C/C++ program to find solution of Josephus
// problem when size of step is 2.
#include <stdio.h>
 
// Returns position of survivor among a circle
// of n persons and every second person being
// killed
int josephus(int n)
{
    // Find value of 2 ^ (1 + floor(Log n))
    // which is a power of 2 whose value
    // is just above n.
    int p = 1;
    while (p <= n)
        p *= 2;
 
    // Return 2n - 2^(1+floor(Logn)) + 1
    return (2 * n) - p + 1;
}
 
// Driver Program to test above function
int main()
{
    int n = 16;
    printf("The chosen place is %d", josephus(n));
    return 0;
}

Java

// Java program to find solution of Josephus
// problem when size of step is 2.
import java.io.*;
 
class GFG {
 
    // Returns position of survivor among
    // a circle of n persons and every
    // second person being killed
    static int josephus(int n)
    {
 
        // Find value of 2 ^ (1 + floor(Log n))
        // which is a power of 2 whose value
        // is just above n.
        int p = 1;
        while (p <= n)
            p *= 2;
 
        // Return 2n - 2^(1+floor(Logn)) + 1
        return (2 * n) - p + 1;
    }
 
    // Driver Program to test above function
    public static void main(String[] args)
    {
        int n = 16;
 
        System.out.println("The chosen place is "
                           + josephus(n));
    }
}
 
// This Code is Contributed by Anuj_67

Python3

# Python3 program to find solution of
# Josephus problem when size of step is 2.
 
# Returns position of survivor among a
# circle of n persons and every second
# person being killed
def josephus(n):
     
    # Find value of 2 ^ (1 + floor(Log n))
    # which is a power of 2 whose value
    # is just above n.
    p = 1
    while p <= n:
        p *= 2
 
    # Return 2n - 2^(1 + floor(Logn)) + 1
    return (2 * n) - p + 1
 
# Driver Code
n = 16
print ("The chosen place is", josephus(n))
 
# This code is contributed by Shreyanshi Arun.

C#

// C# program to find solution of Josephus
// problem when size of step is 2.
using System;
 
class GFG {
 
    // Returns position of survivor among
    // a circle of n persons and every
    // second person being killed
    static int josephus(int n)
    {
 
        // Find value of 2 ^ (1 + floor(Log n))
        // which is a power of 2 whose value
        // is just above n.
        int p = 1;
        while (p <= n)
            p *= 2;
 
        // Return 2n - 2^(1+floor(Logn)) + 1
        return (2 * n) - p + 1;
    }
 
    // Driver Program to test above function
    static void Main()
    {
        int n = 16;
 
        Console.Write("The chosen place is "
                      + josephus(n));
    }
}
 
// This Code is Contributed by Anuj_67

PHP

<?php
// PHP program to find solution
// of Josephus problem when
// size of step is 2.
 
// Returns position of survivor
// among a circle of n persons
// and every second person being
// killed
function josephus($n)
{
    // Find value of 2 ^ (1 + floor(Log n))
    // which is a power of 2 whose value
    // is just above n.
    $p = 1;
    while ($p <= $n)
        $p *= 2;
 
    // Return 2n - 2^(1+floor(Logn)) + 1
    return (2 * $n) - $p + 1;
}
 
// Driver Code
$n = 16;
echo "The chosen place is ", josephus($n);
 
// This code is contributed by ajit.
?>

Javascript

<script>
 
// Javascript program to find solution of Josephus
// problem when size of step is 2.
 
// Returns position of survivor among
// a circle of n persons and every
// second person being killed
function josephus(n)
{
     
    // Find value of 2 ^ (1 + floor(Log n))
    // which is a power of 2 whose value
    // is just above n.
    let p = 1;
     
    while (p <= n)
        p *= 2;
 
    // Return 2n - 2^(1+floor(Logn)) + 1
    return (2 * n) - p + 1;
}
 
// Driver code
let n = 16;
 
document.write("The chosen place is " +
               josephus(n));
                        
// This code is contributed by susmitakundugoaldanga
 
</script>

Output:

The chosen place is 1

Временная сложность вышеуказанного решения составляет O (Log n).
Эта статья предоставлена Рахулом Джайном .

Еще одно интересное решение проблемы, когда k = 2, может быть дано на основе наблюдения, что нам просто нужно повернуть влево двоичное представление N, чтобы получить требуемый ответ. Рабочий код для
то же самое представлено ниже, учитывая, что число является 64-битным числом.

Below is the implementation of the above approach:

C++

// C++ program to find solution of Josephus
// problem when size of step is 2.
#include <bits/stdc++.h>
 
using namespace std;
 
// Returns position of survivor among a circle
// of n persons and every second person being
// killed
int josephus(int n)
{
    // An interesting observation is that
    // for every number of power of two
    // answer is 1 always.
    if (!(n & (n - 1)) && n) {
        return 1;
    }
 
    // The trick is just to right rotate the
    // binary representation of n once.
    // Find whether the number shed off
    // during left shift is set or not
 
    bitset<64> Arr(n);
 
    // shifting the bitset Arr
    // f will become true once leftmost
    // set bit is found
    bool f = false;
    for (int i = 63; i >= 0; --i) {
        if (Arr[i] == 1 && !f) {
            f = true;
            Arr[i] = Arr[i - 1];
        }
        if (f) {
 
            // shifting bits
            Arr[i] = Arr[i - 1];
        }
    }
 
    Arr[0] = 1;
 
    int res;
 
    // changing bitset to int
    res = (int)(Arr.to_ulong());
    return res;
}
 
// Driver Program to test above function
int main()
{
    int n = 16;
    printf("The chosen place is %d", josephus(n));
    return 0;
}

Output:

The chosen place is 1

Сложность времени: O (log (n))
Эту идею внес Анукул Чанд.
Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

Проблема Иосифа | Набор 2 (простое решение при k = 2)

C++

Java

Python3

C#

PHP

Javascript

C++

РЕКОМЕНДУЕМЫЕ СТАТЬИ