Detail the Joseph ring problem and its related C language algorithm implementation

Joseph ring problem

N people in a circle number sequence, starting from 1 by 1, 2, 3...... Number in order, the person who reported p out of the circle, the rest of the people from 1, 2, 3, and then the person who reported p out of the circle, and so on.    
Please output the original number of each person in exit order  

Algorithm thought
Recursion by mathematical induction.

Both the linked list and the array implementations have one thing in common: to simulate the entire game process, the program is not only tedious to write, but the time complexity is as high as O(nm). If nm is too large, the result cannot be calculated in a short time. We note that the original problem was simply to figure out the number of the final winner, not to ask the reader to simulate the whole process. So if you want to be efficient, you have to break the rules and implement a little bit of math.

For the sake of discussion, let's change the question a little bit.
Problem description: n individuals (no. 0~(n-1)), count from 0, report (m-1) exit, the remaining people continue to count from 0. Find the number of the winner.

We know that after the first person (the number must be m%n-1) leaves the column, the remaining n-1 people form a new Joseph ring (starting with the number k=m%n) :
K + 1 k + 2 k... N minus 2, n minus 1, 0, 1, 2... K minus 2 and start at k with 0.
Now let's switch their Numbers:

K.         -- > 0
K + 1     -- > 1
K + 2     -- > 2
.
.
K - 2     -- > N - 2
K - 1     -- > N - 1
If we know the solution to this subproblem: for example, x is the winner, wouldn't changing this x back from the table above be exactly the solution for n people? !!!!! The formula for going back is very simple, which I believe you can deduce: x'=(x+k)%n

How do we know the solution to the problem of n minus 1 personal Numbers? Yeah, we just need to know the individual solution to n minus 2. What's the personal solution to n minus 2? Of course, the n minus 3 case -- this is obviously a backwardation problem! Ok, so here's the idea. Here's the formula for recursion:

Let f[I] represent the number of the final winner when I play the game and m exits. The final result is naturally f[n].

The recursive formula
F [1] = 0;
[I] = f (f [I - 1) + m) % I; (I > 1)

Implementation method

A circular linked list
Create a circular linked list with N elements, then iterate and count from the top of the list. If the cardinality is I == m, kick out the element and continue the loop until the current element exits the loop at the same time as the next element

       

#include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
    
  typedef struct lnode 
  { 
    int pos; 
    struct lnode *next; 
  } lnode; 
    
    
   
  void create_ring(lnode **root, int loc, int n) 
  { 
    lnode *pre, *current, *new; 
    current = *root; 
    pre = NULL; 
    
    while (current != NULL) { 
      pre = current; 
      current = current->next; 
    } 
    
    new = (lnode *)malloc(sizeof(lnode)); 
    new->pos = loc; 
    new->next = current; 
    
    if (pre == NULL) { 
      *root = new; 
    } else { 
      pre->next = new; 
    } 
    
    //Circular linked list
    if (loc == n) { 
      new->next = *root; 
    } 
  } 
    
   
  void kickoff_ring(lnode *head, int p) 
  { 
    int i; 
    lnode *pre, *pcur; 
    pre = pcur = head; 
    
    while (pcur->next != pcur) { 
      for (i = 1; i < p; i ++) { 
        pre = pcur; 
        pcur = pcur->next; 
      } 
    
      printf("%d ", pcur->pos); 
      pre->next = pcur->next; 
      free(pcur); 
      pcur = pre->next; 
    } 
    printf("%dn", pcur->pos); 
    free(pcur); 
  } 
    
    
  void print_ring(lnode *head) 
  { 
    lnode *cur;  
    cur = head; 
    
    while (cur->next != head) { 
      printf("%d ", cur->pos); 
      cur = cur->next; 
    } 
    printf("%dn", cur->pos); 
  } 
    
  int main() 
  { 
    int i, p, n; 
    lnode *head; 
    
    while (scanf("%d %d", &n, &p) != EOF) { 
      //Build the loop list
      for (i = 1, head = NULL; i <= n; i ++) 
        create_ring(&head, i, n); 
    
      //Joseph ring
      if (p != 1)  
        kickoff_ring(head, p); 
      else 
        print_ring(head); 
    } 
    
    return 0; 
  } 

      / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
              Problem: 1188
              User: wangzhengyi
              Language: C
              Result: Accepted
              Time: 110 ms
              Memory: 912 KB
      * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /  

Two, array simulation
The idea is similar to a circular list, with less of the process of building a circular list

     

 #include <stdio.h> 
  #include <stdlib.h> 
   
  int main() 
  { 
    int i, index, p, n, remain, delete[3001], flag[3001] = {0}; 
   
    while (scanf("%d %d", &n, &p) != EOF) { 
      remain = n; 
      index = 0; 
      while (remain >= 1) { 
        for (i = 0; i < n; i ++) { 
          if (flag[i] == 0) { 
            //Count off
            index ++; 
            //P out of the loop
            if (index == p) { 
              //Withdraw from the outside
              flag[i] = 1; 
              //Count off again
              index = 0; 
              delete[remain - 1] = i + 1; 
              remain --; 
            }   
          }   
        } 
      } 
   
      //Output the serial number of each exit person
      for (i = n - 1; i >= 0; i --) { 
        if (i == 0) { 
          printf("%dn", delete[i]); 
        } else { 
          printf("%d ", delete[i]); 
        } 
      } 
    } 
   
    return 0; 
  } 

      3. Mathematical derivation
             

#include <stdio.h> 
   
  int main(void) 
  { 
    int i, n, m, last; 
   
    while (scanf("%d", &n) != EOF && n != 0) { 
      //Receive a count
      scanf("%d", &m); 
   
      //Joseph ring problem
      for (i = 2, last = 0; i <= n; i ++) { 
        last = (last + m) % i; 
      } 
      printf("%dn", last + 1); 
    } 
   
    return 0; 
  }