一、问题描述

约瑟夫环问题是一个很经典的问题：一个圈共有N个人（N为不确定的数字），第一个人的编号为0或者1（两个都可以，看你的程序如何编写），假设这边我将第一个人的编号设置为1号，那么第二个人的编号就为2号，第三个人的编号就为3号，第N个人的编号就为N号，现在提供一个数字M，第一个人开始从1报数，第二个人报的数就是2，依次类推，报到M这个数字的人出局，紧接着从出局的这个人的下一个人重新开始从1报数，和上面过程类似，报到M的人出局，直到N个人全部出局，请问，这个出局的顺序是什么？
 

输入：

10 3

输出：

3 6 9 2 7 1 8 5 10 4

思路：

对于没有出局的人来说，全部标记为0；满足条件出局标记为-1；并且输出；

注意：只有为0才有资格进入是否满足条件

 #include 
 //数组模式 
 using namespace std;
 //ans 计数，超过m就 ans=0
 //num 表示打印出来数字的多少，结束循环
 //x[] 打印出来数字以后把  x[]=-1； 
 
 int main()
 {
 	int m,n;
 	int num=0,i=0,ans=0;
 	int x[10024]={0};
 	cin>>n>>m;
	while(num!=n)
	{
		i++;
		if(i>n) i=1;
		if(x[i]==0)
		{
			ans++;
			if(ans==m)
			{
				num++;
				ans=0;
				x[i]=-1;
				cout< 
 
 
循环链表解法 
思路：创建结构体，尾插法插入数据，创建循环链表（记得让头指针=尾指针，为来约瑟夫环判断只有一个元素）约瑟夫环的模拟
 

#include 
using namespace std;

 typedef struct node  //typedef用来重命名struct node这种数据类型，将其命名为Node
 {
 	int data;
 	struct node*next;
 }Node;


void def(int n,int m)
{
	Node *head=NULL,*r=NULL,*p=NULL;
	head=(Node*)malloc(sizeof(Node));  //开辟空间 
	
	if(NULL==head)  //内存空间可能会申请失败,大多数情况不会申请失败 
	{
			cout<<"Memory Failed!";
			return;
	} 
	
	head->data=1;
	head->next=NULL;
	p=head;
	
	
	//尾插法 
	for(int i=2;i<=n;i++)
	{
		r=(Node*)malloc(sizeof(Node));
		r->data=i;
		r->next=NULL;
		p->next=r;
		p=r;  //p是r的前面一个指针，r每次被新定义，p也相当于整个链表的尾指针 
	}
	
	//创建循环链表
	p->next=head;
	p=head;   //为后续方便，指向head 
	
	//约瑟夫环的模拟
	while(p->next!=p) //只有一个元素
	{
		for(int i=1;inext= p->next
			p=p->next;
		}
		cout<data<<" ";
		r->next=p->next;
		p=p->next;
		
	}
	cout<data;
}
 int main()
 {
 	int n,m;
 	cin>>n>>m;
 	def(n,m);
 	return 0;
 	
 	
 	
 } 

 
 
 
队列queue解法 
思路：利用queue的函数，每次取出第一个元素，判断是否需要出局，如果出局，pop该元素，如果不出局，在队尾加上该元素
 

#include 
using namespace std;

queue  q;
int main()
{
	int ans=1,i=0;
	int n,m; 
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		q.push(i);
	}	
	while(q.size()!=0)
	{
		if(ans 
 
 
 
1. push     q.push(i)    //在队尾插入i
 
 
2. pop       q.pop()      //弹出（删除）队头元素，但是没有返回值
 
 
3. size       q.size()      //返回q的长度
 
 
4. empty    q.empty()  //判断是否为空
 
 
5. front      q.front()     //返回队头元素，但是不删除
 
 
6. back      q.back()     //返回队尾元素，不删除