The Josephus Problem There are a number of prisoners arranged in a circle. Begin

Question

The Josephus Problem

There are a number of prisoners arranged in a circle. Beginning with some given starting position, we count round the circle clockwise and brutally execute every kth prisoner, the circle closing as the prisoners die. Because it is the king's birthday, the last prisoner in the circle is to be set free. For example, if the sequence is

<Roy, Chad, Ray, Gertrude, Lady>

and we start with Chad and k=7, then Ray,Roy,Chad, and Gertrude take a one-way trip on the Stygian Ferry whilst Lady gets to enjoy the birthday celebration.

Write the class JosephusProblem by completing the implementation for the interface given below:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

class JosephusProblem {
private:
vector<string> prisoners; //the circle of prisoners
int start; //the starting position
int delta; //the chosen interval
string survivor; // the problem solution - the surviving prisoner

void erase (vector <string>& v, int pos);
void copy (const vector <string>& v, vector <string>& copyV);
public:
/**
Constructs a Josephus Problem and its solution (the survivor).
@param in the input stream containing the prisoner names - one per line
@param startingPosition the initial position from which choices are made
@param interval the number of positions skipped for each choice
*/
JosephusProblem (istream& in, int startingPosition, int interval);

/**
prints the problem in the following form:
Prisoner List:
name 1
name 2
...
name n

starting position: i; interval for choices: j
the survivor is: name k
*/
friend ostream& operator<<(ostream& out, const JosephusProblem& number);
};

/**
Copies a vector.
@param v a vector
@param copyV a shallow copy of v
*/
void JosephusProblem::copy(const vector<string>& v, vector<string>& copyV)
{
for (int i = 0; i < v.size(); i++)
copyV.push_back(v[i]);
}

/**
Removes an element from an ordered vector.
@param v a vector
@param pos the position of the element to erase
*/
void JosephusProblem::erase(vector<string>& v, int pos)
{
for (int i = pos; i < v.size() - 1; i++)
v[i] = v[i +1];
v.pop_back();
}

JosephusProblem::JosephusProblem(istream& in, int startingPosition, int interval)
{
}

ostream& operator<<(ostream& out, const JosephusProblem& problem)
{
}
int main()
{
ifstream names;
names.open("prisoners.dat")
if (names.fail())
{
cout << "error opening prisoners.dat for reading ";
return 1;
}
JosephusProblem p1(names, 0, 7);
cout << p1;
return 0;
}

ps. the input file has 12 names

Explanation / Answer

Please rate - thanks

not what you're looking for, but I know nothing about vectors, and you didn't respond to my message.

hopefully this will get you started. the way I learned to use linked lists 40 years ago

#include <iostream>
#include <fstream>
using namespace std;
main()
{int i,j=0,n,k,upto,camefrom;
int men[25];
string name[25];
ifstream input;
   input.open("prisoners.dat");           //open file
   if(input.fail())             //is it ok?
       { cout<<"file did not open please check it ";
        system("pause");
        return 1;
        }
n=0;
input>>name[n];
while(input)
    {cout<<name[n]<<endl;
     n++;
     input>>name[n];
     }       
       
cout<<"How many steps to take? ";
cin>>k;
cout<<"what number are you going to start counting at(0 to "<<n-1<<"): ";
cin>>upto;
cout<<"The circle: ";

for(i=0;i<n-1;i++)
    men[i]=i+1;
men[n-1]=0;
do
{ do
   {j++;
    camefrom=upto;
    upto=men[camefrom];
    }while (j<k);
    j=0;
    if(camefrom!=upto)
        cout<<name[upto]<<" is removed ";
    men[camefrom]=men[upto];   
}while(camefrom!=upto);
cout<<name[upto]<<" has survived ";  
system("pause");
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.