ベクトルテーブルによるジョセフ問題の解決


ベクトルテーブル定義
vector.h
#ifndef VECTOR_H
#define VECTOR_H
#include<iostream>
using namespace std;
// 
template <class T>
class Vector
{
	private:
		T *elements;// 
		int ArraySize,VectorLength;
		void GetArray();// 
	public:
		Vector(int Size=0);// 
		~Vector(){delete []elements;}
		int GetLenght() const
		{
			return VectorLength;
		}
		T GetNode(int i)// i 
		{
			return (i<0||i>=VectorLength)?NULL:elements[i];

		}
		int Find(T& x)// x 
		{
			for(int i=0;i<VectorLength;i++)
				if(elements[i]==x) return i;
				return -1;
		}

		bool Insert(T& x,int i);// 
		bool Remove(int i);// 

};
template <class T>
void Vector<T>::GetArray()
{
	elements=new T[ArraySize];
	if(elements==0)
		cerr<<"Memory Allocation Error!"<<endl;
}

template <class T>
Vector<T>::Vector(int sz)// 
{
	if(sz<=0)
		cerr<<"Invaild Array Size!"<<endl;
	else
	{
		ArraySize=sz;
		VectorLength=0;
		GetArray();
	}
}

template <class T>
bool Vector<T>::Insert(T& x,int i)// 
{
	if(VectorLength==ArraySize)
	{
		cerr<<"overflow"<<endl;
		return false;
	}
	else if(i<0||i>VectorLength)
	{
		cerr<<"Insert position error!"<<endl;
		return false;
	}
	else
	{
		for(int j=VectorLength-1;j>=i;j--)
			elements[j+1]=elements[j];// 
		elements[i]=x;// 
		VectorLength++;
		return true;
	}
}

template <class T>
bool Vector<T>::Remove(int i)// 
{
	if(VectorLength==0)
	{
		cerr<<"Verctor is Empty!"<<endl;
		return false;
	}
	else if(i<0||i>VectorLength-1)
	{
		cerr<<"Remove position error!"<<endl;
		return false;
	}
	else
	{
		for(int j=i;j<VectorLength-1;j++)
			elements[j]=elements[j+1];// 
		VectorLength--;
		return true;
	}

}

#endif

 
 
// ( ) 
#include<iostream>
#include"Vector.h"
using namespace std;

void Josephus(Vector<int> &P,int n,int s,int m)//n s , m 
{

	int k=1;
	for(int i=0;i<n;i++)
	{P.Insert(k,i);k++;}
	int s1=s;
	for(int j=n;j>=1;j--)
	{
		s1=(s1+m-1)%j;
		if(s1==0)
			s1=j;
		int w=P.GetNode(s1-1);
		P.Remove(s1-1);// , 
		P.Insert(w,n-1);
	}
}
int main()
{
	Vector<int> a(13);
	Josephus(a,13,1,3);//13 1 , 3 
	for(int i=0;i<13;i++)
		cout<<a.GetNode(i)<<endl;// 
	return 0;
}