北理工LeXue乐学题目 可能有误,仅供参考,每周一/三早八,按时间排序了,暂不分类,从第四周开始
第四周 2024.09.10 约瑟夫问题
展开查看
约瑟夫问题是一个经典的问题(大一我们讲过)。这个问题可以用数组,也可以用链表。作为复习,大家可以试试你自己的算法。
已知n个人(不妨分别以编号1,2,3,…,n 代表 )围坐在一张圆桌周围,从编号为 k 的人开始,从1开始顺时针报数1, 2, 3, ...,顺时针数到m 的那个人,出列并输出。然后从出列的下一个人开始,从1开始继续顺时针报数,数到m的那个人,出列并输出,…依此重复下去,直到圆桌周围的人全部出列。
输入:n, k, m
输出:按照出列的顺序依次输出出列人的编号,编号中间相隔一个空格,每10个编号为一行。
非法输入的对应输出如下
a)
输入::n、k、m任一个小于1
输出:n,m,k must bigger than 0.
b)
输入:k>n
输出:k should not bigger than n.
例:
输入:9,3,2
输出:4 6 8 1 3 7 2 9 5
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node * next; } NODE;NODE* createNode (int data) { NODE* newNode = (NODE*)malloc (sizeof (NODE)); newNode->data = data; newNode->next = newNode; return newNode; }void insertNode (NODE** head, int data) { NODE* newNode = createNode (data); if (*head == NULL ) { *head = newNode; } else { NODE* temp = *head; while (temp->next != *head) { temp = temp->next; } temp->next = newNode; } newNode->next = *head; }void freeList (NODE* head) { if (head == NULL ) return ; NODE* current = head; NODE* nextNode; do { nextNode = current->next; free (current); current = nextNode; } while (current != head); }void baka (int k, NODE** head) { NODE* temp = *head; for (int i = 1 ; i < k; i++) { temp = temp->next; } *head = temp; }int cirno (int m, NODE** head) { int data; NODE* temp = *head; for (int i = 1 ; i < m - 1 ; i++) temp = temp->next; data = temp->next->data; *head = temp->next->next; temp->next = NULL ; temp->next = *head; return data; }int main () { NODE* head = NULL ; int n, k, m; scanf ("%d,%d,%d" , &n, &k, &m); if (n < 1 || m <1 || k <1 ) { printf ("n,m,k must bigger than 0.\n" ); return 0 ; } if (k > n) { printf ("k should not bigger than n.\n" ); return 0 ; } for (int i = 1 ; i <= n; i++) insertNode (&head, i); baka (k, &head); int count=0 ,j, x, past = 0 ; for (j = 0 ; ; j++) { if (j == 10 ) { putchar ('\n' ); j = 0 ; } x = cirno (m, &head); if (x == past) break ; else if (j == 0 ) ; else putchar (' ' ); printf ("%d" ,x ); count++; past = x; } if (count==0 ||count%10 !=0 ) putchar ('\n' ); freeList (head); return 0 ; }