约瑟夫环问题

队列模拟

#include<queue>
queue<int>ql;
int n=read(),k=read();
for(int i=1;i<=n;i++){
    q.push(i);
}
//开始操作
int now=1;//用来计数 当now == k的时候满足条件 让q.front() 输出并出列
while(q.size()){
    if(now==k){
        cout<<q.front()<<" ";
        q.pop();
        now=1;//初始化
    }
    else{//如果不满足是第k个, 则将队头转移到队尾
        now++;
        q.push(q.front());
        q.pop();
    }
}

公式法

f(10,3)=(f(9,3)+3)%10
∴ 从n中依次删去第k的数子
f(n,k)=(f(n-1,k)+k)%n

//函数的两种实现方式
int josephus(int n,int k){
    if(n==1)return 0;
    return (josephus(n-1,k)+k)%n;
}
//第二种
int josephus(int n,int k){
    //从底层向上推
    int value=0;//value 即为f(0,k) -> 向上递推到 f(m,k)
    for(int i=1;i<=n;i++){//从n 一直到 1推出答案 共n次
        value=(value+k)%i; //i即使n的变化值
    }
    return value;
}
int n=read(),k=read();
cout<<josephus(n,k)+1<<endl;