dzungchaos

CTDL&TT: Bài toán Josephus

May 31st, 2020
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.81 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct node
  5. {
  6.     int num;
  7.     struct node *next;
  8. };
  9.  
  10. void create(struct node **);
  11. void display(struct node *);
  12. int survivor(struct node **, int);
  13.  
  14. int main()
  15. {
  16.     struct node *head = NULL;
  17.     int survive, skip;
  18.  
  19.     create(&head);
  20.     printf("The persons in circular list are:\n");
  21.     display(head);
  22.     printf("Enter the number of persons to be skipped: ");
  23.     scanf("%d", &skip);
  24.     survive = survivor(&head, skip);
  25.     printf("The person to survive is : %d\n", survive);
  26.     free(head);
  27.  
  28.     return 0;
  29. }
  30.  
  31. int survivor(struct node **head, int k)
  32. {
  33.     struct node *p, *q;
  34.     int i;
  35.  
  36.     q = p = *head;
  37.     while (p->next != p)
  38.     {
  39.         for (i = 0; i < k - 1; i++)
  40.         {
  41.             q = p;
  42.             p = p->next;
  43.         }
  44.         q->next = p->next;
  45.         printf("%d has been killed.\n", p->num);
  46.         free(p);
  47.         p = q->next;
  48.     }
  49.     *head = p;
  50.  
  51.     return (p->num);
  52. }
  53.  
  54. void create (struct node **head)
  55. {
  56.     struct node *temp, *rear;
  57.     int a, ch;
  58.  
  59.     do
  60.     {
  61.         printf("Enter a number: ");
  62.         scanf("%d", &a);
  63.         temp = (struct node *)malloc(sizeof(struct node));
  64.         temp->num = a;
  65.         temp->next = NULL;
  66.         if (*head == NULL)
  67.         {
  68.             *head = temp;
  69.         }
  70.         else
  71.         {
  72.             rear->next = temp;
  73.         }
  74.         rear = temp;
  75.         printf("Do you want to add a number [1/0]? ");
  76.         scanf("%d", &ch);
  77.     } while (ch != 0);
  78.     rear->next = *head;
  79. }
  80.  
  81. void display(struct node *head)
  82. {
  83.     struct node *temp;
  84.  
  85.     temp = head;
  86.     printf("%d   ", temp->num);
  87.     temp = temp->next;
  88.     while (head != temp)
  89.     {
  90.         printf("%d   ", temp->num);
  91.         temp = temp->next;
  92.     }
  93.     printf("\n");
  94. }
Advertisement
Add Comment
Please, Sign In to add comment