约瑟夫环问题的一种描述是:
编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。
一开始任选一个整数作为报上限制m,从第一个人开始顺时针自1开始顺序报数,报到m时停止报数。
报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,
如此下去,直至所有的人全部出列为止。试设计一个程序,求出列顺序。
#include<stdio.h>
#include<stdlib.h>
void CreatList(int n);//创建函数
void DeleteList(int m,int n);//出列函数
typedef struct NodeType{
int id;//每个人的序号
int password;//每个人的密码
struct NodeType *next;
}Nodetype;
NodeType *pHead = NULL;
int main(){
int m,n;//m为初始密码,n为人数
scanf("%d%d",&m,&n);
CreatList(n);
DeleteList(m,n);
return 0;
}
//创建函数
void CreatList(int n){
NodeType *pNew,*pEnd;
pEnd = (NodeType *)malloc(sizeof(NodeType));
for(int i=1;i<n+1;i++){
pNew = (NodeType *)malloc(sizeof(NodeType));
pNew->id = i;
int password;
printf("\n请输入第%d个人的密码:",i);
scanf("%d",&password);
pNew->password=password;
if(i==1) pHead = pNew;
else pEnd->next = pNew;
pNew->next = pHead;
pEnd = pNew;
}
}
//出列函数
void DeleteList(int m,int n){
int i=0;
NodeType *p=pHead;
NodeType *q=p;
while(n--){
if(m==1){
while(q->next!=p) q=q->next;
pHead = p->next;//
}
else{
while(--m){
q=p;
p=p->next;
}
}
printf("\n第%d个出列的数为:%d\n",++i,p->id);
m=p->password;
q->next = p->next;
free(p);
p=q->next;
q=p;
}
}