Josephus Problem
问题描述
社团共有
n位成员参与破冰游戏，编号为0 ~ n-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字m，从0号成员起开始计数，排在第m位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员（赢家）的编号。
保证\(m\geq 1\), \(n \geq 1\) 以及
m, n为int类型。
问题分析
首先需要明确一个概念：我们要求的编号与索引是不同的，每次一次迭代的索引都是从0开始。但是注意到在迭代开始的时候，我们的索引与编号是完全一致的。那么就会引申出两种解法。
模拟过程
我们不妨建一个循环的链表，即最后链表的next指向head，然后不断模拟整个游戏的过程。这个方法必然能稳定得出正确的结果，但其时间复杂度在\(O(n^2)\)，空间复杂度在\(O(n)\)。当数据规模很大时它的表现就会比较差。
状态转移
对于圆这种可以无限循环的数据结构而言，有一个巧妙的方法是取模，然后构造两个并排的列表（中间用|隔开）：
| 0 | … | n-1 | | | 0 | … | n-1 |
|---|---|---|---|---|---|---|
| this | line | is | left | empty | for | purpose |
这样一来，给定任意一个要删除的索引k（k必然在0 ~ n-1之间，不失一般性我们假定k不在边界处） ，我们可以很简单地构造下一阶段的并排列表：
| n: | 0 | … | k | … | | | 0 | … | k | … |
|---|---|---|---|---|---|---|---|---|---|
| n-1: | k+1 | … | 0 | … | k-1 | | | k+1 | … |
我们可以总结出一个规律：对于每一次迭代，我们就相当于扔掉前面k个元素，再向后数对应n-1个，数完了以后再复制这n-1个构造出并排的列表。
定义\(f(x):\) 成员个数为\(x\)时赢家在并排列表中的 索引（由于是并排的，我们只需要关注前半部分就OK了），注意到赢家是不会被删除的，因此\(x\)的取值在 \(1, 2, 3, ..., n\)。
注意到\(f(x)\)有两个特殊之处：
- \(f(1) = 0\);
- \(f(n)\)就是我们最终要求的赢家的编号。
那么现在的任务就是去求得 \(f(n)\)，自然地，我们希望能找到一个合适的递推公式，这样就可以求解了。
当前成员人数为t时，我们用X表示被删除的编号，S表示即将成为索引为0的编号，*表示赢家的编号。具体过程如下：
t: | … | X | S | … | * | … | | | … |
|---|---|---|---|---|---|---|---|---|
t-1: | S | … | * | … | | | … |
注意到S在t-1的索引为0，在t的索引为 \(m\%t\)。于是乎，我们能找到两个状态之间的平移量：\(m\%t\)。已知*的索引在t-1状态时为\(f(t-1)\)，那么我们可以恢复出它在t状态时的索引：\(m\%t+f(t-1)\)。为防止越界，我们取模，得到状态转移方程
鉴于我们已知\(f(1)\)，我们可以直接写一个循环求解:
int solution(int n, int m) {
int f = 0;
for (int i = 2; i != n + 1; ++i)
f = (m % i + f) % i;
return f;
}
该算法时间复杂度\(O(n)\)，空间复杂度为\(O(1)\)。