openjudge 约瑟夫环问题

1:约瑟夫环问题

• 查看
• 提交
• 统计
• 提问

总时间限制: 

1000ms

 

内存限制: 

1000kB

描述

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

输入

8 1 3 (n=8 k=1 m=3 )

输出

7 (剩下的那个)

样例输入

8 3 1

样例输出

7

 

这题比较坑，因为我用的是带头节点的循环链表，所以让这题很麻烦，在头节点那里需要特判，而且这题的数据会有一个坑就是起始的编号可能会大于n。

#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
int sum=0,s;
template <class T>

struct Node
{
	T data;
	Node<T> *next;
};
template <class T>
class List
{
	Node<T> *first;
public:
	List();
	List(int n);  
	List(T a[],int n,int k);
	void display();
	T del(int be,int n);
	int Len();
};
template <class T>
List<T>::List()
{
	first=new Node<T>;
	first->next=NULL;
}
template <class T>
List<T>::List(int n) ///头插法
{
	first=new Node<T>;
	first->next=first;
	Node<T> *s;
	for(int i=n;i>=1;i--)
	{
		s=new Node<T>;
		s->data=i;
		s->next=first->next;
		first->next=s;
	}
}
template <class T>
T List<T>::del(int be,int k)
{
	Node<T> *temp=first;
	T x;

	 for(int i=1;i<be;i++)
	{
			temp=temp->next;
			if(temp==first)i--;
	}
	while(Len()>0)
	{
		
     	for(int i=1;i<k;i++)
		{
		 temp=temp->next;
		 if(temp==first) i--;
		}
		if(temp->next==first) temp=temp->next;
		
		Node<T> *q;
	    q=temp->next;
		x=q->data;
		temp->next=q->next;
		
		delete q;
		sum++; 
		if(sum==s)
		{
			cout<<x;
			break;
		}
	}
	return x;
	
}
template <class T>
void List<T>::display()
{
	Node<T> *temp=first;
	if(first!=NULL)
	{
		do
		{
			temp=temp->next;
		}while(temp!=first);
	}
}
template <class T>
int List<T>::Len()
{
	Node<T> *temp=first;
	int j=0;
	if(first!=NULL)
	{
		do	
		{
			temp=temp->next;
			 j++;
		}while(temp!=first);
	}
	return j-1;
}
int main()
{
	int n,m,be;
	while(scanf("%d%d%d",&n,&be,&m)!=-1)
	{
	sum=0;s=n;
	List<int> l1(n);
	l1.del(be,m);
	}
	return 0;
}