3.cpp

3. 约瑟夫环问题。设编号为1,2,…,n(n>0)个人按顺时针方向围坐一圈。开始时任意给出一个报数上限值m

#include<iostream>
using namespace std;
#include<malloc.h>
typedef struct node
{
	int data;
	struct node *next;
}node;
void main()
{
	int n,m,a[1000],i;
    int biao;
	 struct node *head,*p,*q,*temp;
	FILE *fp;
	fp=fopen("input3.txt","r");
	fscanf(fp,"%d%d",&n,&m);
	fclose(fp);
	for(i=0;i<n;i++)
	{
		a[i]=i+1;
	}
	head=(node *)malloc(sizeof(node));//建循环链表
	head->next=NULL;
	p=head;
	for(i=0;i<n;i++)
	{
		q=(node *)malloc(sizeof(node));
		q->data=a[i];
		q->next=NULL;
		p->next=q;
		p=p->next;
	}
	p->next=head->next;	
	biao=n;
	p=head;
	while(biao>0)
	{
		for(i=1;i<m;i++)//找到要删除的前一个结点
		{
			p=p->next;
		}
		temp=p->next;//使temp指向要删除的那个结点
		cout<<temp->data<<" ";//删除并读出结点值
		p->next=temp->next;
		biao--;
	}
}