Question

The problem is known as the Josephus Problem (or Josephus permutation) and postulates a group of people of size N >= 1 are standing in a circle waiting to be eliminated. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of M >= 1 people are counted, the M^th person in the circle is eliminated. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and counting the same number of people, until only one person remains.

For example, suppose that M = 3 and there are N = 5 people named A, B, C, D and E. We count three people starting at A, so that C is eliminated first. We then begin at D and count D, E and back to A, so that A is eliminated next. Then we count B, D and E, and finally B, D and B, so that D is the one who remains last.

For this computer assignment, you are to write and implement a C++ program to simulate and solve the Josephus problem. The input to the program is the number M and a list of N names, which is clockwise ordering of the circle, beginning with the person from whom the count is to start. After each removal, the program should print the names of all people in the circle until only one person remains. However, to save printing space, print the names of the remaining people only after K >= 1 eliminations, where K is also an input argument to the program. The input arguments N, M and K can be entered from stdin in the given order. (see josephus.d for values)

Programming Notes:

• Name the people in the circle in the following sequence: A1, A2 ... A9, B1, B2 ... B9, C1, C2 ..., and start counting from the person A1. Enter input values N, M and K when the program prompts for them and use a list<string> container to store the names of N people.

• void init_vals(list<string> &L, args &in) It reads the input values N, M and K of the struct args in when the program prompts for them. The routine prints out those values on stdout, and fills the names of people in the list L. You can find the definition of the struct args in the header file josephus.h, which is defined as:

struct args 
{
        unsigned N;
        unsigned M;
        unsigned K;
}; 

• void print_list(const list<string> &L, const unsigned &cnt) It prints out the contents of the list L at the beginning and after removing K names (each time) from the list, until only one name remains in the list, where cnt has an initial value 0 and it indicates the total number of removals so far. At the end, it also prints the name of the last remaining person. For printout, print only up to 12 names in a single line, where the names are separated by single spaces.

• The main() routine first calls the routine init_vals() and initializes cnt to 0, and then calls the print_list() to print out the names of people in circle. After that it locates the M^th person in the list, and using the member function erase(), it removes that person from the list, and by calling the print_list() prints out the current contents of the list. This process continues (in a loop) until only one person remains in the list.

  • If i (with initial value 0) indicates the position of a person in list L, then the statement: j = (i + (M –1))%L.size() returns the position of the M^th person from the position i.

  • Since the argument to the erase() function is an iterator, you can convert the index value j to an iterator by the advance(p, j) function, where p = L.begin().

• To store the names in an empty list, first change the size of the list to N, and then use the generate() function in the STL. The last argument to this function is the function object SEQ(N), which is defined in the header file josephus.h.

Assignment Notes:

• Include any necessary headers and add necessary global constants.

• You are not allowed to use any I/O functions from the C library, such as scanf or printf. Instead, use the I/O functions from the C++ library, such as cin or cout.

Answer 1

If You have Any Query Regarding this please ask in comment section I will be there to solve all your query in comment section immediately hope you will like it

include.h file

#ifndef H_340
#define H_340

#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>

#include <climits>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stdexcept>

#include <algorithm>
#include <array>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#include <assert.h>
#include <string.h>

using namespace std;
using namespace std::placeholders;
#endif

definition.h file

#include "includes.h"

#ifndef H_PROG5
#define H_PROG5

#define NO_ITEMS 12    // max no of items printed in single line

// class to generate name tags for soldiers

class SEQ {
private:
    string id;         // name tag for soldier
    unsigned size, nd; // no of soldiers, no of digits in name tags

    // returns no of digits in name tags
    unsigned find_nd ( const double& sz ) {
        if ( ( sz / 26 ) <= 1 ) return 2;
        else return ( find_nd ( sz / 26 ) + 1 );
    }

public:
    // constructor for name-tag generator
    SEQ ( const unsigned& s = 1 ) : size ( s ) {
        double sz = ( double ) size / 9; nd = find_nd ( sz );
        id = string ( nd, 'A' ); id [ nd - 1 ] = '1'; 
    }

    // returns next name tag in sequence
    string operator ( ) ( ) {
        string tmp = id; int i = nd - 1;
        if ( id [ i ] < '9' ) id [ i ]++;
        else {
            id [ i ] = '1'; bool flag = true;
            for ( i--; i >= 0 && flag; i-- )
                if ( id [ i ] < 'Z' ) { id [ i ]++; flag = false; }
                else id [ i ] = 'A';
        } 
        return tmp;
    }
};

