Josephus problem implementation in C
Josephus problem is a puzzle problem. A group of people are there. They stand in a circle. Every kth person is eliminated until only one remains.
To solve this problem, circular linked list is the best
option.
C implementation:
This
implementation starts from creating Node structure. It has a data and node. There
is a function create_Circle(). It is used to create the memory for node. Create
the nodes as circular linked list.
Josephus elimination function reads the input as number of
persons and k value. Using the k value, keep on moving the circular linked list.
The kth person is eliminated until the last one is remaining.
Code:
#include <stdio.h>
#include <stdlib.h>
//create a Node
structure with data and node
struct cl_Node {
int data;
struct cl_Node
*next;
};
// circular linked list is created
struct cl_Node* create_Circle(int n) {
struct cl_Node
*head = NULL, *prev = NULL, *newNode;
for (int i = 1; i
<= n; i++) {
newNode =
(struct cl_Node*)malloc(sizeof(struct cl_Node));
newNode->data = i;
if (head ==
NULL) {
head =
newNode;
} else {
prev->next = newNode;
}
prev =
newNode;
}
prev->next =
head; // make it circular
return head;
}
// Josephus elimination function
int josephus_pbm(int n, int k) {
struct cl_Node
*head = create_Circle(n);
struct cl_Node
*ptr = head, *prev = NULL;
while
(ptr->next != ptr) { // until last node left
// move k-1
steps
for (int count
= 1; count < k; count++) {
prev =
ptr;
ptr =
ptr->next;
}
// It is used
to eliminate k-th person
printf("Eliminated: %d\n", ptr->data);
prev->next
= ptr->next;
free(ptr);
ptr =
prev->next;
}
int survivor =
ptr->data;
free(ptr);
return survivor;
}
int main() {
int n, k;
printf("Enter
number of people: ");
scanf("%d", &n);
printf("Enter
step count (k): ");
scanf("%d", &k);
int survivor =
josephus_pbm(n, k);
printf("Survivor: %d\n", survivor);
return 0;
}
Output:
Enter number of people: 6
Enter step count (k): 4
Eliminated: 4
Eliminated: 2
Eliminated: 1
Eliminated: 3
Eliminated: 6
Survivor: 5
The implementation of Josephus elimination in c language was
done successfully. Keep Coding!!!!
Comments
Post a Comment