The Josephus Problem

[SeaPanda]

What's up guys, I have ran into a problem writing code for the Josephus Problem. My professor wants us to use arrays with queue like properties. I'm running into trouble when trying to refresh the " queue" with the member who is kicked out.

this part is giving me trouble...

 

string Cqueue2::remove_nth_member(int n)             //for Josephus problem to remove a member
    {
        string name;
        int i;
        int index;
        int start;

        name = Queue[(n - 1) % Size];
        //we'll be deleteing the soldier at index n%Size
        //subtract 1 to account for the fact that indexing starts at 0

        start = n%Size;
        string * TempQ = new string[Size - 1];
        //some looping has to go on here, to move stuff in current queue to temp queue that is smaller
        for (i = 0; i < Size; i++)
        {
            index(Start++i) % Max;
            tempQ[i] = Queue[index];
        }
        //refresh Queue with the member who is kicked out gone
        //Change its size
        //delete Queue
        for (int j = 0; j < Size; j++)
        {

            Size--;
        }
        //create a new Queue with new Size
        //iterate and move things from tempQ into Queue
        //deduct from the Max variable
        return name;
    }

 

main.cpp

 

#include <iostream>
#include <cstring>
#include "cqueue2.h"

using namespace std;

int main()
{
    int i;
    string Temp;
    int n;                  //number we'll count.
    int num_members;      //number of members

    cout << "*********************** The Josephus Problem ***********************" << endl;
    cout << "A group of soldiers is surrounded. There is no hope for victory." << endl;
    cout << "There is but a single horse available for escape and many soldiers." << endl;
    cout << "Who will survive??" << endl;
    cout << " How many soldiers are there:";
    cin >> num_members;
    cout << num_members;

    //1. Let n be the number of members
    //2. Get the first member.
    //3. Add all of the members to the queue

    //IMPORTANT, HAVE TO ASK WHAT THE NUMBER IS n THAT WE'LL COUNT AROUND THE CIRCLE
    cout << "We'll be counting around a circle. What is n: ";
    cin >> n;

    //while (there is more than one member in the queue):
    //      count through n-1 members in the queue
    //      print the name of the nth member
    //      remove the nth member from the queue
    string Name;
    while (Q.get_size()>1)
    {
        Name = Q.remove_nth_member(n);                            //function removes the member
        cout << endl << Name << " has been removed from the circle.\n";
        cout << "Now the queue contains: ";
        Q.write_Cqueue_to_Console();                            //this will just print out the names still in the queue so you can track what's going on
    }

    //4. Print the name of the only member in the list

    return 0;
}

cqueue2.cpp

 

#include <iostream>
#include "cqueue2.h"

using namespace std;

Cqueue2::Cqueue2(int n)
{
    Size = 0;
    Rear = Front = -1;
    Max = n;
    Queue = new string[n];        //the Queue array is dynamically allocated
}

Cqueue2::~Cqueue2()
{
    delete[] Queue;               //have to delete dynamically allocated memory
}

int Cqueue2::Is_Empty()
{
    if (Size == 0) return true;
    else return false;
}

int Cqueue2::Is_Full()
{
    if (Size == Max) return true;
    else return false;
}

void Cqueue2::Add(string Element)
{
    if (!Is_Full()) Rear = (Rear + 1) % Max;
    Queue[Rear] = Element;
    Size++;
}

string Cqueue2::Delete()
{
    if (Is_Empty())
    {
        cout << "The Cqueue is empty." << endl;
        return "";
    }
    else
    {
        Front = (Front + 1) % Max;
        Size--;
        return Queue[Front];
    }
}

string Cqueue2::getFront()
{
    int Temp;
    if (Is_Empty())
    {
        return "";
    }
    else
    {
        Temp = (Front + 1) % Max;
        return Queue[Temp];
    }
}

