约瑟夫环递归算法（C++）（逻辑分析） 

共计 3823 个字符，预计需要花费 10 分钟才能阅读完成。

题目：

n 个人围成一圈（编号从 1 到 n），从第 1 个人开始报数，报到 m 的人出列，从下一个人再重新报数，报到 m 的人出列，如此下去，直至所有人都出列。求最后一个出列的人的编号。

先给出 核心代码：

#include <iostream>
using namespace std;
int josephus(int n, int m) 
{if(n == 1) return 0;
	else return (josephus(n-1,m)+m ) % n;
}
 
int main() 
{
	int n, m;
	cin >> n >> m;
	int result = josephus(n, m);
	cout << result+1 << endl;
}

举例：n=9，m=4

思路分析 1：

1. 既然是递归，那么就是把复杂的问题一步一步分解为最基本、最简单的问题来解决。即把上例的 n =9，逐步分解为 n =8，n=7，n=6，……，n=2，n= 1 来解决。
2. 据我们观察，其中输入的变量有两个：一个是人数 n，一个是标号数 m。所以，假设我们求的递归函数就是 f(n,m)f(n,m)。又标号数 m 是固定的，每次计数的时候都是这个标号。
3. 递归说明，前一个项和后一个项肯定是有关系的，不然递归进行不下去。即 f(n,m)f(n,m)与 f(n−1,m)f(n−1,m)之间有一定关系

那么思路便已经建立，我们需要找到 f(n,m)f(n,m)与 f(n−1,m)f(n−1,m)之间的关系即可，即找到 n = 9 与 n =8，n= 8 与 n =7，……，n= 3 与 n =2，n= 2 与 n = 1 之间的关系。

既然是把复杂的问题一步一步分解为最基本、最简单的问题来解决，那我们便从 n = 1 的问题来一步步逆向推回去。

思路分析 2：

当 n = 1 时，f(1,m)f(1,m)：

当 n = 1 时，环中只有 1 个人（编号为 1），那么最后一个出列的一定是编号为 1 的人。为了跟之后的推导统一，我们这里得出的 result 不记为 1，而记为 0。所以，当 n = 1 时，result=0。

当 n = 2 时，f(2,m)f(2,m)：

当 n = 2 时，环中有 2 个人（编号为 1，2），那么最后一个出列的人可能编号为 1，也可能编号为 2，这要看 m 的奇偶决定。如果 m 为奇数，那么最后一个出列的是编号为 2 的人；如果 m 为偶数，那么最后一个出列的人是编号为 1 的人。

当 n = 3 时，f(3,m)f(3,m)：

当 n = 3 时，环中有 3 个人（编号为 1，2，3），那么最后一个出列的人可能编号为 1，可能编号为 2，也可能是编号为 3。

可以这样想，当在 m 确定的情况下，则当 n = 3 时，环中每个人依次报数，报到 m 的人就离开，那么报完一轮后，肯定走掉一个人，那么还剩 2 个人，即 n =2。用数学的语言说就是从 f(3,m)f(3,m)递推为 f(2,m)f(2,m)了，即每进行一轮，n 都减 1。

那么问题思路更加清晰了，就是找 f(3,m)f(3,m)和 f(2,m)f(2,m)之间的递推关系，我们用最笨的方法（穷举法）来 找规律：

先对比两张表格，为了方便看，我把上面两张表格合并了：

得出一张新的规律表格：(n= 3 确定)（编号为 0 即编号为 3）

非常容易的观察得到，递推规律为 f(n,m)=[f(n−1,m)+m]%nf(n,m)=[f(n−1,m)+m]%n
再把找到的这个规律代入 f(4,m)f(4,m)和 f(3,m)f(3,m)之间验证，发现也是正确的。即得出递推关系式。

为什么？

看到这里，你或许想问为什么递推关系式是 f(n,m)=[f(n−1,m)+m]%nf(n,m)=[f(n−1,m)+m]%n，我连找规律都没有找出来，又怎么归纳总结递推关系式？

其实，这背后有这样一种思想：
还是拿刚才那个例子说事：
总人数 n = 9 人，从编号为 1 的人开始报数，每报到 4 就把一人踢出去（m=4）。

此时，这些编号已经不能组成一个环，因为编号为 4 的地方产生了一个空位。之后的报数将总要考虑原编号 4 处的空位问题。

如何才能避免已经产生的空位对报数所造成的影响呢？

不过没有关系，因为下一次报数将从编号为 5 的人开始，我们可以将剩下的 8 个人组成一个新的环（5，6，7，8，9，1，2，3）。即，将 3 和 5 首尾相连，这样报数的时候就不用在意 4 的空位了。
但是新产生的环的数字并非连续的，报数时不像之前那样好处理了。

怎么处理新环数字非连续，报数无法简单用 [(当前编号)%n] 这个式子递推的问题？

所以现在我们必须借助存储结构得知下一个应该报数的现存人员编号。
接下来我们的目的是：使新环上的编号能够递推来简化我们之后的处理。
意思就是我们要改变新环上每个人的编号，从而来建立一种有确定规则的映射，达到映射之后数字可以递推的目的。且可以将在新环中继续按原规则报数得到的结果逆推出在旧环中的对应数字。

方法：将长度为 n - 1 的新环与 n - 1 个人组成的编号为 1~n- 1 的环一 一映射。

之前的例子，将剩余的 8 人与 8 人环（编号为 0 ~ 8）一 一映射。

注意，这里的旧环就是进行一轮（踢掉编号为 4 的人）之后的环，新环是按照上面的方法把剩下的 8 人进行重新编号（1~8），且让原来编号为 5 的人现在新的编号为 1，原来编号为 6 的人现在编号为 2（依此类推）。

这样新环的编号既解决了旧环编号不连续的问题，又解决了新编号与旧编号之间一一映射的关系，即(旧的编号)=[(新的编号)+m]%(旧的人数 n)(旧的编号)=[(新的编号)+m]%(旧的人数 n)

咦！这个式子好像有点眼熟？
对，就是刚才找规律总结出来的 f(n,m)=[f(n−1,m)+m]%nf(n,m)=[f(n−1,m)+m]%n

那再看看这个规律适不适用于第二轮、第三轮……

验证成功，每一轮与上一轮之间的关系都满足 f(n,m)=[f(n−1,m)+m]%nf(n,m)=[f(n−1,m)+m]%n，况且我们之前找规律的那张表也可以充分说明这个关系式的可靠性。
综上所述，约瑟夫递归算法全部讲解完成。
再贴一次代码方便查看：

#include <iostream>
using namespace std;
int josephus(int n, int m) 
{if(n == 1) return 0;
	else return (josephus(n-1,m)+m ) % n;
}
 
int main() 
{
	int n, m;
	cin >> n >> m;
	int result = josephus(n, m);
	cout << result+1 << endl;
}