1

约瑟夫斯问题（或约瑟夫斯排列）是一个与某种计数游戏相关的理论问题。

人们围成一圈等待被处决。计数从圆圈中的第一个点开始，并沿顺时针方向围绕圆圈进行。跳过指定人数后，执行下一个人。对剩余的人重复该过程，从下一个人开始，朝相同的方向前进并跳过相同数量的人，直到只剩下一个人并被释放。例如，如果 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，即一开始圈内的人数。牢记上述条件和约束，给出消除顺序。

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

4

3 回答 3

2

我在学习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 值上循环这个函数，就可以得到消除的顺序。

于 2016-02-02T19:32:39.667 回答
1 
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 编写的。队列注意保留新位置另一种方法是使用递归关系解决

于 2020-02-20T13:45:11.323 回答
1

有一种使用有序集的方法

（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

于 2021-07-22T11:34:15.773 回答