基本算法——约瑟夫环问题

关于约瑟夫环问题，我们可以从两种思路去实现，一种是用数组，另一种是采用链表。

用数组方法实现代码:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #define M 8
 5 int find(int *arr, int len);
 6 int main(int argc, char* argv[])
 7 {
 8     int size = atoi(argv[1]);
 9     int* arr = (int*)calloc(size, 4);
10     int index ;
11     for(index = 0; index < size ; index ++)
12     {
13         arr[index] = index + 1 ;
14     }
15     printf("
winner: %d 
", find(arr, size));
16     return 0 ;
17 }
18 int find(int *arr, int len)
19 {
20     int index , step ;
21     int size = len ;
22     index = 0 ;
23     step = 0 ;
24     while(len > 1)
25     {
26         if(arr[index] != 0)
27         {
28             ++step ;
29             if(step == M)
30             {
31                 printf("%3d", index + 1);
32                 arr[index] = 0 ;
33                 step = 0 ;
34                 len -- ;
35             }
36         }
37         index = (index + 1) % size ;
38     }
39     for(index = 0 ; index < size ; index ++)
40     {
41         if(arr[index] != 0)
42         {
43             return arr[index] ;
44         }
45     }
46 }

View Code

该方法就是采用一个计数，同时还要有一个变量来跟随数组下标，每当计数与我们规定的退出值相等时，将数组中当前下标的值置为0，无形中增加了许多判断。

用链表方法实现代码:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #define M 8
 5 typedef struct tag
 6 {
 7     int num;
 8     struct tag *next;
 9 }Node, *pNode;
10 void link_create(pNode *head, int size);
11 void link_del(pNode *head, int a);
12 int find(pNode *head, int size);
13 int main(int argc, char* argv[])
14 {
15     int size = atoi(argv[1]);
16     pNode head;
17     link_create(&head, size);
18     printf("
winner: %d 
", find(&head, size));
19     return 0 ;
20 }
21 
22 int find(pNode *head, int size)
23 {
24     pNode  pcur = *head, ppre = NULL;
25     int step = 1;
26     while(size > 1)
27     {
28         if(step == M)
29         {
30             step = 1;
31             printf("%3d", pcur->num);
32             pNode p = pcur;
33             ppre->next = pcur->next;
34             free(p);
35             pcur = ppre->next;
36             -- size;
37         }
38         else
39         {
40             ++ step;
41             ppre = pcur;
42             pcur = pcur->next;
43         }
44     }
45     return pcur->num;
46 }
47 
48 void link_create(pNode *head, int size)
49 {
50     pNode p;
51     *head = NULL;
52     while(size > 0)
53     {
54         p = (pNode)calloc(1, sizeof(Node));
55         p->num = size;
56         p->next = *head;
57         *head = p;
58         -- size;
59     }
60     p = *head;
61     while(p->next)
62     {
63         p = p->next;
64     }
65     p->next = *head;
66 }

View Code

在这里，我们创建一个链表环，这样，每次计数增加时，链表会指向下一个，无需我们再去跟踪该位置是哪个，我们只需判断计数是否为我们规定的退出值，让链表一直循环即可，当链表中只剩下一个元素是，该值就是我们的胜利者。

在该链表中，我们采用了一种创建环的方法，即将链表的尾指针指向头指针，这里需要注意一下。