引言：
约瑟夫问题（有时也称为约瑟夫斯置换，是一个计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）
约瑟夫问题
N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
这个问题是在我刷剑指Offer时遇到的，看了很多大佬的解题，都是用数字在进行举例，看完还是有一些疑惑，直到看了这两篇文章（文章1、文章2）。这里换了个角度举例，或许会更清晰一些，欢迎大家讨论，并不吝赐教！
问题转换
既然约瑟夫问题就是用人来举例的，那我们也给每个人一个编号（索引值），每个人用字母代替。下面这个例子是N=8，m=6的例子。
我们定义F(n,m)表示最后剩下那个人的索引号，因此我们只关系最后剩下来这个人的索引号的变化情况即可。（注意：该思路只关心最终活着那个人的序号变化）
从8个人开始，每次杀掉一个人，去掉被杀的人，然后把杀掉那个人之后的第一个人作为开头重新编号：
- 第一次F被杀掉，人数变为7，G作为下一轮的开头（最终活下来的A的编号从0变成2）
- 第二次D被杀掉，人数变为6，E作为下一轮的开头（最终活下来的A的编号从2变成3）
- 第三次C被杀掉，人数变为5，E作为下一轮的开头（最终活下来的A的编号从3变成3）
- 以此类推，当值剩下A一个人时，他的编号必定为0！（这是重点，要圈起来）
最后活着的人的编号反推
我们现在知道了A的索引号的变化过程，那么我们反推一下从 N=7 到 N=8 的过程。如何才能将 N=7 的排列变回到 N=8 呢？我们先把被杀掉的 F 补充回来然后右移 m 个人，发现溢出了，再把溢出的补充在最前面，神奇了 经过这个操作就恢复了 N=8 的排列了。如下图所示：
因此我们可推出递推公式非 f(8,6) = (f(7,3) + 6) % 8，进行推广泛化后可以得到 f(n,m) = (f(n-1,m) + m) % n。
递推公式的导出
在以上的推导结果中再把 n=1 这个最初的情况加上，就能得到地推公式：
。
java代码实现
class Solution{
public int lastRemain(int n, int m) {
int pos = 0;//最后活下来的那个人的初始位置（这里是反向推导）
for (int i=2; i <= n; i++) {
pos = (pos + m) % i;//每次循环右移
}
return pos;
}
}
