首页 > 代码库 > 基本算法——约瑟夫环问题
基本算法——约瑟夫环问题
关于约瑟夫环问题，我们可以从两种思路去实现，一种是用数组，另一种是采用链表。
用数组方法实现代码:
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("\nwinner: %d \n", 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 }
该方法就是采用一个计数，同时还要有一个变量来跟随数组下标，每当计数与我们规定的退出值相等时，将数组中当前下标的值置为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("\nwinner: %d \n", 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 else39 {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 }
在这里，我们创建一个链表环，这样，每次计数增加时，链表会指向下一个，无需我们再去跟踪该位置是哪个，我们只需判断计数是否为我们规定的退出值，让链表一直循环即可，当链表中只剩下一个元素是，该值就是我们的胜利者。
在该链表中，我们采用了一种创建环的方法，即将链表的尾指针指向头指针，这里需要注意一下。
基本算法——约瑟夫环问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。