ベクトルテーブルによるジョセフ問題の解決
ベクトルテーブル定義
vector.h
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;
}