约瑟夫环问题求解
【问题描述】
编号为 1,2… n 的 n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一
开始任选一个正整数作为报数的上限值 m,从第一个人开始按顺时针方向自 1 开始顺序报
数,报到 m 时停止报数,报 m 的人出列,将他的密码作为新的 m 值,从他的顺时针方向上
的下一个开始重新从 1 报数,如此下去,直至所有人全部出列为止,设计一个程序求出出
列顺序。
【基本要求】
(1)利用单循环链表作为存储结构模拟此过程;
(2)键盘输入总人数、初始报数上限值 m 及各人密码;
(3)按照出列顺序输出各人的编号。
typedef struct node
{int num;
struct node *next;
} linklist;
linklist *creat(int n)
{linklist *s,*p,*head;
int i;
s=(linklist*)malloc(sizeof(linklist));
head=s;
s->num=1;
p=s;
for(i=2;i<=n;i++)
{s=(linklist*)malloc(sizeof(linklist));
s->num=i;
p->next=s;
p=s;
}
p->next=head;
return (head);
}
void slect(linklist *head,int m,int n)
{linklist *p,*q;
int i,t,k=1;
p=head;
t=1;