Josephu 問題為：設編號為1，2，? n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數，數到m 的那個人出列，它的下一位又從1開始報數，數到m的那個人又出列，依次類推，直到所有人出列為止，由此產生一個出隊編號的序列。 ### 數組實現 ~~~ #include <stdio.h> #include <malloc.h> int Josephu(int n, int m) { int flag, i, j = 0; int *arr = (int *)malloc(n * sizeof(int)); for (i = 0; i < n; ++i) arr[i] = 1; for (i = 1; i < n; ++i) { flag = 0; while (flag < m) { if (j == n) j = 0; if (arr[j]) ++flag; ++j; } arr[j - 1] = 0; printf("第%4d個出局的人是：%4d號\n", i, j); } free(arr); return j; } int main( ) { int n, m; scanf("%d%d", &n, &m); printf("最后勝利的是%d號！\n", Josephu(n, m)); //system("pause"); return 0; } ~~~ ### 鏈表實現 ~~~ #include <stdio.h> #include <malloc.h> typedef struct Node { int index; struct Node *next; }JosephuNode; int Josephu(int n, int m) { int i, j; JosephuNode *head, *tail; head = tail = (JosephuNode *)malloc(sizeof(JosephuNode)); for (i = 1; i < n; ++i) { tail->index = i; tail->next = (JosephuNode *)malloc(sizeof(JosephuNode)); tail = tail->next; } tail->index = i; tail->next = head; for (i = 1; tail != head; ++i) { for (j = 1; j < m; ++j) { tail = head; head = head->next; } tail->next = head->next; printf("第%4d個出局的人是：%4d號\n", i, head->index); free(head); head = tail->next; } i = head->index; free(head); return i; } int main( ) { int n, m; scanf("%d%d", &n, &m); printf("最后勝利的是%d號！\n", Josephu(n, m)); //system("pause"); return 0; } ~~~