josep.cpp

设计一个算法

#include<iostream>
#include<fstream>
#include<string>
#define M 100
using namespace std;
template <class T>
class Josep
{
	private:
		int Maxsize;
		string *a;
	public:
		Josep(int n);
		~Josep() {delete []a;}
		int Josephus(int n,int m,int k,int b[],char name[][M]);
};
template <class T>
Josep<T>::Josep(int n)
{
	Maxsize=n;
	a=new string [Maxsize];
}
int Josephus(int n,int m,int k,int b[],char name[][M])
{
	ofstream out("output.txt");
	int i,j,t=0,count=0;
	int *a=new int[n+1];
	for(i=1;i<n+1;i++) a[i]=i;
	int *c=new int[n-k+1];
	i=0;
	while(t<n-k)
	{
		i++;
		if(a[i]!=0) count++;
		if(count==m)
		{ 
			for(j=1;j<k+1;j++)
				if(i==b[j]) return 0;
			a[i]=0;
			count=0;
			t++;
			c[t]=i;
		}
		if(i==n) i=0;
	}
	out<<m<<endl;
	for(i=1;i<n-k+1;i++)
		out<<name[c[i]]<<endl;
	return 1;
}
int main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	ofstream out("output.txt");
	int n,m,i,j=1,k,t=1,J;
	char name[M][M];
	in>>n>>k;
	if(k<=0||k>=n)
	{
		out<<"error!"<<endl<<"请重新输入数值!";
		exit(1);
	}
	int *b=new int[k+1];
	for(i=1;i<k+1;i++) 
		in>>b[i];
	for(i=1;i<n+1;i++)		
		in>>name[i];
	m=0;
	do
	{
		m++;
		J=Josephus(n,m,k,b,name);
	}while(J==0);
    in.close();
    out.close();
	return 0;
}