void Cqueue2::write_Cqueue_to_Console()         //write all of the class variables to the console
{
    int i;
    int Temp;
    if (Is_Empty())
        cout << "Queue is empty.\n";
    else
    {

        for (i = 1; i <= Size; i++)
        {
            Temp = (Front + i) % Max;
            cout << Queue[Temp] << " ";
        }
        cout << endl;
    }

    int Cqueue2::get_size()                         //this function is added to Cqueue2 so can tell when have 1 member in the queue
    {
        return Size;
    }
    //2: Do this 
    string Cqueue2::remove_nth_member(int n)             //for Josephus problem to remove a member
    {
        string name;
        int i;
        int index;
        int start;

        name = Queue[(n - 1) % Size];
        //we'll be deleteing the soldier at index n%Size
        //subtract 1 to account for the fact that indexing starts at 0

        start = n%Size;
        string * TempQ = new string[Size - 1];
        //some looping has to go on here, to move stuff in current queue to temp queue that is smaller
        for (i = 0; i < Size; i++)
        {
            index(Start++i) % Max;
            tempQ[i] = Queue[index];
        }
        //refresh Queue with the member who is kicked out gone
        //Change its size
        //delete Queue
        for (int j = 0; j < Size; j++)
        {

            Size--;
        }
        //create a new Queue with new Size
        //iterate and move things from tempQ into Queue
        //deduct from the Max variable
        return name;
    }

cqueue2.h

 

/*********************************************
This is a modification of the Cqueue class
for the Josephus Problem. The class variable
Queue is an array of strings (for names).
*********************************************/
#include <cstring>
#include <string>
using namespace std;

class Cqueue2
{
private:
    int Rear, Front;
    string * Queue;
    int Max;
    int Size;
public:
    Cqueue2(int n);
    ~Cqueue2();
    int Is_Empty();
    int Is_Full();
    void Add(string Element);
    string Delete();
    string getFront();
    void write_Cqueue_to_Console();         //write all of the class variables to the console
    int get_size();                         //this function is added to Cqueue2 so can tell when have 1 member in the queue
    string remove_nth_member(int n);        //for Josephus problem to remove a member
};

 

[Mr_KoKa]

I would change 

name = Queue[(n - 1) % Size];

to

index (n - 1) % Size
name = Queue[index];

so you have index as your comments state.

 

Then you need to create new array that is Size - 1 length.

Transfer all elements before removed index, and all elements after.

Then free memory of old array, and assign new array pointer to it.

 

std::string *newQueue = new std::string[Size - 1];

//Transfer all before removed index, even if index will be 0 then this loop won't fire
for(size_t i = 0; i < index; i++){
  newQueue[i] = queue[i];		
}

//Transfer all after index, if index will be last element of array this loop won't fire
for(size_t i = index + 1; i < Size; i++){
  newQueue[i - 1] = queue[i]; // i - 1 cause we skip one and new array has one space less.
}

delete[] queue; // free memory of old queue.
queue = newQueue; // assign pointer of new queue to queue.

Size--; //Reduce Size counter.

 

Looking at your code, I don't know if this is what you want to accomplish, cause your code looks more complicated, but doesn't look valid either... let me know.

[SeaPanda]

@Mr_KoKa thanks for the reply, is the method that you're using implementing a circle queue.

[Mr_KoKa]

2 minutes ago, Sebastian Kurpiel said:

@Mr_KoKa thanks for the reply, is the method that you're using implementing a circle queue.

No, it just removews nth element form the array.

[SeaPanda]

Just now, Mr_KoKa said:

No, it just removews nth element form the array.

Okay, thanks. That's what I was looking for. I'm only getting an error because it says queue = newQueue; is undefined and that name is undefined.

[Mr_KoKa]

You need to fit variable names to your needs.

[SeaPanda]

Just now, Mr_KoKa said:

You need to fit variable names to your needs.

I believe my professor declared it in the main.cpp, 

Name = Q.remove_nth_member(n);  

would I have to redefine it?

[Mr_KoKa]

No, your Name variable is outside remove_nth_member function.

And you have name defined in your remove_nth_member function so there shouldn't be any problem with that.  

 

You use Queue and I used queue, you use TempQ and I used newQueue

[SeaPanda]

index(n - 1) % Size;
name = Queue[index];

does name automatically store the first part?

[Mr_KoKa]

Sorry I see I ate =, it should be

index = (n - 1) % Size;
name = Queue[index];

name stores the element that you are removing.

you should then return it.

[SeaPanda]

Thanks for seeing that, would

Queue = *TempQ

since in std::string *TempQ = new std::string;  it's a pointer

[Mr_KoKa]

You have 

string * TempQ = new string[Size - 1];

so

Queue = TempQ

 

[SeaPanda]

I'm receiving these errors when running the main. Trying to find out where "Q" is.

[Mr_KoKa]

Yeah, you first used Q here:

while (Q.get_size()>1)

But I don't see you define it.

 

You probably want to do:

Cqueue2 Q(num_members);

somewhere after you do:

    cout << " How many soldiers are there:";
    cin >> num_members;
    cout << num_members;

[SeaPanda]

Errors in main.cpp

Errors in cqueue2.cpp

 

 

It's still giving me a error in with Queue = TempQ, could the Size error be from the getsize()

[Mr_KoKa]

I think you forgot to close end bracket of function 

void Cqueue2::write_Cqueue_to_Console()

and then you declare more member functions like inside of this function, which is not allowed.

If you can, paste current code.

[SeaPanda]

It runs, thank you.

However it's not letting me input the name of the members, would I have to add something to my main ?

Edit:Would this be correct?

    Cqueue2 Q(num_members);

    for (i = 0; i< num_members; i++)
    {
        cout << " Name of member" << i << ":" << endl;
        i++;
        cin >> Q(num_members);
    }
 

 

[Mr_KoKa]

Cqueue2 class doesn't let you set the names. You would need to create yourself a function where you can pass name, and index, and it will set given name at given index.

 

Cqueue2::setName(int intex, std::string name){
	Queue[i] = name;
}

//And then in your main you can loop trough up to Size
for(int i = 0; i < Q.get_size(); i++){ 
  Q.setName(i, "New Name"); //You can get name from strin, or make somthing like name 1, name 2 using int to string convertion functions
}

Now when I look at the code, there is Front and Read integers inside Cqueue2 class, do you use them for something? I have feeling that you shouldn't re-declare your array but only operate at originally created one, and just remember where it starts and ends (you would move front or end despite which index you remove so if you remove index closer to the front, it would be only few elements from the front to move), but I don't know what are rules of your assignment.

[SeaPanda]

The way I originally thought this assignment was suppose to go with a circle queue, like I have integers of  012345 and I choose n=2, so I count by 2 and then remove 1 and then I start again at 2 and then remove 3. till I only have one member left.

[Mr_KoKa]

I don't mean how you make algorithm implementation, I'm saying about memory management.

But I guess that Front and Rear variables aren't for that purpose, so nvm.

[SeaPanda]

Just now, Mr_KoKa said:

I don't mean how you make algorithm implementation, I'm saying about memory management.

But I guess that Front and Rear variables aren't for that purpose, so nvm.

 

I would name the setName in my cqueue2 .h void setName(int intex, std::string name)

and then in the main 

for (i = 0; i< num_members; i++)
    {
Q.setName
    }

[Unimportant]

On 29.9.2016 at 7:44 PM, Mr_KoKa said:

 

std::string *newQueue = new std::string[Size - 1];

//Transfer all before removed index, even if index will be 0 then this loop won't fire
for(size_t i = 0; i < index; i++){
  newQueue[i] = queue[i];		
}

//Transfer all after index, if index will be last element of array this loop won't fire
for(size_t i = index + 1; i < Size; i++){
  newQueue[i - 1] = queue[i]; // i - 1 cause we skip one and new array has one space less.
}

delete[] queue; // free memory of old queue.
queue = newQueue; // assign pointer of new queue to queue.

Size--; //Reduce Size counter.

 

 

If i were his professor I'd deduct serious points for code like this. String operator = can throw multiple exceptions, which would cause this code to leak newQueue. Use RAII to wrap newQueue (std::unique_ptr for example). Basically, any naked "new" in code should cause your professor to deduct points.

 

Also, const correctness will be a big help in preventing bugs and should be a habit from the beginning. I'd suggest to the OP to study const correctness and apply it until it's a habit. Again, I'd deduct serious points for the lack of const correctness.

 

If your professor does not deduct points for these things I'd confront him on that. There's no point in learning it wrong.