fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct _Node{
  5.     int number;
  6.     struct _Node* next;
  7. }Node;
  8. Node *createList(int n);
  9. void freeList(Node* head);
  10. int solveJosephus(Node **head, int step);
  11.  
  12. int n;
  13.  
  14. int main(){
  15.     long long k;
  16.     while( scanf("%d%d", &n, &k)!=EOF ){
  17.         Node *head;
  18.         // get the beginning position of head
  19.         // head to store the Node
  20.         head = createList(n);
  21.         printf( "%d\n", solveJosephus(&head, k) );
  22.         //freeList(head);
  23.     }
  24.     return 0;
  25. }
  26.  
  27. //linked list
  28. Node *createList(int n)
  29. {
  30.     Node *head, *now;
  31.     for(int i=1; i<=n; i++)
  32.     {
  33.         //建一個linked list 要創一個新的list把它塞進去
  34.         Node *newN = (Node*)malloc(sizeof(Node));
  35.  
  36.         newN->number = i;
  37.         if(i==1) head = newN;
  38.         else now->next = newN;
  39.         now = newN;
  40.     }
  41.     now->next = head;
  42.     return head;
  43. }
  44.  
  45. //finding the number left
  46. int solveJosephus(Node **head, int step)
  47. {
  48.     Node *p, *q;
  49.     p = *head;
  50.     while(p->next != p)
  51.     {
  52.         if(n<=step)
  53.         {
  54.             int tmp = step;
  55.             tmp = tmp%n;
  56.             for(int i=1; i<tmp-1; i++)
  57.             {
  58.                 p = p->next;
  59.                 n = n - 1;
  60.                 tmp = step;
  61.                 tmp = tmp % n;
  62.                 if(tmp==1)
  63.                 {
  64.                     q = p->next;
  65.                     p->next = q->next;
  66.                     p = p->next;
  67.                     free(q);
  68.                 }
  69.             }
  70.             q = p->next;
  71.             //做 接 的動作
  72.             p->next = q->next;
  73.             p = p->next;
  74.             free(q);
  75.  
  76.             n = n - 1;
  77.             tmp = step;
  78.             tmp = tmp % n;
  79.         }
  80.         else
  81.         {
  82.             for(int i=1; i<step-1; i++)
  83.             {
  84.                 p = p->next;
  85.             }
  86.             q = p->next;
  87.             p->next = q->next;
  88.             p = p->next;
  89.             free(q);
  90.         }
  91.     }
  92.     return p->number;
  93. }
  94.  
  95. //free the old data
  96. void freeList(Node *head)
  97. {
  98.  
  99. }
  100.  
Success #stdin #stdout 0s 5660KB
comments (?)
stdin
copy 
41 3
stdout
copy 
31
https://ideone.com/zlOTVD
language:
C (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!