Порядок исключения у Иосифа Флавия p‌r‌o‌b‌l‌e‌m

Я подготовил решение после изучения http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf . Этот рекурсивный упоминается в приведенном выше pdf.

int last_man(int n,int x)
{
    if(n==1 && x==1)
        return 1;
    else if(n>1 && x==1)
        return 2;
    else if(last_man(n-1,x-1)==n-1)
        return 1;
    else
        return last_man(n-1,x-1)+2;
}

X обозначает x-го человека, который умрет, а n — общее количество людей изначально. Зацикливание этой функции на всех значениях x от 1 до n дает нам порядок исключения.

function josIterative(n, k) {
let queue = [];
for (let i = 1; i <= n; i++) queue.push(i);

let deathOrder = [];

while (queue.length !== 1) {
    for (let skip = 1; skip < k; skip++) queue.push(queue.shift());
    deathOrder.push(queue.shift());
}

console.log("Death order is " + deathOrder.join(" "));
return queue[0]; //survivor
}

console.log(josIterative(7, 3) + " is survivor");

Эта программа написана на javascript es6. Очередь заботится о сохранении новой позиции. Альтернативный способ — решить с помощью рекуррентного соотношения.

Существует подход, использующий упорядоченный набор

(https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/):

• Инициализируйте упорядоченный набор V и вставьте элементы в диапазоне [1, N] в V.
• Инициализируйте переменную, скажем, pos как 0, чтобы сохранить индекс удаленного элемента.
• Iterate until the size of V is greater than 1, and perform the following steps:
  • Store the size of the set in a variable, say X
  • Обновите значение pos до (pos + K) % X.
  • Напечатайте элемент, на который указывает pos в V, а затем сотрите его.
  • Обновите pos до pos%V.size().
• Распечатать последний элемент, сохраненный в начале набора V

Вот код:

#include <iostream>
using namespace std;

// Header files, namespaces to use
// ordered set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set                          \
    tree<int, null_type, less<int>, rb_tree_tag, \
        tree_order_statistics_node_update>

// Function to find the person who
// will get killed in the i'th step
void orderOfExecution(int N, int K)
{

    // Create an ordered set
    ordered_set V;

    // Push elements in the range
    // [1, N] in the set
    for (int i = 1; i <= N; ++i)
        V.insert(i);

    // Stores the position to be removed
    int pos = 0;

    // Iterate until the size of the set
    // is greater than 1
    while (V.size() > 1) {

        // Update the position
        pos = (pos + K) % (int)V.size();

        // Print the removed element
        cout << *(V.find_by_order(pos)) << ' ';

        // Erase it from the ordered set
        V.erase(*(V.find_by_order(pos)));

        // Update position
        pos %= (int)V.size();
    }

    // Print the first element of the set
    cout << *(V.find_by_order(0));
}

int main()
{
    int N = 5, K = 2;

    // Function Call
    orderOfExecution(N, K);

    return 0;
}

Временная сложность: O(N * log(N))

Для лучшего понимания рекомендую посмотреть это видео:

https://youtu.be/KnsDFCcBJbY