-
C语言解决约瑟夫环问题
题目
解答
-
法一：单循环链表
#include#include //定义单循环链表数据结构 typedef struct CNode{ int data; struct CNode *next; }CNode; typedef CNode *CLinkList; //初始化一个指向头节点的指针，使头指针->next=头指针，头指针->data不做处理 void InitList_L(CLinkList *L){ (*L) = (CLinkList)malloc(sizeof(CNode)); if(!(*L)) exit(-2); (*L)->next = *L; } //头插法建立单循环链表 int CreateList_HL(CLinkList *L,int s[],int n){ //二级指针 int i; CLinkList p; *L = (CLinkList)malloc(sizeof(CNode)); if(!(*L)) exit(-2); (*L)->next = *L; //只有一个头节点head，就让next指向自己 for(i=0; i<n; i++){ p = (CLinkList)malloc(sizeof(CNode)); if(!p) exit(-2); p->data = s[i]; //录入数据 p->next = (*L)->next; //将头指针所指向的下一个结点的地址，赋给新创建结点的next (*L)->next = p; //将新创建的结点的地址赋给头指针的下一个结点 } return 1; } //尾插法建立单循环链表 int CreateList_TL(CLinkList *L,int s[],int n){ int i; CLinkList p, q; *L = (CLinkList)malloc(sizeof(CNode)); if(!(*L)) exit(-2); (*L)->next = *L; //只有一个头节点head，就让next指向自己 for(i=0,q=*L; i<n; i++){ p = (CLinkList)malloc(sizeof(CNode)); if(!p) exit(-2); p->data = s[i]; //录入数据 q->next = p; q = q->next; } q->next = *L; //最后一个结点指向head return 1; } //求单循环链表的长度 int ListLength(CLinkList L){ CLinkList p; int count; if(L){ count = 0; p = L; //p指向头结点 while(p->next!=L){ //p没到表头 count++; p = p->next; } } return count; } //得到指向单循环链表第i个元素的指针 CLinkList GetElemPtr(CLinkList L, int i){ int count; CLinkList p; if(L&&i>0){ count = 1; p = L->next; while(p!=L && count<i){ count++; p = p->next; } if(p!=L) //L为头指针 return p; } return NULL; } //单循环链表第i个位置插入元素e int ListInsert(CLinkList L, int i, int e){ CLinkList p, s; int j; if(i<1 || i>ListLength(L)+1) //插入位置不合理 return 0; p = L; j = 0; while(j<i-1){ //寻找第i-1个结点 p = p->next; ++j; } s = (CLinkList)malloc(sizeof(CNode)); if(!s) exit(-2); s->data = e; s->next = p->next; p->next = s; return 1; } //单循环链表第i个位置删除元素e int ListDelete(CLinkList L, int i, int *e){ CLinkList pre, p; int j; if(i<1 || i>ListLength(L)) //删除位置不合理 return 0; pre = L; j = 1; while(pre->next && j<i){ //寻找第i个结点，并令pre指向其前驱 pre = pre->next; ++j; } p = pre->next; pre->next = p->next; *e = p->data; free(p); p=NULL; return 1; } //遍历单循环链表 void ListTraverse(CLinkList L){ CLinkList p; p = L->next; //p指向头结点，正向访问链表 while(p!=L){ printf("%d ",p->data); p = p->next; } printf("\n"); } //判断单循环链表是否为空 int ListEmpty(CLinkList L){ if(L!=NULL && L->next==L) //单循环链表存在并且只有头结点 return 1; else return 0; } /* 用单循环链表解决约瑟夫环问题(带头结点) 这里的单循环链表使用了带头结点的，方便找到表头的位置，但是由于头结点不存储元素，因此需要跳过头结点 链表插入删除都比较方便，不需要移动大量元素，只需要移动指针即可，适合这一类问题 */ void Algo(CLinkList L,int k,int m){ //从编号为k的人开始数，数到m的那个人出队列 int count,i,j; //count表示每次从1开始数，i用来找编号为k的结点的前驱 CLinkList pre,p; pre=L; count=1,i=1,j=1; /*寻找第k个结点，并令pre指向其前驱*/ while(i<k){ if(pre->next==L) //跳过头结点 pre=pre->next->next; else pre = pre->next; ++i; } while(L->next!=L){ //如果单循环链表不为空 if(count==m){ /*下一个结点不是头结点，直接删除*/ if(pre->next!=L){ p=pre->next; printf("第%d次出环的元素是%d\n",j++,p->data); pre->next=p->next; free(p); p=NULL; count=1; } /*下一个结点是头结点，下下个结点不是头结点，跳过头结点，删除下下个结点（头结点不保存数据，因此不参与运算）*/ else if(pre->next->next!=L){ p=pre->next->next; printf("第%d次出环的元素是%d\n",j++,p->data); pre->next->next=p->next; free(p); p=NULL; count=1; } /*下一个结点是头结点，下下个结点也是头结点，说明单循环链表已经为空了,只剩下头结点，因此跳出循环*/ else break; } count++; //count代表要删除的结点数的数，始终在pre指向的结点之前 if(pre->next==L) //跳过头结点 pre=pre->next->next; //pre指向要删除结点的前一个结点 else pre = pre->next; //pre指向要删除结点的前一个结点 } } void main(){ CLinkList L; int n=5,s[5]={1,2,3,4,5}; //假设5个人围坐一圈 int k=3,m=2; //第一次从编号为k的人开始数，数到m的那个人出队列 CreateList_TL(&L,s,n); //头插法建立单循环链表 ListTraverse(L); //遍历原始队列 printf("假设第一次从编号为%d的人开始数，数到%d的那个人出环\n",k,m); Algo(L,k,m); //用单循环链表解决约瑟夫环问题(带头结点) } - 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
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
-
法二：循环数组
/* 用循环数组解决约瑟夫环问题 解决问题的难点有两个: 1、如何求下一个的人的位置：在循环数组中向后移动采用：(k+l)%n 2、此人出圈后对这个人的位置如何处理：先将出圈人的位置打印输出，然后将其位置元素设置为0，表示它已出圈，以后见到它就直接跳过去 */ void Algo2(int s[],int n,int k0,int m){ //开始一共有n个人，从第k0个人开始数，数到m的那个人出队列 int i,j,k=k0-1; //元素访问的下标为 k，初始时从第k0个人开始数 for(i=0;i<n;i++){ //总共循环n次，每循环一次，出队一个元素，k在循环中会不断的运动 j=1; //j表示数的数，初始为1 while(j<m){ //如果还没有数到m while(s[k]==0) //如果s[k]为0，证明它已经出圈了，则跳过它 k=(k+1)%n; j++; //数下一个数 k=(k+1)%n; //数组下标向后走一步 } while(s[k]==0) //如果数到m发现它出圈了，则跳过它，找到第一个没出圈的数 k=(k+1)%n; printf("第%d次出环的元素是%d\n",i+1,s[k]); //先将出圈人的位置打印输出 s[k]=0; //然后将其位置元素设置为0，表示它已经出圈 } } void main(){ int n=5,s[5]={1,2,3,4,5}; //假设5个人围坐一圈 int k=3,m=2; //第一次从编号为k的人开始数，数到m的那个人出队列 printf("假设第一次从编号为%d的人开始数，数到%d的那个人出环\n",k,m); Algo2(s,n,k,m); //用循环数组解决约瑟夫环问题 }- 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
-
法三：递归
/* 用递归解决约瑟夫环问题 n指的是总人数，m指的是每次最大报到的数值，i是第i次，该函数每次可以求出第i次扔海里的人的编号 */ int Algo3(int n,int m,int i){ if(i==1) return (n+m-1)%n; else return (Algo3(n-1,m,i-1)+m)%n; } void main(){ int n=5; //假设5个人围坐一圈 int m=2; //数到2的那个人出环 printf("假设第一次从编号为1的人开始数，数到%d的那个人出环\n",m); for(int i=1;i<=n;i++) printf("第%d次出环的元素是%d\n",i,Algo3(n,m,i)+1); //因为求出的结果是数组中的下标，最终的编号还要加1 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
-
法四：迭代
/* 用迭代解决约瑟夫环问题 递推公式： f(N,M)=(f(N−1,M)+M)%N f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号 f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号 */ int Algo4(int n,int m){ int i,p=0; for(i=2;i<=n;i++){ p=(p+m)%i; } return p+1; //因为求出的结果是数组中的下标，最终的编号还要加1 } void main(){ int n=5; //假设5个人围坐一圈 int m=2; //数到2的那个人出环 printf("假设第一次从编号为1的人开始数，最后出环的是：%d\n",Algo4(n,m)); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
-
-
相关阅读:
java计算机毕业设计ssm贫困区教育资源捐赠平台element vue前后端分离
系统部署常用操作_查看硬盘大小_查看内存情况_查看某个端口是否被占用_telnet_远程scp复制拉取---Linux运维工作笔记055
vSphere+、vSAN+来了！VMware 混合云聚焦：原生、快速迁移、混合负载
你对lambda表达式的使用方法以及底层原理了解吗？
三翼鸟三周年：三次升级，全面引领
ES6新增属性
js 封装一个异步任务函数
环形队列结构
linux批量修改多个文件的同一部分内容
【使用 BERT 的问答系统】第 6 章 ：BERT 模型应用：其他任务
- 原文地址：https://blog.csdn.net/qq_41829337/article/details/126238648
