约瑟夫环问题
约瑟夫问题的一种描述为：编号1,2,…,n的n 个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m, 从第一个人开始顺时针自1开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。
例如m 的初值为20；n=7，7个人的密码依次是：3,1,7,2,4,8,4, 出列顺序为6,1,4,7,2,3,5。
【解答】：
#include
#include
typedef struct Node
{
int password;
int num;
struct Node *next;
}Node,*Linklist;
void Josephus()
{
Linklist L;
Node *p,*r,*q;
int m,n,C,j;
L=(Node*)malloc(sizeof(Node));/*初始化单向循环链表*/
if(L==NULL){printf("\n链表申请不到空间!");return;}
L->next=NULL;
r=L;
printf("请输入人数n 的值(n>0):");
scanf("%d",&n);
for(j=1;j
{
p=(Node*)malloc(sizeof(Node));
if(p!=NULL)
{
printf("请输入第%d个人的密码:",j);
scanf("%d",&C);
p->password=C;
p->num=j;
r->next=p;
r=p;
}
}
r->next=L->next;
printf("请输入第一个报数上限值m(m>0):");
scanf("%d",&m);
printf("*****************************************\n");printf("出列的顺序为:\n");
q=L;
p=L->next;
while(n!=1)/*计算出列的顺序*/{
j=1;
while(j
q=p;/*q为当前结点p 的前驱结点*/p=p->next;
j++;
}
printf("%d->",p->num);
m=p->password;/*获得新密码*/n--;
q->next=p->next;/*p出列*/
r=p;
p=p->next;
free(r);
}
printf("%d\n",p->num);
}
int main()
{
Josephus();
return 0;
}
约瑟夫环问题
约瑟夫问题的一种描述为：编号1,2,…,n的n 个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m, 从第一个人开始顺时针自1开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。
例如m 的初值为20；n=7，7个人的密码依次是：3,1,7,2,4,8,4, 出列顺序为6,1,4,7,2,3,5。
【解答】：
#include
#include
typedef struct Node
{
int password;
int num;
struct Node *next;
}Node,*Linklist;
void Josephus()
{
Linklist L;
Node *p,*r,*q;
int m,n,C,j;
L=(Node*)malloc(sizeof(Node));/*初始化单向循环链表*/
if(L==NULL){printf("\n链表申请不到空间!");return;}
L->next=NULL;
r=L;
printf("请输入人数n 的值(n>0):");
scanf("%d",&n);
for(j=1;j
{
p=(Node*)malloc(sizeof(Node));
if(p!=NULL)
{
printf("请输入第%d个人的密码:",j);
scanf("%d",&C);
p->password=C;
p->num=j;
r->next=p;
r=p;
}
}
r->next=L->next;
printf("请输入第一个报数上限值m(m>0):");
scanf("%d",&m);
printf("*****************************************\n");printf("出列的顺序为:\n");
q=L;
p=L->next;
while(n!=1)/*计算出列的顺序*/{
j=1;
while(j
q=p;/*q为当前结点p 的前驱结点*/p=p->next;
j++;
}
printf("%d->",p->num);
m=p->password;/*获得新密码*/n--;
q->next=p->next;/*p出列*/
r=p;
p=p->next;
free(r);
}
printf("%d\n",p->num);
}
int main()
{
Josephus();
return 0;
}