问题描述：
设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m个的人出列，然后从出列的下一个人重新开始报数，数到第m个的人又出列，.......，如此反复直到所有的人出列为止。
Josephus.c
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList; void CreateList(LinkList *l,int n)
{
int i;
LinkList p,tail;
for(i = ;i <= n;i++)
{
p = (LinkList)malloc(sizeof(LNode));
p->data = i; if(i == )
{
*l = p;
tail = *l;
}
else
{
tail->next = p;
}
tail = p;
}
tail->next = *l;
} void PrintList(LinkList l)
{
LinkList p;
p=l;
printf("初始化：");
while(p->next != l)
{
printf("%d ",p->data);
p = p->next;
}
printf("%d\n",p->data);
} void DelElem(LinkList l)
{
LinkList p;
p = l->next;
l->next = p->next;
printf("%d",p->data);
free(p);
} LinkList LocatePos(LinkList l,int m)
{
LinkList p = l;
int i;
for(i = ;i < m;i++)
{
p = p->next;
}
return p;
} void Josephus(LinkList l,int n,int s,int m)
{
LinkList p,q;
p = LocatePos(l,s);
while(p->next != p)
{
if(m == )
{
q = LocatePos(p,n--);
}
else
{
q =LocatePos(p,m-);
}
DelElem(q);
p = q->next;
}
printf("%d",p->data);
}
int main()
{
int n,s,m;
LinkList l;
printf("总人数：");
scanf("%d",&n);
CreateList(&l,n);
PrintList(l);
printf("第几个人开始报数：");
scanf("%d",&s);
printf("数到第几个人出列：");
scanf("%d",&m);
Josephus(l,n,s,m);
return ;
}
Josephus.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList; LinkList CreateList(LinkList &l,int n)
{
LinkList tail,p;
int i;
for(i = ;i <= n;i++)
{
p = (LinkList)malloc(sizeof(LNode));
p->data = i;
if(i == )
{
l = p;
tail = l;
}
else
{
tail->next = p;
}
tail = p;
}
tail->next = l;
} void PrintList(LinkList l)
{
LinkList p = l;
while(p->next != l)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<p->data<<endl;
} void DelElem(LinkList p)
{ LinkList q;
q = p->next;
p->next = q->next;
cout<<q->data<<" ";
free(q);
} LinkList LocatePos(LinkList l,int k)
{
int i;
LinkList p = l;
for(i = ;i < k;i++)
{
p = p->next;
}
return p;
} void Josephus(LinkList l,int n,int s,int m)
{
LinkList p,q;
p = LocatePos(l,s);
cout<<"输出顺序：";
while(p != p->next)
{
if(m == )
q = LocatePos(p,n--);
else
q = LocatePos(p,m-);
DelElem(q);
p = q->next; }
cout<<p->data<<endl;
free(p);
}
int main()
{
LinkList l;
int n,s,m;
cout<<"总人数：";
cin>>n;
CreateList(l,n);
cout<<"初始化：";
PrintList(l);
cout<<"第几个人开始报数：";
cin>>s;
cout<<"数到第几个人出列：";
cin>>m;
Josephus(l,n,s,m);
return ;
}