I've been tryin for a while but i cant figure out how to make the program below take N as input and generate an M in order that the last soldier that dies is the 13th(N>13);
int main()
{
int N, M;
struct node { int player_id; struct node *next; };
struct node *p, *q;
int i, count;
printf("Enter N (number of players): "); scanf("%d", &N);
printf("Enter M (every M-th payer gets eliminated): "); scanf("%d", &M);
// Create circular linked list containing all the players:
p = q = malloc(sizeof(struct node));
p->player_id = 1;
for (i = 2; i <= N; ++i) {
p->next = malloc(sizeof(struct node));
p = p->next;
p->player_id = i;
}
p->next = q;//Close the circular linkedlist by having the last node point to the 1st
// Eliminate every M-th player as long as more than one player remains:
for (count = N; count > 1; --count) {
for (i = 0; i < M - 1; ++i)
p = p->next; p->next = p->next->next;
// Remove the eiminated player from the circular linked list.
} printf("Last player left standing is %d\n.", p->player_id);
return 0;
}
the result should be the same as this one(but I need it in linked lists cos i dont understand that one):>.
I didn't read all the code above, I think it can find the last item for given N and M
According to the original problem, 12<N<100. So, probably it can be solved in the given time limit simply with brute force.
Nm from 1 m. If the last item is 13, return the loop variable.EDIT:
You don't have to work a lot. You just simply start a loop instead of reading M.
M=1;
while(1)
{
//your code goes here:
//build up the linked list with N element
//eliminate the nodes, until only one remains
//instead of writing out the last number, you check it: if it equals 13 print M, if doesn't, increment `M` and continue the loop.
if(p->player_id==13)
{
printf("The minimal M is: %d\n", M);
break;
}
else
M++;
}
If You want to do this for multiple N-s, You can put this loop into a function. In this case insted of printing M, the function should return it.
The funny thing is: The linked list part is done by You. Maybe You should try simpler exercises first.
EDIT 2: HERE is my final answer, check the structure and the output, I hope it is understandable.
NOTE: I think if You really want to learn, You should do something like this instead of jumping in a not trivial problem: