Порядок ликвидации в Иосифа Пуршобелева

Проблема Джозефуса (или перестановка Джозефуса) - это теоретическая проблема, связанная с определенной игрой отсчета.

Люди стоят в кругу в ожидании казни. Отсчет начинается с первой точки круга и продолжается по кругу по часовой стрелке. После пропуска определенного количества людей, следующий человек казнен. Процедура повторяется с остальными людьми, начиная со следующего человека, идя в том же направлении и пропуская такое же количество людей, пока не останется только один человек и не будет освобожден. Например, если n=10, то порядок исключения составляет 2, 4, 6, 8, 10, 3, 7, 1, 9 и 5.

The problem is, without simulation of the above game, try to find out the order of 
elimination through means of mathematical formula or a mathematical pattern.

Изначально нам дано n, то есть количество людей в круге на старте. Дайте порядок устранения с учетом вышеуказанных условий и ограничений.

Проще говоря, выведите образец смерти, не используя никаких структур данных, таких как массивы и связанные списки.

Источник

3 ответа

Решение

Я подготовил решение после изучения 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 обозначает, что человек умрет, а n - общее число людей на начальном этапе. Зацикливание этой функции на всех значениях x от 1 до n дает нам порядок исключения.

Источник

Есть подход, который использует упорядоченный набор

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

  • Инициализируйте упорядоченный набор V и вставьте элементы из диапазона [1, N] в V.
  • Инициализируйте переменную, скажем, pos как 0, чтобы сохранить индекс удаленного элемента.
  • Итерируйте, пока размер V не станет больше 1, и выполните следующие шаги:
    • Сохраните размер набора в переменной, скажем 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

Источник 
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. Очередь заботится о том, чтобы сохранить новую позицию. Альтернативный способ решения - использовать отношение повторения.

Источник
Другие вопросы по тегам