约瑟夫环详解

第n个出列  ？ ---> 0（**）

从上面可以总结规律：

1.  f(*) = (f(**)+m)%n  n指当前未出列元素的个数

2. f(**) 每次都是减少最右边的元素，所以最后一个元素为0

通过以上两个规律就可以进行求解：

最后一个出列的元素为0，即

f(**)(1) = 0; 则 f(*)(1) = (f(**)(1)+3)%1;

因为下一次出列是按照f(**)中的元素进行出列的，所以f(*)(1)序号与f(**)(2)序号相同，即：

f(**)(2)=f(*)(1); 同理可以求出f(*)(2); f(*)(2) = (f(*)(1)+3)%2;

最后得出公式 f(*)(1)=(0+m)%n;  f(*)(n) = (f(*)(n-1)+m)%n; 

扩展 倒数第k个出列的肿么求呢?  

其实挺简单，只要把初始条件换一下，继续套用上面总结出来的公式就ok了。

f(**)（k） = k-1;

f(*)(k)=(f(**)（k）+m)%n;  f(*)(n) = (f(*)(n-1)+m)%n;