The following code is based on the Josephus problem, the code does compile and g
ID: 3792158 • Letter: T
Question
The following code is based on the Josephus problem, the code does compile and gives me an answer but it's not the right answer according to how the josephus problem works.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
class Node
{
public int iData;
public Node next;
public Node(int x) {
iData = x;
}
public void displayNode() {
System.out.print(iData + " ");
}
}
class CircularList
{
private Node first;
private Node last;
private Node current;
private int count; // total items in the list
public CircularList getCurrent;
public CircularList() {
first = null;
last = null;
current = null;
count = 0;
}
public boolean isEmpty() {
return first == null;
}
public void step() {
current = current.next;
}
public Node getCurrent() {
return current;
}
public Node getFirst() {
return first;
}
public void insert(int x) {
Node newNode = new Node(x);
if (isEmpty()) {
first = newNode;
current = first;
} else {
current.next = newNode;
}
newNode.next = first;
last = newNode;
step();
count++;
}
public boolean search(int x) {
Node search = first;
int y = 0;
while (search.iData != x && y < count) {
search = search.next;
y++;
}
if (search.iData == x) {
System.out.println("Found the value: " + search.iData);
return true;
} else {
System.out.println("Value not found in list");
return false;
}
}
public void delete(int x) {
Node prev = first;
Node curr = first.next;
while (curr.iData != x) {
prev = curr;
curr = curr.next;
}
if (count == 1) {
first = null;
count--;
} else if (curr == first) {
prev.next = curr.next;
first = curr.next;
count--;
} else {
prev.next = curr.next;
count--;
}
}
public void displayList() {
int x = 0;
Node printer = first;
while (x < count) {
printer.displayNode();
printer = printer.next;
x++;
}
System.out.println("");
}
}
class Josephus
{
private int numOfPeople; // number of people in a circle
private int countNum; // number used for counting off
private Node head;
private Node tail;
CircularList circle;
public Josephus() {
circle = new CircularList();
numOfPeople = 0;
countNum = 0;
}
public void setNumOfPeople(int x) {
numOfPeople = x;
}
public int getNumOfPeople() {
return numOfPeople;
}
public void setCountNum(int x) {
countNum = x;
}
public int getCountNum() {
return countNum;
}
public void addPeople() {
for (int i = 1; i < numOfPeople; i++) {
circle.insert(i);
}
}
public void move() {
for (int i = 0; i < countNum; i++) {
tail = head;
head = head.next;
}
System.out.println("KILLED : " + head.iData);
}
public void execute() {
tail = null;
head = circle.getFirst();
while (numOfPeople != 2) {
move();
circle.delete(head.iData);
tail = tail.next;
head = head.next;
numOfPeople--;
display();
}
}
public void display() {
System.out.print("Alive: ");
circle.displayList();
}
}
public class Test
{
public static void main(String[] args) {
Josephus suicide = new Josephus();
suicide.setNumOfPeople(20);
suicide.addPeople();
suicide.display();
suicide.setCountNum(12);
suicide.execute();
}
}
/*
Output
Entre cantidad de personas
10
Entre cantidad de personas muertas
1
Muertas: 1
2 3 4 5 6 7 8 9 10 Muertas: 2
3 4 5 6 7 8 9 10 Muertas: 3
4 5 6 7 8 9 10 Muertas: 4
5 6 7 8 9 10 Muertas: 5
6 7 8 9 10 Muertas: 6
7 8 9 10 Muertas: 7
8 9 10 Muertas: 8
9 10 Muertas: 9
10El sobreviviente es: 10
Press any key to continue . . .
*/
Explanation / Answer
The Josephus problem is described as:
There are n people 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 and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle.
The task is to choose the place in the initial circle so that you are the last one remaining and so survive.
The logic should be like this:
josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1
josephus(1, k) = 1
Program to test the above logic
int main()
{
int n = 17;
int k = 5;
printf("The chosen place is %d", josephus(n, k));
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.