本贴头一次做约瑟夫环问题，看了很多人的递推公式解析，最火的CSDN那一篇也还是没看懂，我觉得不从映射的角度去找新旧索引的关系，难以理解约瑟夫环问题。。。求助于Deepseek，发现Deepseek生成的解答方式很便于理解，也很具有逻辑，因此想把这条记录分享出来。

解答是从新旧下标的关系去解答，搜寻映射方式，下面看deepseek生成原文
 

初始理解约瑟夫问题

首先，约瑟夫问题描述的是：有N个人围成一圈，编号从0到N-1（或者从1到N，这里假设从0开始），从第一个人开始报数，每数到M的那个人就被淘汰出局，然后从下一个人重新开始报数，直到所有人都被淘汰。问题是：给定N和M，确定最后剩下的那个人的初始编号。

简单例子

让我们用一个简单的例子来理解：

例子：N=5，M=3

• 初始序列：0, 1, 2, 3, 4

• 淘汰顺序：

  1. 从0开始数，0(1), 1(2), 2(3) → 淘汰2，剩下：0, 1, 3, 4

  2. 从3开始数，3(1), 4(2), 0(3) → 淘汰0，剩下：1, 3, 4

  3. 从1开始数，1(1), 3(2), 4(3) → 淘汰4，剩下：1, 3

  4. 从1开始数，1(1), 3(2), 1(3) → 淘汰1，剩下：3

• 最后剩下的是3。

递推公式的理解

现在，我们需要理解为什么递推公式是：

f(N, M) = (f(N-1, M) + M) % N

并且初始条件是f(1, M) = 0（因为只有一个人时，他就是胜利者，编号为0）。

关键思想

1. 问题规模缩小：每次淘汰一个人后，问题就从N个人变为N-1个人。

2. 下标的变化：淘汰一个人后，剩下的人会重新排列，我们需要找到新旧下标之间的关系。

具体解释

假设我们有N个人，编号为0到N-1，数到M的人被淘汰。第一个被淘汰的人是(M-1) % N（因为从0开始数）。淘汰后，剩下的N-1个人是：

• 旧编号：M % N, (M+1) % N, ..., (M+N-2) % N

• 新编号：0, 1, ..., N-2

现在，我们需要找到一个映射，将N-1个人的解（即f(N-1, M)）映射回N个人的解。

• 在新编号中，胜利者的位置是f(N-1, M)。

• 这个胜利者在旧编号中的位置就是 (f(N-1, M) + M) % N。

为什么？

因为新编号的0对应旧编号的M % N，新编号的1对应旧编号的(M+1) % N，...，所以新编号的k对应旧编号的(M + k) % N。因此，新编号的f(N-1, M)对应旧编号的 (f(N-1, M) + M) % N。

从新和旧具体编号对应也能知道这个递推方式了，我觉得这种方式比较好理解