首先，可以很简单的得出a[1]=0，然后我们开始找规律，得出a[i]=(a[i-1]+m)%i。正确代码如下：

#include<iostream> using namespace std; struct node{ int data; node *pre,*next; }; int main(){ node *head,*r,*p,*temp; head=new node; head->data=0; head->pre=head; head->next=head; r=head; int n,m; cin>>n>>m; for(int i=1;i<n;i++){ p=new node; p->data=i; p->next=r->next; p->pre=r; p->next->pre=p; p->pre->next=p; r=p; } for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ head=head->next; } temp=head; head->pre->next=head->next; head->next->pre=head->pre; head=head->next; delete temp; } cout<<head->data; return 0; }

约瑟夫问题，或称“约瑟夫环”，又名“丢手绢问题”。偶然碰到了这么一个问题，又了解到了它的来龙去脉，顿时十分感兴趣。在思考了一段时间后，我觉得有必要写下此文，纪念和传播这道经典的算法题，同时也附带我个人一些浅薄的思考和理解，与诸君分享。 这道算法题有着深刻的时代背景，它起源于一个非常惨烈的故事： 据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个**方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须**，然后再由下一个重新报数，直到所有人都**身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是一开始要站在什么地方才能避免**？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。 第一次看见约瑟夫问题时是在学python

#include<iostream> using namespace std; const int qmaxsize=1000010; int q[1000010]; int head,tail; void init(){ head=tail=0; } void push(int x){ tail=(tail+1)%qmaxsize; q[tail]=x; } void pop(){ head=(head+1)%qmaxsize; } int front(){ return q[(head+1)%qmaxsize]; } int back(){ return q[tail]; } bool empty(){ return headtail; } int size(){ return (tail+qmaxsize-head)%qmaxsize; } void clear(){ head=tail; } bool full(){ return (tail+1)%qmaxsizehead; } int main(){ init(); int n,k; cin>>n>>k; for(int i=0;i<=n-1;i++){ push(i); } while(size()!=1){ for(int i=1;i<k;i++){ push(front()); pop(); } pop(); } cout<<front(); return 0; }

#include <bits/stdc++.h> using namespace std; const int qmaxzie=1000000; int q[1000010]; int head,tail; void init(){ head=tail=0; } void push(int x){ tail=(tail+1)%qmaxzie; q[tail]=x; } void pop(){ head=(head+1)%qmaxzie; } int front(){ return q[(head+1)%qmaxzie]; } int beck(){ return q[tail]; } bool empty(){ return head==tail; } int size(){ return (tail+qmaxzie-head)%qmaxzie; } void clear(){ head=tail; } int main(){ init(); int n,k; cin>>n>>k; for(int i=0;i<n;i++){ push(i); } while(size()!=1){ for(int i=1;i<k;i++){ push(front()); pop(); } pop(); } cout<<front(); return 0; }

#include<bits/stdc++.h> using namespace std; struct node{ int data; node *next; }; int main(){ int n,m; cin>>n>>m; node *head,*r,*p; head=new node; head->next=NULL; r=head; for(int i=0;i<n;i++){ p=new node; p->data=i; p->next=NULL; r->next=p; r=p; } r->next=head->next; p=head->next; for(int i=1;i<n;i++){ for(int j=1;j<=m-2;j++){ p=p->next; } p->next=p->next->next; p=p->next; } cout<<p->data; return 0; }

或许可用数组来做静态链表 方式如下： #include<bits/stdc++.h> using namespace std; const int N =1e6; int a[N+1]; int main(){ int n,x; cin>>n>>x; for(int i=1;i<=n;i++) //里面的数据是下个的下标 a[i]=i+1; a[n]=1; int prev=1,now=1; while((n--)>1){ for(int i=1;i<x;i++){ prev=now; now=a[prev]; } a[prev]=a[now]; now=a[prev]; } cout<<now-1; //because 我的下标从1开始 return 0; }

#include<bits/stdc++.h> using namespace std; int n,m,x; queue<int> q; int main(){ cin>>n>>m; for(int i=0;i<n;i++)q.push(i); while(q.size()>1){ x++; if(x==m){ x=0; } else{ q.push(q.front()); } q.pop(); } cout<<q.front(); return 0; }

#include <bits/stdc++.h> using namespace std;int main() {int n,m;cin>>n>>m;queue<int>q;for(int i=0;i<n;i++){q.push(i);}while(q.size()>1){for(int i=1;i<=m-1;i++){q.push(q.front());q.pop();}q.pop();}cout<<q.front();}

#include<iostream> using namespace std; int main(){ int a[1000005]={0}; int n,m; cin>>n>>m; a[1]=0; for(int i=2;i<=n;i++){ a[i]=(a[i-1]+m)%i; } cout<<a[n]; return 0; }

#include <iostream> using namespace std; int josephus(int n, int m) { int pos = 0; // 最后剩下的人的位置 for (int i = 2; i <= n; ++i) { pos = (pos + m) % i; } return pos; } int main() { int n, m; cin >> n >> m; cout << josephus(n, m) << endl; return 0; }

#include <bits/stdc++.h> using namespace std; const int qmaxzie=1000000; int q[1000010]; int head,tail; void init(){ head=tail=0; } void push(int x){ tail=(tail+1)%qmaxzie; q[tail]=x; } void pop(){ head=(head+1)%qmaxzie; } int front(){ return q[(head+1)%qmaxzie]; } int beck(){ return q[tail]; } bool empty(){ return head==tail; } int size(){ return (tail+qmaxzie-head)%qmaxzie; } void clear(){ head=tail; } int main(){ init(); int n,k; cin>>n>>k; for(int i=0;i<n;i++){ push(i); } while(size()!=1){ for(int i=1;i<k;i++){ push(front()); pop(); } pop(); } cout<<front(); return 0; }