Josephus Election A. Implement the code below, document, test and submit a full

Question

Josephus Election

A. Implement the code below, document, test and submit a full report.

B. Describe how you could implement this using an array instead of the node class.

C .Implement your design in problem B (explain)

//Josephus Problem

#include <iostream>

#include <cstdlib>

using namespace std;

class node

{

public:

int item; node* next;

node(int x, node* t)

{ item = x; next = t; }

};

typedef node *link;

int main(int argc, char *argv[])

{ int i, N = atoi(argv[1]), M = atoi(argv[2]);

link t = new node(1, 0); t->next = t;

link x = t;

for (i = 2; i <= N; i++)

x = (x->next = new node(i, t));

while (x != x->next)

{

for (i = 1; i < M; i++) x = x->next;

x->next = x->next->next;

}

cout << x->item << endl;

}

Explanation / Answer

Please find the code of array implementation of Joseph problem below :

//Josephus Problem

#include <iostream>

#include <cstdlib>

using namespace std;

int main(int argc, char *argv[])

{ int N = atoi(argv[1]), M = atoi(argv[2]);

//{ int N = 7, M = 3;

int arr[N];

int cnt = N,i=0;

for(int k=0; k<N; k++)

arr[k] = 1;

while(cnt>1)

{

int j = 0;

while(j<M)

{

i = (i+1)%N;

if(arr[i] == 1)

{

j++;

}

}

arr[i] = 0;

cnt--;

}

for(int i=0; i<N; i++)

if(arr[i] == 1)

cout << i << endl;

}

Please let me know if u face any problem understanding the code.

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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