约瑟夫问题的一些解法

发表于 2017-10-09 分类于题解

约瑟夫问题：

有n个人，编号为 $1. . n$ ，从第1个人开始报数，报到m的人离开，求最后的幸存者。

算法1（Simple算法）：

用队列模拟，可以算出每一次出队的人。

时间复杂度 $O (n m)$

当n很小而m很大时，可以通过取膜将 $O (n m)$ 优化为 $O (n^{2})$

注：

编号整体 $+ x$ 的意思就是1号变为 $x + 1$ 号，2号变为 $x + 2$ 号......， $n - x$ 号变为 $n$ 号， $n - x + 1$ 号变为1号，...... $n$ 号变为 $x$ 号。

编号整体 $- x$ 的意思就是1号变为 $n - x + 1$ 号， $2$ 号变为 $n - x + 2$ 号......， $x$ 号变为 $n$ 号， $x + 1$ 号变为1号，...... $n$ 号变为 $n - x$ 号。

算法2：

设 $f (n)$ 表示n个人报数最后的幸存者。首先第一次第m个人离开，剩下的 $n - 1$ 人编号整体-m，然后就变成了一个n-1个人的问题。算完以后整体右移回去这m位，如果 $> n$ 就 $- n$

所以发现递推式： $f (n) = (f (n - 1) + m - 1) \mod n + 1$ ### 算法3( $m = 2$ )：当 $m = 2$ 时，首先会将所有偶数编号的人移出去。

然后如果 $n$ 是个偶数，则下一次会移出3，等等，也就是说可以直接化为n/2人的问题，其中原来的 $2 x - 1$ 号变为了 $x$ 号。计算出来的答案要 $\times 2 - 1$

如果是个奇数，下一次会让1号出去，我们就可以直接把1号移出去然后把其它的奇数编号重编号 $2 x - 3$ 变为 $x$ ，就化为了 $⌊ \frac{x}{2} ⌋$ 的问题。算出的答案要 $\times 2 - 3$

所以发现了递推公式：

$\begin{matrix} (1) & f (n) = {\begin{cases} f (\frac{n}{2}) \times 2 - 1 & n \equiv 0 (\mod 2) \\ f (⌊ \frac{n}{2} ⌋) \times 2 - 3 & n \equiv 0 (\mod 2) \end{cases} \end{matrix}$

时间复杂度 $O (l o g_{2} n)$ ### 算法4：对于算法2，我们发现有很多时候取膜并没有用。那么我们可以合并很多个取膜。然后就快了很多。能过 $n \leq 10^{9}$ , $m \leq 10^{5}$

算法3,4的代码：

/*
Author: CNYALI_LK
LANG: C++
PROG: mayuri.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
#define end(...) {printf(__VA_ARGS);exit(0);}
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs

int yues(int x){//m=2
    if(x==1)return 1;
    else if(x&1)return 2*yues(x>>1)+1;
    else return 2*yues(x>>1)-1;
}
int main(){
    freopen("mayuri.in","r",stdin);
    freopen("mayuri.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T){
    int n,m;
    scanf("%d%d",&n,&m);
        int s=1,t=1,k;
        while(t<=n){
            k=(t-s)/(m-1);
            if(t+k>=n){
                s=s+m*(n-t);
                printf("%d\n",s);
                break;
            }
            s+=m*k;//压缩多个(+ m-1) mod n + 1 
            t+=k;
            ++t;
            s=(s+m-1)%t+1;
        }
        --T;
    }
    return 0;
}