Question

约瑟夫环问题 设计一个带头结点的循环单链表类，实现约瑟夫环问题； 问题描述：设编号为1,2,…，n(n>0)个

设计一个带头结点的循环单链表类，实现约瑟夫环问题；
问题描述：设编号为1,2,…，n(n>0)个人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。
测试数据：
n=7,7个人的密码依次为3,1,7,2,4,8,4
初始报数上限值m=20

Answer 1

#include<stdio.h>

struct node{
int data;
struct node *next;
}node,*list,*p,*r;

void JOSEPHU(int n,int k,int m)
{
int i,j;
list=NULL;
for(i=1;i<=n;i++)
{
p=(struct node*)malloc(sizeof(node));
p->data=i;
if(list==NULL)
list=p;
else
r->next=p;
r=p;
}
p->next=list; /*建立一个循环链表*/

p=list;
for(i=1;i<=n+1;i++)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n"); /*打印链表,并检查循环链表是不输入正确*/
p=list;
i=1;
while(p&&i<k)
{ r=p;
p=p->next;
++i;
}
for(i=1;i<n;i++)
{
for(j=1;j<m;j++)
{ r=p;
p=p->next;
}
printf("The out=%d\n",p->data);
r->next=p->next;
}
}
void main()
{
int x, y, z;
printf("input the lenth n\n");/*n,k,m分别代表总的人数，第一个报数的人，间隔的人数*/
scanf("%d",&x);
printf("input the start k\n");
scanf("%d",&y);
printf("input the m\n");
scanf("%d",&z);
JOSEPHU(x,y,z);
}