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

c/c++

浏览数:174

2019-3-28

AD:资源代下载服务

约瑟夫问题一般的解法即用循环模拟报数,但是此这样的方法时间复杂度为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;  
}