Based on the original Josephus Problem introduced in class, an additional rule of this problem is to change
direction of counting after killing a person. For example, there are 8 people, numbered 1 to 8, in a circle
and arranged in clockwise. The step to kill is 3.
The sequence of killing people is
1, 2, 3 (kill 3, change the direction to counter-clockwise)
2, 1, 8 (kill 8, change the direction to clockwise)
1, 2, 4 (kill 4, change the direction to counter-clockwise)
2, 1, 7 (kill 7, change the direction to clockwise)
1, 2, 5 (kill 5, change the direction to counter-clockwise)
2, 1, 6 (kill 6, change the direction to clockwise)
1, 2, 1 (kill 1)
So the person numbered 2 is the survivor.
You're asked to solve this problem using circular linked list.
You will be provided with main.c and function.h, and you need to implement function.c.
Note there is a time limit to solve this problem: 3 seconds.
Note that you can use the following partial code.
#include <stdio.h>
#include <stdlib.h>
#include "function.h"
man* createList(int n){
int i;
man* curr;
head = (man*)malloc(sizeof(man));
curr = head;
curr->id = 1;
for(i=2; i<=n; i++){
curr->next = (man*)malloc(sizeof(man));
curr->next->prev = curr;
curr = curr->next;
curr->id = i;
}
curr->next = head;
head->prev = curr;
return head;
}
int solveJosephus(int step){
}
The input has two integers, n and m, where n is the number of total people, and m is the step to kill.
The output is an integer: the survivor's number. There is a newline after that.