Josephus Problem 约瑟夫问题

有趣的问题
  1. 约瑟夫问题
    1. 模拟 O(n logn)
    2. 循环链表 O(n m)
    3. 数据结构维护 O(n lgn)
    4. 递归式1 O(n)
    5. 递归式2 O(logn)
    6. 特例 m=2
  2. 扩展约瑟夫问题
    1. 递归式1 O(n)
    2. 递推式2 O(logn)
    3. 特例 m=2
  3. 参考资料

问题求解 Open Topic 总结

注：本文所有数字都从 \(0\) 开始

约瑟夫问题

\(n\) 个人 (编号为 \(0, 1, ..., n-1\)) 围成一个圈子, 从 \(0\) 号开始依次报数, 每数到第 \(m\) 个人, 这个人就得自杀, 之后从下个人开始继续报数, 直到所有人都死亡为止. 问最后一个死的人的编号.

模拟 O(n logn)

依次判断下一个人是否已经死掉, 直到找到第 \(m\) 个活着的人, 则为下一个需要自杀的人.
code by hengxin
因为每一轮都会减少 \(1/m\), 即变为原来的 \((m-1)/m\), 故总共会进行 \(\log_{\frac{m}{m-1}}n\) 轮, 每轮 \(\leq n\) 次.
因此时间复杂度为 \(O(n\times \log_{\frac{m}{m-1}}n)\)

循环链表 O(n m)

链表直接指向下一个活着的人, 这样链表跳 \(m\) 次即可.
code by hengxin
时间复杂度为 \(O(nm)\)

数据结构维护 O(n lgn)

第 \(i\) (从 \(0\) 开始) 次操作, 将自杀的人 (第 \(x\) 小) 从列表中清除, 则下一次查询编号第 \((x + m - 1) \bmod (n - i - 1)\) 小的人.

可以理解为, 将 \(0\) 到 \(n-1\) 存在一个数组里. 第 \(i\) 次操作将自杀的人 (设下标为 \(x\)) 从数组中删去 (后面位置的要前移), 则操作之后数组的长度为 \(n-i-1\). 则第 \(i + 1\) 次操作要删去下标为 \((x + m - 1) \bmod (n - i - 1)\) 的人. 

1
2
3
4
5
6
for (int i = 0; i < n; ++i)
	vec.push_back(i);
for (int x = 0, i = 0; i < n; ++i) {
	x = (x + m - 1) % (n - i);
	vec.erase(vec.begin() + x); // 第 i 次自杀的是 vec[x]
}

但维护数组代价太大, 而下标即为第几小, 故可以用数据结构维护.
使用二叉搜索树, 需要的操作有：建树、删除、查询第 \(k\) 小 (听说支持查询第 \(k\) 小的应该叫排序统计树)

建树操作直接二分递归, 时间复杂度\(O(n)\).
删除操作有点复杂见算法导论 (大概思想为, 如果节点 \(x\) 只有一个孩子就直接提上来; 否则找到 \(x\) 的后继 \(y\), 即 \(x\) 的右子树中最左边的节点, 然后将用 \(y\) 替换 \(x\), 用 \(y\) 的右子树替换 \(y\)). 时间复杂度 \(O(\log n)\).
查询操作需要记录每个节点的 size, 即子树中节点的个数. 如果 \(k \leq size[left\_child]\), 那么查询左子树; 如果 \(k > size[left\_child] + 1\), 那么查询右子树; 否则 \(x\) 就是要找的点, 时间复杂度 \(O(\log n)\). 而删除操作最多只会更改 \(\log\) (层数) 个节点, 也是 \(O(\log n)\) 的.

复杂度为 \(O(n\times \log n)\).
可以看算法导论思考题 14-2 (红黑树)

递归式1 O(n)

考虑 \(n = 8\), \(m = 3\) 的情况
0 1 2 3 4 5 6 7
0 1    3 4 5 6 7
　　　\(\uparrow (x+m)\bmod n\)
5 6    0 1 2 3 4
即如果已知 \(n = 7\), \(m = 3\) 时的答案为 \(x\), 那么 \((x+m)\bmod n\) 即为 \(n = 8\), \(m = 3\) 时的答案.

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

时间复杂度为 \(O(n)\)

递归式2 O(logn)

