约瑟夫环
Jimmy
posted @ 2011年10月24日 01:01
in Others
, 1371 阅读
1.问题描述：n个人（编号1~n)，从1开始报数，报到m的退出，剩下的人继续从1开始报数。按顺序输出列者编号
模拟过程，使用循环链表或者数组，但是链表便于删除，效率更高。使用循环链表的C代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | <span style="font-size:16px;">#include <stdio.h>#include <stdlib.h>struct node{ int value; struct node *next;};typedef struct node list;int main(){ int n, m; int i; while(scanf("%d%d", &n, &m) != EOF) { list *head, *tmp, *pre; head = (list*)malloc(sizeof(list)); head -> value = 1; head -> next = NULL; tmp = head; for(i=2; i<=n; i++) { list *node = (list*)malloc(sizeof(list)); node -> value = i; node -> next =NULL; tmp -> next = node; tmp = node; } tmp -> next = head; //link the last to the head pre = tmp; tmp = head; while(tmp -> next != tmp) { for(i=1; i<m; i++) { pre = tmp; tmp = tmp -> next; } //delete the node to which tmp point to pre -> next = tmp -> next; printf("%d ", tmp -> value); free(tmp); tmp = pre -> next; } printf("%d\n", tmp -> value); free(tmp); } return 0;}</span> |
另一种方法是使用数学方法计算，C代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | <span style="font-size:16px;">#include <stdio.h>#include <stdlib.h>int main(){ int n, m; int i , p; int *array, counter; while(scanf("%d%d", &n, &m) != EOF) { i = 0; array = (int*)malloc(sizeof(int)*n); counter = 0; while(++i <= n) { p = i * m; while(p > n) p = p - n + (p - n -1)/(m - 1); array[counter] = p; counter++; } if(counter == 1) printf("%d\n", array[0]); else { for(i=0; i<counter-1; i++) printf("%d ", array[i]); printf("%d\n", array[i]); } free(array); } return 0;}</span> |
两种方法的时间复杂度都是O(n)
2023年9月08日 02:43
Are you ready to embark on an unforgettable journey filled with incredible experiences? Start exploring things to do today and unlock a world of endless possibilities. Let's dive in and discover the best things to do near me together!"