约瑟夫环递推公式推导

题目描述：

一共有 n 个人，编号为1，2，...，n，这些人围成一个圈子，然后指定一个数 m ，从 1 号开始，数到 m 的人出列，并且下一个人重新开始由 1 计数，问最后一个出列的人是几号？

解析：

1.通常这类问题会想到使用链表解决，每 m 个就删除一个节点

2.也可以用循环数组的方式，对数组的下标取模

对于以上两种方法都不适用于解决数目过于大的约瑟夫环问题，而对于约瑟夫环问题有一个简洁的递推公式：

f(n) = (f(n - 1) + m) % n（编号由 0 开始）

其中 f(n) 表示对于 n 个人的约瑟夫环问题的解（即最后一个出列的人的编号） 

推导过程：

1.设一共有 10 个人，且 m 取 7，进行推导：

首次序号，以及第一个人出列后的新报数序号如下：

能够发现，第一行的数列与第二行的数列有一个对应关系，为了方便统计规律，我们将编号从 0 开始，则：

很容易发现其规律：g(i, 10) = (g(i, 9) + 7) mod 10

其中，-1 < i < 10，i 是正整数，且 i != 6，g(i, n) 表示 n 人环中第 i 人的编号

有了这样的对应关系，10 人环的第二次出列的编号就可以由 9 人环的第一次出列的编号推导出来；

这样递推下去：

out(10, 2) <= out(9, 1)

out(10, 3) <= out(9, 2) <= out(8, 1)

.........

out(10, 10) <= out(9, 9) <= out(8, 8) <= ... <= out(1, 1)

其中 out(n, i) 为 n 人环中，第 i 个出列的编号

而 out(1, 1) = 0

有了以上的推导，我们已经知道能够将 n = 10 的约瑟夫环问题转化为一个 n = 1 的约瑟夫环问题（已知答案）

那么，如何将之一般化：

对任意的 n, m 将 n 个人从零开始编号，从一开始报数（对于从一开始编号的要注意进行适当处理）

设第 i 个人第一次报数到 m ，则其下一个 i + 1 编号的人也对应 m 这个编号；

i + 1 和 m 不一定的相等的，因为当 m > n 时，在一次报数中一个人可能会报两次，例：

这样，编号 0 的人同时也拥有编号 7，14

那么编号为 m 的人又重新开始报数，将之进行新的编号为 0；

那么 对于这个节点来说：(new_id + m) mod n = old_id， old_id 就是原数列的最小编号

即：f(n) = (f(n - 1) + m) % n，对于 f(1) = 0