// reads and initializes all input arguments
void init_vals ( vector <string>&, unsigned&, unsigned&, unsigned& );

// prints all name tags for remaining soldiers after elimination
void print_vector ( const vector <string>&, const unsigned& );
#endif

josephus.cc Filename

#include "definitions.h"


int main()
{
        vector <string> vect;                                                                                                                                     //vector to hold data

        typedef vector <string> ::iterator vsi;                                                                                                   //typedef string itterator

                                                                                                                                                                                        //input variabbles

        unsigned int n;                                                                                                                                                 //number of soldiers
        unsigned int m;                                                                                                                                                 //count number for removal
        unsigned int k;                                                                                                                                                 //times to print the list

        unsigned int cnt = 0;

        cout << "Number of people? ";                                                                                                                     //prompt for number of soldiers                                                                 
        cin >> n;                                                                                                                                                         //store input for number of soldiers
        cout << "Index for elimination? ";                                                                                                                //prompt for count
        cin >> m;                                                                                                                                                         //gather count from stdin
        cout << "Index for printing? ";                                                                                                                   //prompt for print times
        cin >> k;                                                                                                                                                         //gather print from stdin

        init_vals(vect, n, m, k);                                                                                                                               //fill vector with values

        print_vector(vect, cnt);                                                                                                                                //print vector initial values

        vsi loop = vect.begin();                                                                                                                                //loop itterator
        vsi begin = vect.begin();                                                                                                                               //beginning iterator
        vsi end = vect.end();                                                                                                                                   //end itterator

        unsigned int i = 1;                                                                                                                                             //starting position for iner loop

        
        while (vect.size() > 1)                                                                                                                                      //while loop runs until vector size is 1
        {                                                                                                                                                                               
                while (i < m)                                                                                                                                                //inner loop runs M times
                {
                        if (loop == vect.end())                                                                                                                 //when loop itearator reaches the end of
                        {                                                                                                                                                               //the container is set to the beginning
                                loop = vect.begin();                                                                                                            //to continue iterating
                        }

                        loop = loop + 1;                                                                                                                                //increment the loop 1 space each time
                        i++;                                                                                                                                                    //increment the number of times counted to M

                }
                

                if (loop == vect.end())                                                                                                                         //check if the iterator is past the end of the
                {                                                                                                                                                                       //containner and reset it back to the beginning
                        loop = vect.begin();
                }
                
                        loop = vect.erase(loop);                                                                                                                //delete the calue loop is currently pointing to
                                                                                                                                                                                        //and set it to the next position in the container

                        i = 1;                                                                                                                                                  //reset counter for inner while loop back to 1
                        cnt++;
                        
                        if ((cnt % k) == 0)
                        {
                                print_vector(vect, cnt);
                        }

        }

        print_vector(vect, cnt);
        
        system("Pause");

        return 0;
}

void init_vals(vector < string >& v, unsigned int & N, unsigned int & M, unsigned int& K)
{
        typedef vector <string> ::iterator vsi;                                                                                           //typedef string itterator

        v.resize(N);                                                                                                                                            //resize the vector to the input value

        vsi loop = v.begin();                                                                                                                           //loop itterator
        vsi begin = v.begin();                                                                                                                          //beginning iterator
        vsi end = v.end();                                                                                                                                      //end itterator
        
        for (; loop != v.end(); loop++)                                                                                                 //fill up the vector with values
        {
                generate(begin, end, SEQ(N));                                                                                                   //generate values off function object
                
        }

}

void print_vector(const vector < string >& v, const unsigned int & cnt)
{
        cout << endl;

        typedef vector <string> ::const_iterator vsi;
        if (cnt == 0)
        {
                cout << "Initial group of people" << endl;

        }
        else
        {
                cout << "After eliminating " << cnt << "th person" << endl;
        }
        cout << "-----------------------------" << endl;

        int count = 0;

        vsi loop = v.cbegin();

        for (; loop != v.cend(); ++loop)
        {
                cout << *loop << " ";

                count++;

                if ((count % NO_ITEMS) == 0)
                        cout << endl;

        }
        cout << endl;
        cout << endl;
}