【题解】围圈报数（约瑟夫问题）
【题目描述】
有n个人依次围成一圈，从第1个人开始报数，数到第m个人出列，然后从出列的下一个人开始报数，数到第m个热呢又出列，... ,如此反复到所有的人全部出列为止。设n个人的编号分别为1，2
，... , n，打印出列的顺序。
【输入描述】
一行，n和m。
【输出描述】
输出列的顺序
【样例输入】
4 17
【样例输出】
1 3 4 2
【题目分析与思路1】—数组
题目来源于“约瑟夫问题”。把所有人都放到数组中
每个人的状态有两个，出列或者不出列，可以用true和false表示
每个人一开始都在队列中，可以都用false表示
然后模拟出队列的过程，直到所有人都出队列
问题难点在于每个人出队后，队列就变了（长度变了），
在外部写个循环保证还有人在队伍里就继续
在上一个条件下，遍历数组，给选定的人进行标记，同时进行累加判断，找到第m个人。
【参考代码1】
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int a[100]; //学生数组
int n,m; // n个人，第m个人出列
int main()
{
int people,position; //用people表示还在队列中的人，position表示每轮的计数情况，每次从0开始
cin>>n>>m;
for(int i=1;i<=n;i++)
a[i]=1; //先把所有的人都标记为1
people=n; //把所有人赋值给people
position=0;
while(people>0) // 只要还有人在队列中就继续
{
for(int i=1;i<=n;i++) //遍历n个人
{
if(a[i]==1) //如果当前这个人是1，表示在队列中，就从中找第m个
{
position++; //位置加1
if(position==m) //如果是第m个位置
{
position=0; // 把位置重置为0
a[i]=0; //把当前这个人提出队列，下次就不再遍历他了
cout<<i<<" "; //当前人编号输出
people--; //队列减去一个1
if(people==0) //如果没人了，就退出
{
break;
}
}
}
}
}
return 0;
}【题目分析与思路2】—队列
#include<iostream>
#include<queue>
using namespace std;
int main()
{
int n,m;
cin>>n>>m; //读入n和m
queue<int> q;
for(int i=1;i<=n;i++)
q.push(i);
int cnt=0;
while(!q.empty()){ //只要队列不为空
cnt++; // 计数加1
int temp=q.front(); //把当前队首元素拿出
if(cnt==m){ //判断是不是到了m
cnt=0; //把计算器变为0
cout<<temp<<" "; // 输出这个人的编号
}
else{
q.push(temp); //表示还没到m
}
q.pop(); //遇到第m个，就删除队首。没有遇到第m个，就把队首删除（队首已经重新入队变成队尾了）
}
cout<<endl;
return 0;
}【链表版本】
#include <iostream>
using namespace std;
struct node {
long d;
node * next;
};
long n,m;
node *head,*p,*r;
int main() {
long i,j,k,l;
cin>>n>>m;
head=new node;
head->d=1;
head->next=NULL;
r=head;
for(i=2; i<=n; i++) {
p=new node;
p->d=i;
p->next=NULL;
r->next=p;
r=p;
}
r->next=head;
r=head;
for(i=1; i<=n; i++) {
for(j=1; j<=m-2; j++)
r=r->next;
cout<<r->next->d<<" ";
r->next=r->next->next;
r=r->next;
}
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
