约瑟夫问题的数学解(C++)

约瑟夫问题一般的解法即用循环模拟报数，但是此这样的方法时间复杂度为O(mn)，m为报的数，n为人数，在规模较大时旺旺效率并不好，我们可以用数学方法来讲问题进行简化，用O(n)的复杂度解决问题

初始的约瑟夫问题设为F(n),我们假设从第0人开始报数，第一个出去的人即第m-1个人，淘汰一人之后我们可以看作是一个n-1人的约瑟夫问题，但是其初始报数位置并不是从头开始，而是从第m%n处开始，我们可以将序号平移，将m%n处的人移动到第一位，便可以变成一n-1人的约瑟夫环F(n-1),则F(n-1)中编号为k的人刚才的序号为(k+m)%n,

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

类似的，我们反过来看,当只有一个人时

F(1)=0

这个人即为最后胜利的人，那么这个人在上一次报数中所在的位置为

F(2)=(F(1)+m)%n

F(3)=(F(2)+m)%n

...

F(n)=(F(n-1)+m)%

即为此人最开始的编号

c++实现如下

#include<iostream>  
using namespace std;  
int main(int argc, char** argv) {  
    int n,k;  
    cin>>n>>k;  
    int r;  
    r=0;  
    for(int i=1;i<=n;i++){  
        r=(r+k)%i;  
    }  
    cout<<r+1<<endl;  
}