约瑟夫环问题（C语言数组和循环链表） |
您所在的位置：网站首页 › 约瑟夫环数原理 › 约瑟夫环问题（C语言数组和循环链表） |
|
本文将用两种方式（数组和循环链表）求解约瑟夫环问题，为了更好理解，本文将从洛谷的P1996 约瑟夫问题出发。 题目描述n个人围成一圈，从第一个人开始报数,数到 m的人出列，再由下一个人重新从1开始报数，数到 m的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。 输入格式输入两个整数 n,m。 输出格式输出一行 n个整数，按顺序输出每个出圈人的编号。 输入输出样例输入 10 3输出 3 6 9 2 7 1 8 5 10 4 说明/提示1≤m,n≤100 方法一（数组）： 解题思路：创建一个大小为n的数组用来表示n个人，同时用给数组元素赋值0或1表示该人的生死状态（0为生，1为死），同时设置一个flag用来表示当前淘汰的人数，当淘汰人数为n-1个人就跳出循环。 代码实现： #include int main() { int n, q, i = 0, count = 1, flag = 0; printf("人数："); scanf("%d", &n);//输入人数 getchar(); printf("报到哪个数被杀死："); scanf("%d", &q);//输入报到哪个数死 int a[n]; for (i = 0; i < n; i++) {//给每个人设置“生”的状态 a[i] = 0; } i = 0; printf("杀死顺序(下标)："); while (1) { if (flag == n - 1) break;//当只剩下一个人时，跳出循环 if (a[i] == 1) i++;//如果该人为死亡的状态，则跳过该人 else { if (count == q) {//满足被杀死的条件 a[i] = 1;//设置死亡状态 flag++;//死亡人数加一 printf("%d ", i);//输出这一次死亡的人的编号 count = 1;//重置报数 i++;//移动到下一个人开始 } else {//不满足被杀死的状态 count++;//继续报数 i++; } } if (i == n) i = 0;//由于数组下标从0开始，所以当i=n时，应该是移动到第一个人了 } printf("\n存活（下标）："); for (i = 0;; i++) { if (a[i] != 1) {//输出最后存活的人 printf("%d", i); break; } } return 0; }该方法一般为约瑟夫环问题的常见方法，但时间复杂度较高，而下面的方法可以帮助我们更好的理解循环链表的结构。 方法二（循环链表）： 解题思路： 创建一个循环链表，这样可以看成一群人围成一圈的状态，并在头结点开始给人从1开始赋值表示编号，另外创建一个大小为n的数组用来储存死亡顺序（编号），每当有人死亡时，就把该人的编号储存到数组中，同时把该人从链表中删去。还需设计一个flag来表示死亡人数，当死亡人数为n-1人时就跳出循环。 代码实现： 创建循环链表函数Creat: LINK* Creat(int n) {//该函数用来创建一个循环链表并返回该链表的尾结点 LINK *head = NULL,*p = NULL, *pr = NULL;//head用来表示头节点，p用来申请内存空间，pr用来表示当前链表的尾结点 int i; for(i = 1;i id = i; if(head == NULL)//如果头节点为空指针，则把p赋给head { head = p; } else {//否则就用尾插法创建链表 pr->next = p; } pr = p;//将pr赋值为指向当前链表最后一个结点 } pr->next = head;//将最后一个节点的next指向head以构成循环链表 return pr;//返回尾结点 }用于确定出圈顺序的函数YueSeFu： void YueSeFu(LINK* tail, int n, int m, int* a) { int count = 0, flag = 0;//设置报数值和死亡人数值 LINK* p = tail->next, *q = tail;//定义p为头指针，q为p前一个结点的指针 while (flag < n - 1) {//死亡人数没有达到n-1 count++;//报数 if (count == m) {//满足出圈条件 *a = p->id;//记录当前出圈者的编号 a++;//让数组移向下一个值 q->next = p->next;//让p的上一个结点的指针指向p的下一个结点 free(p);//释放当前结点 p = q->next;//p移动到下一个人 count = 0;//重新开始报数 flag++;//死亡人数加一 } else {//不满足就移向下一个人 q = p; p = p->next; } } *a = p->id;//记录最后一个人的编号 free(p); }完整代码： #include #include typedef struct link { int id; struct link* next; } LINK; LINK* Creat(int n); void YueSeFu(LINK* head, int n, int m, int* a); void DisplyLINK (LINK *head); int main(void) { int n, m;//n为总人数，m为出圈时报的数 scanf("%d%d", &n, &m); int a[n]; LINK* tail = NULL;//定义尾指针 tail = Creat(n);//创建一个循环链表并得到尾指针 YueSeFu(tail, n, m, a); for (int i = 0; i < n; i++) {//打印出圈顺序（编号） printf("%d ", a[i]); } } LINK* Creat(int n) { LINK *head = NULL,*p = NULL, *pr = NULL; int i; for(i = 1;i id = i; if(head == NULL) { head = p; } else { pr->next = p; } pr = p; } p->next = head; return pr; } void YueSeFu(LINK* tail, int n, int m, int* a) { int count = 0, sum = 0; LINK* p = tail->next, *q = tail; while (sum < n - 1) { count++; if (count == m) { q->next = p->next; *a = p->id; free(p); p = q->next; count = 0; sum++; a++; } else { q=p; p=p->next; } } *a = p->id; free(p); } |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |