The Josephus Problem
People are standing in a circle (Links to an external site.)Links to an external site. waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only a specified number of persons remain, and are freed. The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the positions in the initial circle to avoid execution. In the original Josephus problem 41 men stand in a circle and decide to kill every 3rd person until 2 men remain who then kill themselves. Write a function that declares a local queue to solve the original Josephus problem as a special case. The function's prototype is vector solveJosephus( int ncandidates, int nsurvivors);
The function returns the positions in the original circle of the survivors. The function returns an empty vector if any of its parameters is bad. What are the characteristics of a bad parameter?
Data Structure C++. Visual Studios 2017
#include <bits/stdc++.h>
using namespace std;
/* structure for a Node */
struct Node {
int data;
Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
/*Utility function to print the circular linked list*/
void printList(Node* head)
{
if (head == NULL)
return;
Node* temp = head;
do {
cout <<
temp->data << "->";
temp =
temp->next;
} while (temp != head);
cout << head->data << endl;
}
/*Function to delete every kth Node*/
void deleteK(Node** head_ref, int k)
{
Node* head = *head_ref;
// If list is empty, simply return.
if (head == NULL)
return;
// take two pointers - current and
previous
Node *curr = head, *prev;
while (true) {
// Check if Node is the
only Node\
// If yes, we reached
the goal, therefore
// return.
if (curr->next ==
head && curr == head)
break;
// Print intermediate
list.
printList(head);
// If more than one Node
present in the list,
// Make previous pointer
point to current
// Iterate current
pointer k times,
// i.e. current Node is
to be deleted.
for (int i = 0; i <
k; i++) {
prev = curr;
curr = curr->next;
}
// If Node to be deleted
is head
if (curr == head)
{
prev = head;
while (prev->next != head)
prev = prev->next;
head = curr->next;
prev->next = head;
*head_ref = head;
free(curr);
}
// If Node to be deleted
is last Node.
else if (curr->next
== head) {
prev->next = head;
free(curr);
}
else {
prev->next = curr->next;
free(curr);
}
}
}
/* Function to insert a Node at the end of
a Circular linked list */
void insertNode(Node** head_ref, int x)
{
// Create a new Node
Node* head = *head_ref;
Node* temp = new Node(x);
// if the list is empty, make the new Node
head
// Also, it will point to itself.
if (head == NULL) {
temp->next =
temp;
*head_ref = temp;
}
// traverse the list to reach the last
Node
// and insert the Node
else {
Node* temp1 =
head;
while (temp1->next !=
head)
temp1 = temp1->next;
temp1->next =
temp;
temp->next =
head;
}
}
/* Driver program to test above functions */
int main()
{
int i;
// insert Nodes in the circular linked
list
struct Node* head = NULL;
for(i=1;i<=41;i++)
{
insertNode(&head, i);
}
int k = 2;
// Delete every kth Node from the
// circular linked list.
deleteK(&head, k);
return 0;
}
The Josephus Problem People are standing in a circle (Links to an external site.)Links to an external site. waiting to be executed. Counting begins at a specified point in the circle and proceeds arou...
In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical prob- lem related to a certain counting-out game.) People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a spec- ified number of people are skipped, the next person is executed. The procedure is repeated with the remain- ing people, starting with the next person, going in...
Need different C code then what has been posted here Problem In this assignment, you have to simulate the Josephus problem. There are n number of prisoners standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller...