X-Kingdom has trapped n number of soldiers of their opponent. They want to execute them. They created a strategy so that the prisoners will kill each other and at the end one prisoner will be alive and eventually released. As part of the process, they assigned each trapped soldier a sequence number starting from 1 and ending at n. If n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1 is killed. Finally, the person at position 5 is killed. So, the person at position 3 survives. If n = 7 and k = 3, then the safe position is 4. The people at positions 3, 6, 2, 7, 5, 1 are killed in order, and the person at position 4 survives. Input:n and k Output:Print the list of prisoners in reverse order from n to 1Then reverse the list to print it in correct order from 1 to nDisplay the position number who will survive. You must have to use circular doubly linked list for your solution. You need to declare appropriate doubly linked list node structure to store a soldier with sequence number as the data value. Functions needed; a.) soldier* create_soldier (int sequence): It takes an integer, dynamically allocate a soldier structure and returns a soldier node b.) soldier* create_reverse_circle(int n): It takes an integer and creates a circular doubly linked list with n number of soldiers placed in descending sequence. For example, if n=5 it should produce a circular doubly linked list starting from 5 and ending at 1 as sequence number. After creating the circle, it returns the head of the circular linked list. c.) soldier* rearrange_circle(soldier* head): This function reverse a given circular doubly linked list where head is the head pointer. After reversing the linked list, it returns the head pointer of the updated linked list d.) void display(soldier* head): This function displays a given circular doubly linked list.. head is head pointer of the linked list e.) int kill(soldier* head, int n, int k): This function takes head of the linked list, number of soldiers n, and skip value k as parameter and returns the sequence number of the surviving soldier. Note that in addition to the above functions, you will utilize other linked list functions for insertion, deletion, and you may create more function as you need for your solution.
X-Kingdom has trapped n number of soldiers of their opponent. They want to execute them. They created a strategy so that the prisoners will kill each other and at the end one prisoner will be alive and eventually released. As part of the process, they assigned each trapped soldier a sequence number starting from 1 and ending at n.
If n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1 is killed. Finally, the person at position 5 is killed. So, the person at position 3 survives. If n = 7 and k = 3, then the safe position is 4. The people at positions 3, 6, 2, 7, 5, 1 are killed in order, and the person at position 4 survives.
Input:
n and k
Output:
Print the list of prisoners in reverse order from n to 1
Then reverse the list to print it in correct order from 1 to n
Display the position number who will survive.
You must have to use circular doubly linked list for your solution. You need to declare appropriate doubly linked list node structure to store a soldier with sequence number as the data value.
Functions needed;
a.) soldier* create_soldier (int sequence): It takes an integer, dynamically allocate a soldier structure and returns a soldier node
b.) soldier* create_reverse_circle(int n): It takes an integer and creates a circular doubly linked list with n number of soldiers placed in descending sequence. For example, if n=5 it should produce a circular doubly linked list starting from 5 and ending at 1 as sequence number. After creating the circle, it returns the head of the circular linked list.
c.) soldier* rearrange_circle(soldier* head): This function reverse a given circular doubly linked list where head is the head pointer. After reversing the linked list, it returns the head pointer of the updated linked list
d.) void display(soldier* head): This function displays a given circular doubly linked list.. head is head pointer of the linked list
e.) int kill(soldier* head, int n, int k): This function takes head of the linked list, number of soldiers n, and skip value k as parameter and returns the sequence number of the surviving soldier.
Note that in addition to the above functions, you will utilize other linked list functions for insertion, deletion, and you may create more function as you need for your solution.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
