Josephus p‌r‌o‌b‌l‌e‌m 中的消除顺序

Question

Josephus 问题（或 Josephus 排列）是与某种计数游戏相关的理论问题。

People are standing in a circle waiting to be executed. Counting begins at the first point in the circle and proceeds around the circle in a clockwise direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed. For example if n=10 then the order of elimination is 2, 4, 6, 8, 10, 3, 7, 1, 9 and 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，即开始时圈子里的人数。记住上述条件和限制，给出消除顺序。

简单来说，打印死亡模式，而不使用任何数据结构，如数组和链表。

Answer 1

我研究了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是最初的总人数。将此函数循环遍历从 1 到 n 的所有 x 值，即可得出排除顺序。

Answer 2

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");

这个程序是用javascriptes6写的。队列注意保留新位置另一种方法是使用递归关系

来解决

Answer 3

有一种使用有序集的方法

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

初始化一个有序集合V，将[1,N]范围内的元素插入V
初始化一个变量，比如pos为0，用来存放变量的索引删除元素。
迭代直到V的大小大于1，执行以下步骤：
- 将集合的大小存储在变量中，比如 X
- 将pos的值更新为(pos + K) % X
- 在V中打印pos指向的元素，然后擦除
- 将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

Josephus p‌r‌o‌b‌l‌e‌m 中的消除顺序

Order of elimination in Josephus p‌r‌o‌b‌l‌e‌m

algorithm

math

recursion

josephus