#include using namespace std; //The Josephus Problem class CircleIntArray { public: CircleIntArray(int inSize) : inArrSize(inSize) { inArray = new int [inSize]; } ~CircleIntArray() { delete [] inArray; } //------------------------------ int el(int elNum) {//returns the value of the element elNum = calcEl(elNum); return inArray[elNum]; } //------------------------------ void assign(int elNum, int elValue) {//assigns the value to the element inArray[calcEl(elNum)] = elValue; } //------------------------------ int calcEl(int inEl) {//given any large number, calculates the number of element by circle if(inEl < inArrSize) { return inEl; } return inEl % inArrSize; } //------------------------------ void del(int elNum) {//deletes the element, decreasing size of the array for(int i = calcEl(elNum); i < (inArrSize - 1); i++) { inArray[i] = inArray[i + 1]; } inArrSize--; } //------------------------------ int size() {//returns size of the array return inArrSize; } //---------------------------- void prnt() {//prints every element in a string for(int i = 0; i < inArrSize; i++) { cout << inArray[i] << " "; } cout << endl; } //------------------------------ private: int *inArray; int inArrSize; //------------------------------ }; //============================== int main() { //-------------------- int men;//number of men in the circle cin >> men; CircleIntArray myArr(men); //filling the array for(int i = 1; i <= myArr.size(); i++) { myArr.assign(i - 1, i); cout << myArr.el(i - 1) << " "; } cout << endl << endl; //solving and printing results int sword = 0;//position number in array of the man who holds the sword while(myArr.size() > 2) { cout << myArr.el(sword) << " kills " << myArr.el(sword + 1) << " and gives the sword to " << myArr.el(sword + 2) << endl; myArr.del(sword + 1); if(myArr.calcEl(sword) == sword) { sword++; } else {//Doesn't work without this. Why?!! sword = myArr.calcEl(sword); } cout << "thus there are " << myArr.size() << " men in the circle:" << endl; myArr.prnt(); cout << endl; } cout << myArr.el(sword) << " kills " << myArr.el(sword + 1) << " and he is the lucky!" << endl; myArr.del(sword + 1); cout << "thus the last man with a sword is "; myArr.prnt(); cout << endl; //-------------------- return 0; }

Circle kills (Josephus Problem)