约瑟夫问题

摘要

约瑟夫问题由来已久,而这个问题的解法也在不断改进,只是目前仍没有一个极其高效的算法(log以内)解决这个问题。

问题描述

n个人标号 逆时针站一圈,从 号开始,每一次从当前的人逆时针数 个,然后让这个人出局。问最后剩下的人是谁。

这个经典的问题由约瑟夫于公元1世纪提出,尽管他当时只考虑了 的情况。现在我们可以用许多高效的算法解决这个问题。

朴素算法

最朴素的算法莫过于直接枚举。用一个环形链表枚举删除的过程,重复 次得到答案。复杂度

简单优化

寻找下一个人的过程可以用线段树优化。具体地,开一个 的线段树,然后记录区间内剩下的人的个数。寻找当前的人的位置以及之后的第k个人可以在线段树上二分做。

线性算法

表示规模分别为 的约瑟夫问题的答案。我们有如下递归式

这个也很好推。你从0开始数k个,让第 个人出局后剩下 个人,你计算出在 个人中选的答案后,再加一个相对位移k得到真正的答案。这个算法的复杂度显然是 的。

int josephus(int n, int k) {
    int res = 0;
    for (int i = 1; i <= n; ++i) res = (res + k) % i;
    return res;
}

对数算法

对于k较小n较大的情况,本题还有一种复杂度为 的算法。

考虑到我们每次走k个删一个,那么在一圈以内我们可以删掉 个,然后剩下了 个人。这时我们在第 个人的位置上。而你发现这个东西它等于 。于是我们继续递归处理,算完后还原它的相对位置。得到如下的算法:

int josephus(int n, int k) {
    if (n == 1) return 0;
    if (k == 1) return n-1;
    if (k > n) return (josephus(n-1, k) + k) % n;//线性算法
    int res = josephus(n - n / k, k);
    res -= n % k;
    if (res < 0) res += n;//mod n
    else res += res / (k - 1);//还原位置
    return res;
}

可以证明这个算法的复杂度是 的。我们设这个过程的递归次数是 ,那么每一次问题规模会大致变成 ,于是得到

解这个方程得到

用泰勒级数搞一搞可以得到 。于是可以近似认为该算法的复杂度是


  转载请注明: Sshwy's Blog 约瑟夫问题

 上一篇
Stern-Brocot 树与 Farey 序列 Stern-Brocot 树与 Farey 序列
摘要 Stern-Brocot树是一种维护分数的优雅的数据结构。它分别由Moritz Stern在1858年和Achille Brocot 在1861年发现这个结构。 概述Stern-Borcot 树从两个简单的分数开始: \frac{
2019.07.17
下一篇 
扩展埃氏筛 扩展埃氏筛
摘要 本文介绍一种比欧拉筛更高效的筛法,扩展 Eratosthenes 筛法。 杜教筛适用范围较小,未充分利用积性。扩展埃氏筛要求对于任意质数 p, 是一个关于 p 的低阶多项式。对于任意 的指数
2019.07.13 Sshwy
  目录