9.cpp

约瑟夫问题的一个解法

#include <iostream>
using namespace std;

class Joseph{
protected:
	int number_of_people;
	int step;
public:
	virtual void CreateOutput()=0;
	Joseph(int n,int m){
		number_of_people=n;
		step=m;
	}
};

class JosephWithArray:public Joseph{
	int *WorkingArray;
	int NextPeople(int prev);
public:
	JosephWithArray(int n,int m);
	void CreateOutput();
	~JosephWithArray(){delete[] WorkingArray;}
};

JosephWithArray::JosephWithArray(int n,int m):Joseph(n,m){
	WorkingArray = new int[n];
	for(int i=0;i<n;i++)
		WorkingArray[i]=i+1;
}

void JosephWithArray::CreateOutput(){
    int i;
	int outnum=-1;
	for(i=0;i<number_of_people;i++){
		outnum = NextPeople(outnum);
		cout << WorkingArray[outnum] << " ";
		WorkingArray[outnum]=0;
	}
	cout << endl;
}

int JosephWithArray::NextPeople(int prev){
	int count=0;
	int travel=prev;
	while(count<step){
		travel=(travel+1)%number_of_people;
		if(WorkingArray[travel])
			count++;
	}
	return travel;
}

int main(){
	int n,m;
	cout << "please input number of people:";
	cin >> n;
	cout << "please input step:";
	cin >> m;
	JosephWithArray obj(n,m);
	obj.CreateOutput();
	getchar();
	getchar();
	return 0;
}