约瑟夫环问题

设有n个人围成一圈，每个人持有一个密码m，现从第1个人开始报数，报m的出圈，再从他的下一个人重新报数，报m的出圈，如此下去直到圈中只剩一人。求该人的编号及出圈次序。

简单的方法就是拿一个数组来代表一个环，然后模拟报号出圈的过程，直到所有人都出圈。
以下参考代码
#include <iostream>
using namespace std;
int main()
{
int n,m,i,j,k;
cin>>n>>m;
int *p=new int[n];
for(i=0; i<n; i++)*(p+i)=i+1;//编号
for(j=k=0,i=1; k<n; j=++j%n)//从左至右，重复扫描数组，直到所有人都出圈。
{
if(*(p+j)!=0)//用零来表示已出圈，出圈了不报号
{
if(i==m)//报号数与密码相同，则出圈
{
cout<<j+1<<" ";//cout<<*(p+i-1)<<" ";//输出编号
*(p+j)=0;//标记已出圈
++k;//累记出圈人数
i=1;//报号重置
}
else ++i;//继续报号
}
}
return 0;
}追问

能用链表来写吗？数据结构的题目！谢谢了！

追答

…………那个知道方法，自己动手写还是很简单的，花些时间而已，你如果有学这些东西，建议还是自己多多动手
#include
using namespace std;
typedef struct _poin
{
int num;
struct _poin *next;
} poin;

int main()
{
int n,m,i,j,count;
poin *fir,*p;
cin>>n>>m;
fir=new poin;//表头
fir->num=1;
fir->next=0;
p=fir;
for(i=1; inext=new poin;
p=p->next;
p->num=i+1;//编号
}
p->next=fir;//首尾相连
for(count=1; p->next!=p;)//指向本身，说明链表只剩一个元素
{
if(count==m)
{
poin *lep=p->next;
coutnumnext=p->next->next;
count=1;
delete lep;
}
else
{
++count;
p=p->next;
}
}
coutnum<<" ";
return 0;
}

温馨提示：内容为网友见解，仅供参考

当前网址：https://22.t2y.org/zz/000x6hcc0.html