约瑟夫问题:

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

算法1(Simple算法):

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

时间复杂度$O(nm)$

当n很小而m很大时,可以通过取膜将$O(nm)$优化为$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人的问题,其中原来的$2x-1$号变为了$x$号。计算出来的答案要$\times 2-1$

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

所以发现了递推公式:

$$ f(n)=\begin{cases}f(\frac{n}{2})\times2-1 & n \equiv 0(\mod 2) \\ f(\lfloor\frac{n}{2}\rfloor)\times 2 - 3 & n \equiv 0(\mod 2)\end{cases} $$

时间复杂度$O(log_2n)$

算法4:

对于算法2,我们发现有很多时候取膜并没有用。
那么我们可以合并很多个取膜。
然后就快了很多。
能过$n\le 10^9$,$m\le 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;
}

标签: 数论

添加新评论