约瑟夫环问题

基本问题描述：

已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。那么我这里主要研究的是最后一个出列的人的序号要怎么确定。

第一种：模拟

同方法名所说，简单的数组模拟链表，就不多讲了，贴上自己的代码，复杂度O(nm)。

 1 #include<bits/stdc++.h>
 2 #define N 20010
 3 using namespace std;
 4 int n,m,i,j,l[N],r[N],now;
 5 int main()
 6 {
 7     scanf("%d%d",&n,&m);
 8     for(i=1;i<=n;i++)l[i]=i-1,r[i]=i+1;
 9     r[0]=r[n]=1,l[1]=n,now=0;
10     for(i=n;i;i--)
11     {
12         for(j=m;j;j--)now=r[now];
13         l[r[now]]=l[now],r[l[now]]=r[now];
14     }
15     printf("%d
",now);
16     return 0;
17 }

第二种：找规律，用数学方法解决

表格中的n指总人数，m指报到m的人出圈

m	1	2	3	4	5	6
1	1	2	3	4	5	6
2	1	1	3	1	3	5
3	1	2	2	1	4	1

通过更多的数据（我就不一一列举了），可以发现一个规律f(x)=(f(x-1)+m-1) mod x+1,f(0)=0（f(x)指有x个人的时候）。由此可以得到一个O(n)的做法，代码如下。（当然我在最后会证明这个式子的正确性，不想看的可以不看）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,i,now;
 4 int main()
 5 {
 6     scanf("%d%d",&n,&m);
 7     for(i=1;i<=n;i++)now=(now+m-1)%i+1;
 8     printf("%d
",now);
 9     return 0;
10 }

第三种：在第二种方法的基础上用数学方法优化

我们可以发现当n很大的时候，大部分f(n)=f(n-1)+m，这样就要花很多步去加m，所以可以考虑用乘法把这些步骤一步到位，而当f(n)=f(n-1)+m成立时，f(n-1)+m-1<n，所以不妨设f(n+x+1)恰好不满足f(n+x)+m,即f(n)+x*m-1<n+x，此时f(n+x+1)=(f(n)+x*m+m-1)mod(n+x+1)+1。合并同类项后，(m-1)*x<n-f(n)+1，即(m-1)*x<=n-f(n)。

当m=1时，活下来的人一定是n

当m>1时，x<=(n-f(n))/(m-1)，当n+x>=当前总人数时，循环停止，好了说了半天，发代码，自己看。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,i,fi,x;
 4 int main()
 5 {
 6     scanf("%d%d",&n,&m);
 7     if(m==1)printf("%d
",n);
 8     else
 9     {
10         for(i=fi=x=0;i+x<n;)
11             i+=x+1,fi=(fi+x*m+m-1)%i+1,x=(i-fi)/(m-1);
12         printf("%d
",fi+(n-i)*m);
13     }
14     return 0;
15 }

最后，原理解释：

首先，n个人里第一个报m的一定是(m-1)mod n+1这个人，这个人拿走后序列为（先把这个人的位置当作k）

a k+1,k+2,k+3,..., n-1, n, 1,...,k-2,k-1

而n-1个人的序列是b 1, 2, 3,...,n-1-k,n-k,n-k+1,...,n-2,n-1

然后一对比就发现ai=(bi+k-1) mod n+1,所以f(i)=(f(i-1)+(m-1)mod n)mod n+1，即f(i)=(f(i-1)+m-1)mod n+1