问题描述
【问题描述】
约瑟夫环问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀的顺序是：5，4，6，2，3，1。
【输入形式】
输入两个正整数N和M，N表示N个人，M表示报数到M；
【输出形式】
输出依次出列的序号。以空格作为分隔。
【样例输入1】
6 5
1 2 3 4 5 6
【样例输出1】
5 4 6 2 3 1
【样例输入2】
3 3
3 2 1
【样例输出2】
1 3 2
一、顺序表法
用顺序表方法来求解，关键一步是最后一个人报完数后如何回到第一个人继续报数
1.1 初始化并创建一个顺序表
typedef struct List{ int * data; //顺序表的每个元素 int len; //顺序表的有效长度 int size; //顺序表的大小 }List,*PList; PList Init_List(PList L){ L->data=(int * )malloc(SIZE*sizeof(int)); 初始化顺序表 L->len=0; //置表有效长度为0 L->size=SIZE; //表的大小为SIZE（自己定义的） return L; } void Creat_List(PList L,int n){ if(L->len==L->size){ //一定要先判断有效长度是否等于表的大小 L->data=(int * )realloc(L->data,(L->size+INCREAM)*sizeof(int)); L->size+=INCREAM; //如果表已经满了，要重新开辟空间 } int i; for(i=0;i<n;i++){ scanf("%d",&L->data[i]); L->len++; //每增加一个元素，表的有效长度加上了1 } }
1.2 用顺序表解约瑟夫环问题的具体算法
void Ysfh_List(PList L,int n,int m){ int i,j,k; k=n; //用k来保存剩余的人数 j=0; //用j来表示报数的大小 for(i=0;i<=n;i++){ if(i==n) i=0; //一定要先判断是否都报完数了，都报完了就返回第一个人继续报 if(L->data[i]!=0) j++; //如果不是0，那么继续报数 if(j==m){ //报数为m的人被杀掉 printf("%d ",L->data[i]); //打印被杀掉的人 L->data[i]=0; //给被杀掉的人赋值0，方便其他人报数 j=0; //每杀掉一个人，重新开始报数 k--; //每杀掉一个人，总人数减少1 } if(k==0) break; //当所有人都被杀掉了以后，退出循环 } }
1.3 代码实现
1.3.1 完整代码
#include<stdio.h> #include<malloc.h> #define SIZE 10 #define INCREAM 10 typedef struct List{ int * data; int len; int size; }List,*PList; PList Init_List(PList L){ L->data=(int * )malloc(SIZE*sizeof(int)); L->len=0; L->size=SIZE; return L; } void Creat_List(PList L,int n){ if(L->len==L->size){ L->data=(int * )realloc(L->data,(L->size+INCREAM)*sizeof(int)); L->size+=INCREAM; } int i; for(i=0;i<n;i++){ scanf("%d",&L->data[i]); L->len++; } } void Ysfh_List(PList L,int n,int m){ int i,j,k; k=n; j=0; for(i=0;i<=n;i++){ if(i==n) i=0; if(L->data[i]!=0) j++; if(j==m){ printf("%d ",L->data[i]); L->data[i]=0; j=0; k--; } if(k==0) break; } } int main(){ int n,m; List L; Init_List(&L); scanf("%d %d",&n,&m); Creat_List(&L,n); Ysfh_List(&L,n,m); return 0; }
1.3.2 运行结果
二、循环单链表法
2.1 带头结点的循环单链表
2.1.1 初始化并创建一个带头结点的循环单链表
在初始化并创建一个带头结点的循环单链表时，我们一定要注意，尾结点的指针域不能指向头结点，要让尾结点的指针域指向头结点后面的第一个有效结点。如果尾结点的指针域指向了头结点，那么这个循环单链表就是带着头结点一起循环了。
typedef struct Node{ int data; //数据域 struct Node * next; //指针域 }Node,*PNode; PNode Init_Node(){ PNode head=(PNode)malloc(sizeof(Node)); //初始化带头结点的单链表 head->next=NULL; //指针域指向空 return head; } void Creat_Node(PNode head,int n){ PNode Last=head; int i; for(i=0;i<n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); scanf("%d",&Pnew->data); Pnew->next=NULL; Last->next=Pnew; //尾插法 Last=Pnew; } Last->next=head->next; //因为是循环单链表，所以尾指针指针域指向第一个有效结点 } //注意不是指向头结点，是第一个有效结点
2.1.2 用带头结点的循环单链表解决约瑟夫环问题
用循环单链表解决约瑟夫问题时，不用考虑最后一个人报完数后如何回到第一个人接着报数。
我们只需要找到每个将被杀掉的人的前面一个结点就好，注意要找的是被杀掉的人的前面一个人的结点，这样我们才能杀掉想要杀掉的人（跟删除过程类似），一定是找到被杀的人的前驱。
void Ysfh_Node(PNode head,int n,int m){ int i,j; PNode p=head; for(i=0;i<n;i++){ //第一重循环，每循环一次杀掉一个人 for(j=1;j<m;j++){ //第二重循环，用来找到被杀的人前面的那个人 p=p->next; } PNode q=p->next; //q是被杀的人 printf("%d ",q->data); //打印q p->next=q->next; //杀掉q free(q); //释放q } }
2.1.3 完整代码
#include<stdio.h> #include<malloc.h> typedef struct Node{ int data; struct Node * next; }Node,*PNode; PNode Init_Node(){ PNode head=(PNode)malloc(sizeof(Node)); head->next=NULL; return head; } void Creat_Node(PNode head,int n){ PNode Last=head; int i; for(i=0;i<n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); scanf("%d",&Pnew->data); Pnew->next=NULL; Last->next=Pnew; Last=Pnew; } Last->next=head->next; } void Ysfh_Node(PNode head,int n,int m){ int i,j; PNode p=head; for(i=0;i<n;i++){ for(j=1;j<m;j++){ p=p->next; } PNode q=p->next; printf("%d ",q->data); p->next=q->next; free(q); } } int main(){ int n,m; PNode p; p=Init_Node(); scanf("%d %d",&n,&m); Creat_Node(p,n); Ysfh_Node(p,n,m); return 0; }
2.2 不带头结点的循环单链表
2.2.1 初始化并创建一个不带头结点的循环单链表
初始化并创建一个不带头结点的循环单链表，我们只需要将一个普通单链表的尾结点的指针域指向头结点就好了。（其他都和初始化并创建一个不带头结点的单链表一样）
typedef struct Node{ int data; //数据域 struct Node * next; //指针域 }Node,*PNode; PNode Init_Node(){ PNode head; //初始化不带头结点的链表 head=NULL; return head; } void Creat_Node(PNode *head,int n){ int i; PNode Last; Last->next=NULL; for(i=0;i<n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); scanf("%d",&Pnew->data); Pnew->next=NULL; if(*head==NULL){ //先判断头指针是否指向空 *head=Pnew; Last=Pnew; }else{ Last->next=Pnew; //尾插法 Last=Pnew; } } Last->next=*head; //循环单链表，尾指针指针域指向头结点 }
2.2.2 用不带头结点的循环单链表解决约瑟夫环问题
用不带头结点的循环单链表解决约瑟夫环问题时，我们要注意你要找第一个被杀的人的循环次数和找其他被杀掉的人的循环次数不同。假设你第一次要杀掉的是第5个人，那么你应该找到第4个人的结点，由于每报完一个数，p都指向了下一个结点，说明要找第4个人的结点，此时应该报数为3。将第5个人杀掉后，此时p指针指向的依然是第4个结点，第4个结点后面接上了原来的第6个结点（现在成为了第5个结点），然后要执行第二次杀人，此时重新开始了报数，这个时候第5个结点的人报数1，p同时指向了第5个结点，说明此时要找到被杀掉的人的情况和带头结点是相似的，假设要杀第5个人，只需要找第4个人的结点，由于报数为4的同时p会指向这个结点，所以相比之下要多循环一次。
void Ysfh_Node(PNode head,int n,int m){ PNode p=head,q; int i,j; for(i=0;i<n;i++){ if(i==0){ //不带头结点，我们要多一次判断 for(j=1;j<m-1;j++){ //要找到第一个被杀的人时，循环的次数会少一次 p=p->next; } }else{ for(j=1;j<m;j++){ //除了第一个被杀掉的人，找其他被杀的人循环次数不变 p=p->next; } } q=p->next; //杀人的方法和带头结点时是一样 printf("%d ",q->data); p->next=q->next; free(q); } }
2.2.3 完整代码
#include<stdio.h> #include<malloc.h> typedef struct Node{ int data; struct Node * next; }Node,*PNode; PNode Init_Node(){ PNode head; head=NULL; return head; } void Creat_Node(PNode *head,int n){ int i; PNode Last; Last->next=NULL; for(i=0;i<n;i++){ PNode Pnew=(PNode)malloc(sizeof(Node)); scanf("%d",&Pnew->data); Pnew->next=NULL; if(*head==NULL){ *head=Pnew; Last=Pnew; }else{ Last->next=Pnew; Last=Pnew; } } Last->next=*head; } void Ysfh_Node(PNode head,int n,int m){ PNode p=head,q; int i,j; for(i=0;i<n;i++){ if(i==0){ for(j=1;j<m-1;j++){ p=p->next; } }else{ for(j=1;j<m;j++){ p=p->next; } } q=p->next; printf("%d ",q->data); p->next=q->next; free(q); } } int main(){ PNode p; p=Init_Node(); int n,m; scanf("%d %d",&n,&m); Creat_Node(&p,n); Ysfh_Node(p,n,m); return 0; }
2.3 运行结果
三、总结
1.初始化并创建不带头结点的循环单链表时，要注意判断头指针是否指向空
2.初始化并创建带头结点的循环单链表时，要注意尾结点指针域指向头结点后面的第一个有效结点
3.用不带头结点的循环单链表解决约瑟夫环问题，注意杀掉第1个人的循环次数要相对杀掉其他人的循环次数减少1次
