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 总结

注:本文所有数字都从 00 开始

约瑟夫问题

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

模拟 O(n logn)

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

循环链表 O(n m)

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

数据结构维护 O(n lgn)

ii (从 00 开始) 次操作, 将自杀的人 (第 xx 小) 从列表中清除, 则下一次查询编号第 小的人.

可以理解为, 将 00n1n-1 存在一个数组里. 第 ii 次操作将自杀的人 (设下标为 xx) 从数组中删去 (后面位置的要前移), 则操作之后数组的长度为 ni1n-i-1. 则第 i+1i + 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]
}

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

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

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

递归式1 O(n)

考虑 n=8n = 8, m=3m = 3 的情况
0 1 2 3 4 5 6 7
0 1 3 4 5 6 7
   
5 6 0 1 2 3 4
即如果已知 n=7n = 7, m=3m = 3 时的答案为 xx, 那么 即为 n=8n = 8, m=3m = 3 时的答案.

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

递归式2 O(logn)

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

0 1 2 3 4 5 6 7
0 1 3 4 6 7
   
2 3 4 5 0 1

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

特例 m=2

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

扩展约瑟夫问题

求第 kk (从 00 开始) 个自杀的人的编号

n=8n=8, m=3m=3 时为:2,5,0,4,1,7,3,62, 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 (nnkk 都减小 11)

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

递推式2 O(logn)

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

下面是 n=8n=8, m=3m=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
设第 pp 次报数的是 yy, 令 p=m×a+bp = m \times a + b, 其中 (a=n/m)(a = \lfloor n/m\rfloor), 则之前死了 aa 个人.
若本次报数之后 yy 没死, 则下次报数 q=p+na=n+(m1)×a+bq = p + n - a = n + (m - 1) \times a + bb<n1b<n-1,
移项, 得 a=qnbm1=qnm1a = \lfloor\frac{q-n-b}{m-1}\rfloor=\lfloor\frac{q-n}{m-1}\rfloor, 故 p=qna=qn+qnm1=(qn)mm1p = 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)×m1)f(n, m, k) = g(n, m, (k+1)\times m - 1).
g(n,m,x)={x,x<ng(n,m,(qn)mm1),k0.g(n, m, x) = \begin{cases} x, & x<n \\ g(n, m, \lfloor\frac{(q-n)\cdot m}{m-1}\rfloor), & k \geq 0 \end{cases}.

写成 c++ 为

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

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

特例 m=2

f(n,2,k)=2n(2n2k1)(2lgn/(2n2k2)+1sgnn/2k+1).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).
其中 sgnsgn 为符号函数, 正数返回11, 负数返回1-1, 00返回00.

参考资料