关于约瑟夫环问题的公式解法的推导，我看了很多文章，其中推理过程各有千秋，所以写一写自己的推导过程。

问题描述

公式法

第一轮分析

先看第一轮出列的人是谁：

无论m和n哪个大，m%n都是下一轮的第一个人。

假设上一轮出列的人是 k 。

1
2
3

原序列:    {0···k-1 , k ,  k+1(就是m%n)···n-1}        //n个人
K出列:    {0···k-1 ,        , k+1(就是m%n)···n-1}    //n-1个人
⚠️重点标记⚠️ 最后我们会回来用到上面👆

这时候问题由 (m,n) 的退化成了 (m,n-1)的，其实每次退化，m都不会变。

所以我们可以直接说，问题从 F(n) 退化成了 F(n-1) 的。

我们只需要往下分析完F(n-1)的，问题就很清晰了。

第二轮分析

这一轮还有 n-1个数，重新编号肯定是 0到n-2呗，

k+1 变成了 0，k+2 变成了 1，

最后一个数 k+n-1 变成了 n-2。而我们都知道， k-1就是 k+n-1 。

这时候我们思考一个问题， 给你一个这一轮新编的序号 x 。你怎么算出它在第一轮序号？

是不是 (x+k+1)%n就可以？举几个例子：

x=0, (0+k+1)%n = k+1

x=1, (1+k+1)%n = k+2

x=n-2, (n-2+k+1)%n = k-1

这一步的分析告诉我们，如果我们求出 F(n-1)这个问题的解是 x，那 (x+k+1)%n 就是 F(n) 的解。

写成公式就是：

1	F(n) =[ F(n-1)+k+1 ]%n

综上可知

我们每轮都能得到一个结果x。用x可以推出它在上一轮的结果。

最后一轮F(1)的结果一定是0，

F(1), 无论m是几，n=1。m%1当然是0。

但是这个 0 ，是F(1)这个问题里的0!

它是上一层的几号？我们要一步步推回去才知道！

一层层反推上去，是不是就能最终得到，F(1) 里那个 0 ，对应的是 F(n) 里的几号？这个结果不就是答案吗？

看懵了？

有同学可能会说，反正最后一次F(0)结果肯定是 0 。那我一层层推回去得到 F(n)，岂不是这个问题的结果只和 n 有关？

看看由 F(n-1) 推出 F(n) 的公式！

1	F(n) =[ F(n-1)+k+1 ]%n

这里面，是只有 n 这一个变量吗？还有k啊！ k是什么？看⚠️重点标记⚠️ 啊。

k+1 就是 m%n !!!

所以推导公式其实就是

F(n) =[ F(n-1)+ m%n ]%n ==化简==> F(n) =[ F(n-1)+ m ]%n

所以这道题其实就是求函数

1 2	F(n) = [ F(n-1)+ m ]%n ,n>1 F(n) = 0, n=1

对着这公式代码写起来就太容易了吧？

int func(int n,int m){
    if(n==1)
        return 0;
    return (func(n-1,m)+m)%n;
}

其中的一些细节，还需要多琢磨几遍！

Adopting CC BY-NC-SA 4.0 License Agreement