Question

• Implement the codes must use the LinkedList implementation

• Add an additional empty node (“dummy node”) that connects the end of the list with the beginning, transforming the list to a circular list

Code in c++

The Josephus problem is named after the historian Flavius Josephus, who lived between the years 37 and 100 CE. Josephus was a reluctant leader of the Jewish revolt against the Roman Empire. When it appeared that Josephus and his band were to be captured, they resolved to kill themselves. Josephus persuaded the group by saying, “Let us commit our mutual deaths to determination by lot. He to whom the first lot falls, let him be killed by him that hath the second lot, and thus fortune shall make its progress through us all; nor shall any of us erish by his own right hand, for it would be unfair if, when the rest are gone, somebody should repent and save himself” (Flavius Josephus, The Wars of the Jews, Book III, Chapter 8, Verse 7, tr. William Whiston, 1737). Yet that is exactly what happened; Josephus was left for last, and he and the person he was to kill surrendered to the Romans. Although Josephus does not describe how the lots were assigned, the following approach is generally believed to be the way it was done. People form a circle and count around the circle some predetermined number. When this number is reached, that person receives a lot and leaves the circle. The count starts over with the next person. Using the circular linked list developed in Exercise 6, simulate this problem.

Your program should take two parameters: n, the number of people that start, and

m, the number of counts. For example, try n = 20 and m = 12. Where does Josephus need to be in the original list so that he is the last one chosen?

Answer 1

#include<bits/stdc++.h>
using namespace std;
  

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

Node *newNode(int pos)
{
Node *temp = new Node;
temp->next = temp;
temp->position = pos;
}
  
/* Function to find the only person left
after one in every m-th node is killed
in a circle of n nodes */
void josephusPosition(int m, int n)
{
// Create a circular linked list of
// size N.
Node *head = newNode(1);
Node *prev = head;
for (int i = 2; i <= n; i++)
{
prev->next = newNode(i);
prev = prev->next;
}
prev->next = head; // Connect last
// node to first
  
/* while only one node is left in the
linked list*/
Node *ptr1 = head, *ptr2 = head;
while (ptr1->next != ptr1)
{
// Find m-th node
int count = 1;
while (count != m)
{
ptr2 = ptr1;
ptr1 = ptr1->next;
count++;
}
  
/* Remove the m-th node */
ptr2->next = ptr1->next;
free(ptr1);
ptr1 = ptr2->next;
}
  
cout<<"Position of Josephus in orignal list is: "<<ptr1->position<<endl;
}
  

int main()
{
int n, m;
cout<<"Enter number of persons(n)"<<endl;
cin>>n;
cout<<"Enter the count(m)"<<endl;
cin>>m;
josephusPosition(m, n);
return 0;
}