C++ Question: The Josephus problem is the following game: N people, number 1 to

Question

C++ Question: The Josephus problem is the following game: N people, number 1 to N, are sitting in a circle. Starting at person 1, a hot potato is passed. After M passes, the person holding the hot potato is eliminated, the circle closes ranks, and the game continues with the person who was sitting after the eliminated person picking up the hot potato. The last remaining person wins. Thus, if M = 0 and N = 5, players are eliminated in order, and player 5 wins. If M = 1 and N = 5, the order of elimination is 2, 4, 1, 5.

Write a program to solve the Josephus problem for general values of M and N.

The goal of this assignment is to identify the performance and implementation tradeoffs between various ADTs (linked list, vector).

Your task is to provide two different implementations for the Josephus problem using STL list and vector, respectively. Your program should build upon the following source code:

VectorMyJosephus.h

ListMyJosephus.h

Using the above source code, implement your own VectorMyJosephus.cpp and ListMyJosephus.cpp. Feel free to add more functions as needed for your implementation. The above source code is provided to give you a template to start with. You will have to make whatever changes necessary to complete, compile and get it working.

For your testing, conduct the following two sets of experiments separately:

Experiment #1:    Keep M fixed at 3, and vary N in powers of two starting from 4,8,16,32,.. up to at least 262,144. Go even higher if possible, as long as the overall time is under a few minutes.

Experiment #2:    Keep N fixed (at say 262,144) and vary M in powers of two starting from 2,4,8,... up to the largest power of 2 less than N.

What to submit:

Complete set of source code.

A simple report (in doc or PDF) on your experimental Results. You should report and compare the performance (running time) of the list and vector implementations based on your observations, and provide justification for your observations.

Explanation / Answer

The c++ program using linked list is given below:

#include<ListMyJosephus.h>
#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<list>
using namespace std;

struct Node
{
int data;
struct Node *next;
};

Node *newNode(int data)
{
Node *temp = new Node;
temp->next = temp;
temp->data = data;
}

void getWinnerPosition(int m, int n)
{
//Making a circular linked list
Node *first = newNode(1);
Node *prev = first;
for (int i = 2; i <= n; i++)
{
prev->next = newNode(i);
prev = prev->next;
}
prev->next = first;

Node *ptr1 = first, *ptr2 = first;
while (ptr1->next != ptr1)
{

int count = 1;
while (count != m)
{
ptr2 = ptr1;
ptr1 = ptr1->next;
count++;
}

ptr2->next = ptr1->next;
ptr1 = ptr2->next;
}

printf ("Winner is %d ",
ptr1->data);
}

int main()
{
cout<<"Enter the values of n & m"<<endl;
int n,m;
cin>>n>>m;
getWinnerPosition(m, n);
return 0;
}

The program using Vectors is given below:

#include<VectorMyJosephus.h>

#include <iostream>

#include <vector>

#include <numeric>

using namespace std;

int main(){
int n,m;
cout<<"Enter the values of N & M respectively "<<endl;
cin >> n>>m;

//fill the v with 1,2,3...n
vector <int> v;
for(int i=1;i<=n;i++)v.push_back(i);

int index = -1;
while (v.size() > 1) {
//advance by m
index = (index + m) % v.size();

//execute Person
v.erase(v.begin() + (index));

//readjust to compensate for missing element
--index;
}
cout << "Winner is" << v.front() << ". ";
}

Experiment results:

Using VECTORS:

Experiment 1 :
m n time(in seconds)
3 4 time: 0
3 8 time: 0
3 16 time: 0
3 32 time: 0
3 64 time: 0
3 128 time: 0
3 256 time: 0
3 512 time: 0
3 1024 time: 0
3 2048 time: 0
3 4096 time: 2
3 8192 time: 4
3 16384 time: 10
3 32768 time: 44
3 65536 time: 184
3 131072 time: 828
3 262144 time: 3601

Experiment 2:

n m time(in seconds)
262144 4 time: 3469
262144 8 time: 3237
262144 16 time: 3079
262144 32 time: 3041
262144 64 time: 3002
262144 128 time: 2962
262144 256 time: 3007
262144 512 time: 2969
262144 1024 time: 3044
262144 2048 time: 2973
262144 4096 time: 3111
262144 8192 time: 3085
262144 16384 time: 3044
262144 32768 time: 2996
262144 65536 time: 2986
262144 131072 time: 3010

Using LINKED LIST:

Experiment 1:

m n time(in seconds)
3 4 time: 0
3 8 time: 0
3 16 time: 0
3 32 time: 0
3 64 time: 0
3 128 time: 0
3 256 time: 0
3 512 time: 0
3 1024 time: 0
3 2048 time: 0
3 4096 time: 0
3 8192 time: 0
3 16384 time: 0
3 32768 time: 4
3 65536 time: 4
3 131072 time: 12
3 262144 time: 28

Experiment 2:

n m time(in seconds)
262144 4 time: 28
262144 8 time: 38
262144 16 time: 55
262144 32 time: 96
262144 64 time: 166
262144 128 time: 347
262144 256 time: 629
262144 512 time: 1216
262144 1024 time: 2446
262144 2048 time: 4919
262144 4096 time: 10648
262144 8192 time: 19806
262144 16384 time: 38807
262144 32768 time: 75860

after that the program started taking a lot of time.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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