The Josephus Problem using C++

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 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` container to store the names of `N` people.

- `void init_vals(list &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:

```c++ struct args

{

unsigned N;

unsigned M;

unsigned K;

}; ```

- `void print_list(const list &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`.

** 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.

- Add documentation to the appropriate source files as discussed in your class.

josephus.h file:

#ifndef H_JOSEPHUS

#define H_JOSEPHUS

#include

#include

#include

#include

#include

using namespace std;

#define NO_LETS 26 // no of letters in English alphabet

#define NO_ITEMS 12 // no of items printed on single line

// struct for input arguments

struct args {

unsigned N, // no of initial people

M, // count to eliminate person

K; // frequency of printouts

};

// class to generate name tags for people

class SEQ {

private:

string id; // name tag for person

unsigned size, nd; // no of people, no of digits in name tags

// returns no of digits in name tags

unsigned find_nd ( const double& sz ) {

if ( ( sz / NO_LETS ) <= 1 ) return 2;

else return ( find_nd ( sz / NO_LETS ) + 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(list &, args &);

// prints all name tags for remaining people after elimination

void print_list ( const list < string >&, const unsigned& );

#endif

expected output

Number of people? 41 Index for elimination? 3 Index for printing? 7

Initial group of people ----------------------- A1 A2 A3 A4 A5 A6 A7 A8 A9 B1 B2 B3 B4 B5 B6 B7 B8 B9 C1 C2 C3 C4 C5 C6 C7 C8 C9 D1 D2 D3 D4 D5 D6 D7 D8 D9 E1 E2 E3 E4 E5

After eliminating 7th person ---------------------------- A1 A2 A4 A5 A7 A8 B1 B2 B4 B5 B7 B8 C1 C2 C4 C5 C6 C7 C8 C9 D1 D2 D3 D4 D5 D6 D7 D8 D9 E1 E2 E3 E4 E5