josep.cpp

Josephus排列问题定义如下：假设n个竞赛者排成一个环形。给定一个正整数m

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

class List;

class OutOfBounds{};

class Node//节点类
{
	friend class List;
	friend bool Jose(const int& total,const int& distance,const int& par,
		int* survivor_num,int* survivor_list);
private:
	int data;		//用于存储每个人在圈中的序号
	string name;	//存储每个人的名字
	Node* next;
};

class List
{
public:
	List();
	~List();
	//输入表中人的序号，得到其名字存储在name中
	bool Retrieve(const int num,string& name) const;
	//在指定的位置k处插入节点
	List& push_back(const int& x,const string& name);
	//删除指定的节点
	List& Delete(Node* current);

	friend bool Jose(const int& total,const int& distance,const int& par,
		int* survivor_num,int* survivor_list);
private:
	int len;//表的长度
	Node* last;//指向最后一个节点的指针
};

List::List()//默认表中没有元素
{
	last=NULL;
	len=0;
}

List::~List()//析构函数，删除节点
{
	Node* next;
	while(len-->1)
	{
		next=last->next;
		delete last;
		last=next;
	}
	delete last;
}
//输入表中人的序号，得到其名字存储在name中
bool List::Retrieve(const int num,string& name) const
{
	Node* current=last->next;
	int index=0;
	while(index++<len)
	{
		if(current->data==num)
		{
			name=current->name;
			return true;
		}
		current=current->next;
	}
	return false;
}
//删除p指向的节点
List& List::Delete(Node* p)
{
	Node* current=last->next;
	Node* c=last;
	int index=0;
	while(index++<len)
	{
		if(current==p)
		{
			c->next=current->next;
			if(current==last) last=c;
			delete p;
			len--;
			return *this;
		}
		else
		{
			c=current;
			current=current->next;
		}
	}
	if(index==len) throw OutOfBounds();//p指向的节点不在该链表中，抛出异常	
	return *this;
}
//在链表的末尾插入一个元素
List& List::push_back(const int& num,const string& name)
{
	Node* p=new Node;//新建一个节点
	p->data=num;
	p->name=name;
	
	if(last)
	{
		Node* temp=last->next;
		last->next=p;
		p->next=temp;
		last=p;
	}
	else
	{
		last=p;
		p->next=p;
	}
	len++;
	
	return *this;
}

bool Jose(const int& total,const int& distance,const int& par,
		  int* survivor_num,int* survivor_list)
{
	List list;
	for(int i=0;i<total;i++)
	{
		list.push_back(i+1,"");
	}
	Node* current=list.last->next;
	
	int j=0;
	for(; j<total-par ;j++)
	{
		int k=distance%list.len;
		if(!k) k=list.len;

		for(;k>1;k--)
		{
			current=current->next;
		}
		survivor_list[j]=current->data;
		Node* c=current;
		current=current->next;
		list.Delete(c);
	}
	
	for(int m=0;m<par;m++)
	{
		for(int n=0;n<total-par;n++)
		{
			if(survivor_num[m]==survivor_list[n]) return false;
		}
	}
	return true;//最后的par个数与文件中读入的序列相同，表明该distance 满足要求，返回true
}

int Josep(int total,int par,int* survivor_num,int* survivor_list)
{
	for(int distance=1;  ;distance++)
	{
		if(Jose(total,distance,par,survivor_num,survivor_list))
				return distance;
	}
}

void main()
{
	ifstream Input("input.txt");
	if(!Input)
	{
		cerr<<"Fail to open the \"input.txt\"!"<<endl;
		exit(1);
	}
	cout<<"Suceed to open the \"input.txt!\""<<endl;
	
	ofstream Output("output.txt");
	if(!Output)
	{
		cerr<<"Fail to open or built the \"output.txt\"!"<<endl;
		exit(1);
	}
	cout<<"Suceed to open the \"output.txt\"!"<<endl;
	
	int total,par;
	
	Input>>total>>par;//从文件中读入总人数和排在最后的指定的人数
	
	if(par<1 || total<1) //检测输入是否合法
	{
		cout<<"Wrong input!Please check it!"<<endl;
		
		throw OutOfBounds();
	}

	int* survivor_num=new int[par];//survivor_num为指向排在最后的par个人序号组成的数组的指针
	
	for(int i=0;i<par;i++) Input>>survivor_num[i];//从文件中读入par个人的序号
			
	List list;
	string name;
	
	for(int j=0;j<total;j++)
	{
		Input>>name;//从文件中读入total个人的名字
		list.push_back(j+1,name);
	}
	
	int* survivor_list=new int[total-par];//survivor_list为指向满足要求的Josephus排列的指针
	//调用函数得到间隔人数，并将其输出到文件output.txt中
	int distance=Josep(total,par,survivor_num,survivor_list);
	
	Output<<distance<<endl;
	
	for(int k=0;k<total-par;k++)
	{//将前total-par个出列的人名字输出到文件output.txt中
		list.Retrieve(survivor_list[k],name);
		Output<<name.c_str()<<endl;
	}

	
	delete[] survivor_num;
	delete[] survivor_list;
	
	Input.close();
	Output.close();
}