当 \(m\) 远大于 \(n\) 时, 可以简化操作. 考虑一轮, 则有 \(\lfloor\frac{n}{m}\rfloor\times m\) 个人报过数, 并死了 \(\lfloor\frac{n}{m}\rfloor\) 个人

0 1 2 3 4 5 6 7
0 1    3 4    6 7
　　　\(\uparrow \lfloor ((x-n\bmod m) \bmod (n-\lfloor n/m \rfloor))\times m / (m - 1)\rfloor\)
2 3    4 5    0 1

故 \(f(n, m) = \begin{cases} 0, & n = 1 \\ (f(n-1, m) + m) \bmod n, & 1 < n < m \\ \left\lfloor \frac{(f(n-\lfloor n/m \rfloor, m)-n\bmod m) \bmod (n-\lfloor n/m \rfloor))\times m}{m - 1}\right\rfloor, & n \geq m \end{cases}.\)

先用第三个式子, 把 \(n\) 降到 \(m\) 的数量级, 时间复杂度 \(O(\log_{\frac{m}{m-1}}\frac{n}{m})\); 再用前两个式子在 \(O(m)\) 求出答案.
总时间复杂度为 \(O(m + \log_{\frac{m}{m-1}}\frac{n}{m})\)

特例 m=2

\(f(n, 2) = 2\times (n - 2^{\lfloor\log_2 n\rfloor})\)

扩展约瑟夫问题

求第 \(k\) (从 \(0\) 开始) 个自杀的人的编号

如 \(n=8\), \(m=3\) 时为：\(2, 5, 0, 4, 1, 7, 3, 6\)

递归式1 O(n)

0 1 2 3 4 5 6 7
5 6    0 1 2 3 4 (\(n\) 和 \(k\) 都减小 \(1\))

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

时间复杂度为 \(O(n)\)

递推式2 O(logn)

知第 \(k\) 个自杀的人为第 \((k + 1) \times m - 1\) 个报数的人. 即我们已知某人某个报数的位置, 且已知前 \(n\) 个报数的人一定是 \(0\) 到 \(n-1\), 想推出此人的编号.

下面是 \(n=8\), \(m=3\) 时的报数序列, 其中加粗的为自杀的人和位置.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 0 1   3    4    6   7   1    3   6    7    3   6   3    6    6   6
设第 \(p\) 次报数的是 \(y\), 令 \(p = m \times a + b\), 其中 \((a = \lfloor p/m\rfloor)\), 则之前死了 \(a\) 个人.
若本次报数之后 \(y\) 没死, 则下次报数 \(q = p + n - a = n + (m - 1) \times a + b\) 且 \(b<m-1\),
移项, 得 \(a = \lfloor\frac{q-n-b}{m-1}\rfloor=\lfloor\frac{q-n}{m-1}\rfloor\), 故 \(p = q - n + a = q - n + \lfloor\frac{q-n}{m-1}\rfloor = \lfloor\frac{(q-n)\cdot m}{m-1}\rfloor\).

故 \(f(n, m, k) = g(n, m, (k+1)\times m - 1)\).
而 \(g(n, m, x) = \begin{cases} x, & x<n \\ g(n, m, \lfloor\frac{(x-n)\cdot m}{m-1}\rfloor), & x \geq n \end{cases}.\)

写成 c++ 为 

1
for (x = (k + 1) * m - 1; x >= n; x = (x - n) + (x - n) / (m - 1));

操作抽象一下就是, 如果知道某次报数的位置, 就可以知道上一次报数的位置, 所以最多往前跳 \(\log_{\frac{m}{m-1}}n\) (轮数) 就能跳到第一轮. 因此时间复杂度 \(O(\log_{\frac{m}{m-1}}n)\).

当 \(m\to \infty\) 时，循环时每次 \(x\) 会减少 \(n\)，故时间复杂度为 \(O(\frac{mk}{n})\).

特例 m=2

\(f(n, 2, k) = 2n-(2n-2k-1)(2^{\left\lceil \lg\lceil n/(2n-2k-2)\rceil\right\rceil + 1}-sgn\left\lceil\frac{\lceil n/2\rceil}{k+1}\right\rceil).\)
其中 \(sgn\) 为符号函数, 正数返回\(1\), 负数返回\(-1\), \(0\)返回\(0\).

参考资料

组合数学 problem solving