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.

main.cpp

#include <iostream>

#include <iomanip>

//#include "/home/cs340/progs/16f/p5/prog5.h"

#include "prog5.h"

using std::cout; using std::endl; using std::cin;

using std::advance;

const int TAGS_LINE = 12;

int main() {

   in_args josephusStruct; //creates a struct to hold values for Josephus Problem

   vector<string> josephusVec; //creates a vector to hold the names for Josephus Problem

   unsigned cnt = 1; //count of number of passes

   cout << "\nNumber of soldiers? 41"; //Sets values to corresponding members of the struct

   josephusStruct.N = 41;

   cout << "\nIndex for emlination? 3";

   josephusStruct.M = 3;

   cout << "\nIndex for printing? 7 \n";

   josephusStruct.K = 7;

   init_vals(josephusVec, josephusStruct); //calles function to fill up vector

   print_vector(josephusVec, cnt); //prints the intital vector with all names before elimation begins

   josephusStruct.M -= 1; //adjusts elimation index

   auto indexIt = josephusStruct.M % josephusVec.size(); //iterator to be used for index elimation

   while(josephusVec.size() >1) { //runs until only one left in vector

       auto vecIter = josephusVec.begin(); //iterator for vector

       advance(vecIter, indexIt); //advances to Mth spot in the vector

       josephusVec.erase(vecIter); //deletes that element in the vector

       indexIt += josephusStruct.M; //adjuts iterator for index elimation

       indexIt %= josephusVec.size();

       if( (cnt % josephusStruct.K == 0 && cnt != 0) || josephusVec.size() == 1) //prints out vector with the header every Kth time

           print_vector(josephusVec, cnt);

       cnt++; //increment number of passes

   }

   cout << endl;

   return 0;

}

void init_vals(vector<string>& vec, in_args& in) {

   vec.resize(in.N);

   generate(vec.begin(), vec.end(), SEQ(in.N));

}

void print_vector(const vector<string>& vec, const unsigned& cnt) {

   vector<string>::const_iterator vecIt; //iterator to print items in vector

   int itemCnt = 0; //count for items per line

   if(cnt < 2) { //prints out the intial group header

       cout << "\n Initial group of soldiers \n"

            << "" << endl;

   }

   else { //prints out after elimation group header

       cout <<"\n After emliminating the " << cnt << "th soldier" << endl

            << "" << endl;

   }

   for(vecIt = vec.begin(); vecIt != vec.end(); vecIt++) { //for loop to iterate thrpugh items in vector and print them

       if(itemCnt % TAGS_LINE == 0 && itemCnt != 0) //prints a new line once desiered number of items per line is reached

           cout << endl;

       cout << *vecIt << " ";

       itemCnt++;

   }

   cout << endl;

}

pro5.h

#ifndef H_PROG5

#define H_PROG5

#include <algorithm>

#include <iostream>

#include <string>

#include <vector>

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 in_args {

   unsigned N,       // total no of soldiers

            M,       // count to eliminate soldier

            K;       // frequency of printouts

};

// 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 / 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 ( vector <string>&, unsigned&, unsigned&, unsigned& );

void init_vals ( vector <string>&, in_args& );

// prints all name tags for remaining soldiers after elimination

void print_vector ( const vector <string>&, const unsigned& );

#endif