2527: 【普及-】【P1996】约瑟夫问题

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：39 解决：25

题目描述

 个人围成一圈，从第一个人开始报数,数到 lns="http://www.w3.org/1998/Math/MathML">� 的人出列，再由下一个人重新从 lns="http://www.w3.org/1998/Math/MathML">1 开始报数，数到 lns="http://www.w3.org/1998/Math/MathML">� 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 lns="http://www.w3.org/1998/Math/MathML">�−1 名小朋友，而该题是全部出圈。


输入

输入两个整数 lns="http://www.w3.org/1998/Math/MathML">�,�。

输出

输出一行 lns="http://www.w3.org/1998/Math/MathML">� 个整数，按顺序输出每个出圈人的编号。

样例输入 复制 

41 3

样例输出 复制 

3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31

提示

1≤m,n≤100

使用队列queue： 

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

使用链表list： 

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt=0;
list<int> a;
int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++) a.push_back(i);
	list<int>::iterator it,now;
	it=a.begin();
	while (!a.empty()) {
		cnt++;
		now=it;
		if (++it==a.end()) it=a.begin(); //实现环状链表
		if (cnt==m) {
			cout<<*now<<" ";
			a.erase(now);
			cnt=0;
		} 
	}
	return 0;
}


来源/分类

提交提交记录统计露一手!