约瑟夫环问题求解

一、概述

约瑟夫环问题(Josephus)是考察队列的一个经典问题，通常可用循环队列解决，时间复杂度O(m*n)，通过数学递推的解法具有O(n)的时间复杂度，是一个很高效的算法。

二、算法原理

约瑟夫环的递推公式：

那么这两个公式有什么不同？ 首先可以肯定的是这两个公式都正确。公式1，得到的是以0～n-1标注的最终序号；公式2得到的就是正常的1~n的序号。下面我们就分别推导两个公式。 公式1的推导： 给出一个序列，从0～n-1编号。其中，k代表出列的序号的下一个，即k-1出列。 $$ a: 0, 1, …, k-1, k, k+1, …, n-1 $$ 那么，出列的序号是(m-1)%n，k=m%n（这个可真的是显而易见）。出列k-1后，序列变为 $$ b: 0, 1, …, k-2, k, k+1, …, n-1 $$ 然后，我们继续从n-1后延长这个序列，可以得到 $$ c': 0, 1, …, k-2, k, k+1, …, n-1, n, n+1, …, n+k-2 $$ 我们取从k开始直到n+k-2这段序列。其实这段序列可以看作将序列b的0~k-2段移到了b序列的后面。这样，得到一个新的序列 $$ c: k, k+1, …, n-1, n, n+1, …, n+k-2 $$ 好了，整个序列c都减除一个k，得到 $$ d: 0, 1, …, n-2 $$ c序列中的n-1, n, n+1都减除个k是什么？这个不需要关心，反正c序列是连续的，我们知道了头和尾，就能知道d序列是什么样的。

因此，从序列a到序列d，就是一个n序列到n-1序列的变化，约瑟夫环可以通过递推来获得最终结果。ok，继续向下。剩下的就是根据n-1序列递推到n序列。假设在n-1序列中，也就是序列d中，我们知道了最终剩下的一个序号是x，那么如果知道了x转换到序列a中的编号x'，不就是知道了最终的结果了么？

下面我们就开始推导出序列a中x的序号是什么。

• d->c，这个变换很容易，就是x+k；
• c->b，从b->c，其实就是0~k-2这段序列转换为n~n+k-2这段序列，那么再翻转回去，简单的就是%n，即(x+k)%n。%n以后，k~n-1这段序列值不会发生变化，而n~n+k-2这段序列则变成了0~k-2；这两段序列合起来，就是序列b。

于是，我们就知道了 $$ x'=(x+k)\%n $$并且，$$ k=m\%n $$所以$$ x'=(x+m\%n)\%n=(x+m)%n $$公式1就出来了：$$ f[i]=(f[i-1]+m)\%i $$当然，i=1就是特殊情况了，$f[1]=0$。这里还有一个小问题。也许你会迷惑为什么$x'=(x+m\%n)\%n=(x+m)\%n $中的$\%n$变成公式中 $ f[i]=(f[i-1]+m)\%i $中的 $ \%i $ ？其实这个稍微想想就能明了。我们%n就是为了从序列c转换到序列b——这是在n-1序列转换成n序列时%n；那么从n-2转换到n-1呢？不是要 $ \%(n-1) $了吗？所以这个值是变量，不是常量。

好了，这个最后需要注意的就是从一开始，我们将n序列从$0~n-1$编号，所以依据公式1得出的序号是基于0开始的。

三、求解出圈序列(线段树)

如果需要输出出圈的序列，常规求解算法为队列的解法，可以用循环队列优化空间，但时间复杂度仍未 O(m*n), 可以采用线段树（排名树）的方法提高效率。通过线段树记录每个区间内还没有出圈的元素的个数，每次通过取模运算求出需要出列的元素从1开始的相对位置，再从线段树中找出该元素，并更新线段树。时间复杂度为O(n*logn)。参考 wikioi 1282 题，具体实现如下：

#include <cstdio>
using namespace std;

// segment tree.

int sum[120010];

void build(int l, int r, int rt)
{
    if (l == r) {
        sum[rt] = 1;
        return;
    }
    int m = (l+r) >> 1;
    build(l, m, rt << 1);
    build(m+1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void update(int p, int l, int r, int rt)
{
    sum[rt]--;
    if (l == r) {
        printf("%d ", l);
        return;
    }
    int m = (l+r) >> 1;
    if (p <= sum[rt << 1]) {
        update(p, l, m, rt << 1);
    } else {
        update(p-sum[rt<<1], m+1, r, rt << 1 | 1);
    }
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

int main(int argc, char **argv)
{
    int n, m;
    scanf("%d %d", &n, &m);
    build(1, n, 1);
    int seq = 1;
    for (int i = 1; i <= n; ++i) {
        seq = (seq+m-1) % sum[1]; // get the relative postion.
        if (seq == 0) {
            seq = sum[1];
        }
        update(seq, 1, n, 1);
    }

    return 0;
}

四 、参考：

1、http://hi.baidu.com/anywei/item/294351b5f432f144ba0e12f2

2、http://www.cnblogs.com/EricYang/archive/2009/09/04/1560478.html

Comments: