约瑟夫问题的一些解法

约瑟夫问题:

有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的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
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;
}