【题解】约瑟夫环问题

就拿最原始的约瑟夫环问题来描述该类问题:

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个***方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须***，然后再由下一个重新报数，直到所有人都***身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

这里拿a, b, c, d, e, f, g, h, i, j 来模拟10个人，设m=3.
下图的意思呢，就是模拟这10个人玩这个游戏到最后一个人存活下来的整个过程。绿色行表示在n=*时，每个人的位置索引。因为在n=10时，数一个m，杀死了c之后，后面的继续从0开始数，此时剩9个人，从0开始数，相当于这又是一个全新的游戏，只不过现在只剩9个人，而这9个人此时的位置索引也发生了变动。

通过上图，我们可以很直观的看到，最终d存活了下来。那么，此时我们从下往上看图，看看每一轮d的位置索引是什么情况。当n = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10时，d分别选择了位置索引为：0, 1， 1， 0， 3， 0， 3， 6， 0， 3。什么意思呢？可以这么理解，现在让你参与玩这个游戏，你不想死，怎么办呢，要是有1个人参与，ok，你不用死。要是总共2个人参与，你必须选择位置索引为1才能存活下来；要是总共有3个人参与，你必须选择位置索引为1才能存活；要是总共有4个人，你必须选择0......依次类推。你必须通过n来推算自己的索引位置才可以存活下来。

那么我们此时用表示个人的时候，能够存活的位置索引。由上图显然可以得到。但是我们要找的是通项公式。从图中也可以很直观的看到，n=9时d的位置索引就是n=10时循环左移了3位。那么可以得到，因为是循环左移，所以需要加一个取余，防止越界。同理可以得到，。
从始至终，只是一个常量。所以不影响结论。所以约瑟夫环问题的公式：

虽然不是在证明这个公式，但是通过这种方式，希望你能理解这个公式。