约瑟夫环问题

约瑟夫环问题：一圈共有N个人，开始报数，报到M的人自杀，然后重新开始报数，问最后自杀的人是谁？

解法

首先看到题目，可以抽象出核心问题，我们记为f(n,m)，表示n个人报数m的最终结果，很自然我们可以知道当第一个报数到m的人去除之后，所有人数变为n-1，之后又重新开始1-m的报数，这时问题迭代为$f(n-1,m)。但是我们要注意到，这个迭代中最终结果表示的差异，因为n和n-1的定义顺序可能不是同一点开始的。f(n,m)表示的最终结果p为n的某个序列号，而f(n-1,m)中的结果q是n-1的某个序列号。因此问题又转化为找出p和q的对应关系，也就是如何从f(n,m)转化为f(n-1,m)。

示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

原序列      剔除m的序列



1               n-m+1
2               n-m+2
.                   .   
.                   .   
.                   .   
m-1             n-1
m
m+1            1   
.                   .   
.                   .   
.                   .   
n-1           n-m-1
n n-m ``` 可以看出```f(n-1,m)```中元素k对应的```f(n,m)```中的元素序列为```(k+m)%n``` 则有迭代关系式：```f(n,m)=(f(n-1,m)+m)%n```

### 代码

java public class Solution {

1
2
3
4
5
6
7
8

public int JosephCircle(int n, int m)
{ if(n==0||m==0)return -1;
    int ret=0;
    for(int i=2;i<=n;i++)
    { ret=(ret+m)%i;
    }   
   return ret;
}

} ```