约瑟夫问题探究

本文探究了约瑟夫问题的相关知识。

问题介绍

约瑟夫问题是指这样一类问题:\(n\) 个人围成一圈,编号为 \(1\)\(n\)。从 \(1\) 号最先从 \(1\) 开始报数,每次报到 \(m\) 的人出圈,下一个人重新从 \(1\) 开始报数,直到剩下最后一人为止。

解法介绍

其中影响到一个人在出圈顺序中的位置 \(id\) 的有三个关键参量:他的编号 \(i\) 、人数 \(n\) 以及出圈间歇 \(m\)

在某些特殊情况下,部分参量并不起作用。如 \(m|i\) 时, \(i\)\(id\) 无影响; \(m = 1\) 时, \(n\)\(id\) 无影响。在部分题目中这可能成为解题的关键。

该类问题有两种问法,分别是:

  • 询问约瑟夫排列(即出圈顺序)

  • 询问第 \(k\) 出圈(第 \(n\) 出圈者即为获胜者)

询问约瑟夫排列

一般情况

时间复杂度 \(\mathcal{O}(n \log n)\)

这样考虑问题:假定当前出圈的人编号为当前第 \(k\) 小,此人出圈后圈内还有 \(n\) 人,那么下一个出圈的人为圈内编号第 \((k-1+m-1)\bmod n + 1\) 小。

那么只需要一个数据结构,满足能够单点修改,并查询区间第 \(k\) 小的:权值树状数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

struct ValueBIT {
vector<int> c;
int n;

int lowbit(int x) {
return x & (-x);
}

void init(int n) {
this->n = n;
c.resize(n + 1);
for (int i = 1; i <= n; i++) {
c[i] = lowbit(i);
}
}

void add(int m, int x) {
for (int i = m; i <= n; i += lowbit(i)) {
c[i] += x;
}
}

int find_kth(int k) {
int add = 0, sum = 0;
for (int i = 20; i >= 0; i--) {
add += 1 << i;
if (add > n || c[add] + sum >= k) {
add -= 1 << i;
} else {
sum += c[add];
}
}
return add + 1;
}
} vbit;

int main() {
int n, m;
scanf("%d%d", &n, &m);
vbit.init(n);
int now = 1;
while (n) {
now = (now - 1 + m - 1) % n + 1;
int k = vbit.find_kth(now);
vbit.add(k, -1);
printf("%d ", k);
n--;
}
return 0;
}

当然也可以使用顺序统计树

询问第 \(k\) 出圈

时间复杂度 \(\mathcal{O}(k)\)

\(f(n,m,k)\) 表示第 \(k\) 出圈人。

有公式:

\[ f(n,m,k)= \begin{cases} (m - 1) \bmod n + 1 & , k = 1 \\ (f(n - 1, m, k - 1) -1 + m) \bmod n + 1 & , k > 0 \end{cases} \]

代码实现如下

1
2
3
int f(int n, int m, int k) {
return ((k == 1 ? 0 : f(n - 1, m, k - 1)) - 1 + m) % n + 1;
}

当然也有非递归的写法

1
2
3
4
5
6
7
int f(int n, int m, int k) {
int s = (m - 1) % (n - k + 1);
for (int i = n - k + 2; i <= n; i++) {
s = (s + m) % i;
}
return s + 1;
}

时间复杂度 \(\mathcal{O}(\log_{\frac{m}{m - 1}}n)\)

\(n>>m\) 时,每次从 \(1\)\(n\) 的一个循环中,有 \(\lfloor \frac{n}{m} \rfloor \times m\) 人报数,其中 \(\lfloor \frac{n}{m} \rfloor\) 人出圈。

参考前面时间复杂度 \(\mathcal{O}(k)\) 的式子,可以发现在此过程中有许多取模操作是无作用的。

于是我们可以合并一些操作,使得部分加法合并为乘法。

有公式

\[ f(n, m, k) = (f(n - c, m, k - c) - 1 + m \times c) \bmod n + 1 \]

式中 \(c\) 表示从当前的 \(n\) 一直变化到到 \(c\) 的期间内取模都无作用的最大的 \(c\)

代码如下

1
2
3
4
5
6
7
8
9
10
11
int f(int n, int m, int k) {
if (m == 1) {
return k;
}
int i = n - k + 1, s = (m - 1) % i;
while (i < n) {
int c = min(n - i, (i - s + m - 2) / (m - 1));
s = (s + m * c) % (i += c);
}
return s + 1;
}

时间复杂度 \(\mathcal{O}(\frac{mk}{n})\)

易知第 \(k\) 出圈人为第 \(k \times m\) 报数人,以此为基础进行推导。

首先明确几个概念:

  • 位置编号:从 \(1\) 开始编号到 \(n\),表示在圈内的初始编号为 \(k\)

  • 报数编号:从 \(1\) 开始编号到 \(n \times m\),表示第 \(k\) 次报数。

  • 报数:从 \(1\) 开始编号到 \(m\),表示某人所报的某个数。

首先取一个报数编号 \(p\),对应位置编号 \(id\)。可以用该式来表示:\(p = a \times m + b\) (\(0 \leq a < n\), \(1 \leq b \leq m\))。实际含义是:在第 \(a\) 轮报数结束后,报数为 \(b\)

那么容易推出以下信息:

  • 此时圈内所剩人员数量为 \(n - a\)

  • 若此人报数 \(b = m\),则此人出局。否则圈内剩余的人将会恰好各报一次数,然后此人会再一次报数。

假设此人未出局,那么 \(b < m\)

设此人下一次报数编号为 \(q\),易知 \(q = p + n - a = a \times (m - 1) + b + n\)

那么可以推导:\(a = \dfrac{q - n - b}{m-1} = \lfloor \dfrac{q - n - 1}{m - 1} \rfloor\)

所以有:\(p = q - n + a = q - n - \lfloor \dfrac{q - n - 1}{m - 1} \rfloor = \lfloor \dfrac{(q - n - 1) \times m}{m - 1} \rfloor + 1\)

这样就完成了后继公式到前驱公式的变化,如此不断迭代,直到得到他是第 \(k\) 报数人为止。

有公式:

\[ f(n, m, k) = g(n, m, k \times m) \]

\[ g(n, m, x) = \begin{cases} x & , x \leq n \\ g(n, m, \lfloor \dfrac{(x - 1 - n) \times m}{m - 1} \rfloor + 1) &, x > n \end{cases} \]

代码实现如下:

1
2
3
4
5
6
7
int g(int n, int m, int x) {
return x <= n ? x : g(n, m, (x - 1 - n) * m / (m - 1) + 1);
}

int f(int n, int m, int k) {
return g(n, m, k * m);
}

注意到该函数可以非递归实现,给出优化后的代码:

1
2
3
4
5
6
7
int f(int n, int m, int k) {
int s = k * m - 1;
while (s >= n) {
s = (s - n) * m / (m - 1);
}
return s + 1;
}