#include<stdio.h> //约瑟夫问题,共n个人,从x开始数数,数到y时去掉,要求最后剩下的一个人编号为1
typedef int elemtype;
typedef struct{
elemtype data;
struct Node *next;
}*Linklist,Node;
int f(Node *start,int n,int y,Linklist L) //递归算法
{
Node *s,*p;
elemtype e;
int i;
if (n==1&&start->data==1) return 1; //若最后剩下1,则返回1
if (n==1) {printf("%d\n",start->data);return 0;} //其他则输出最后的编号,并返回0
for (i=1,p=start;i<y-1;i++) // 删除数到y的
{
p=p->next;
}
s=p->next;
e=s->data;
p->next=s->next;
free(s);
printf("%d\t",e); //输出删除的编号
start=p->next;
f(start,n-1,y,L);
}
void TraverseList(Linklist L)
{
Node *p=L;
while(p->data!=5)
{
printf("%d\t",p->data);
p=p->next;
}
printf("\n");
}
int main()
{
Linklist L;
L=(Linklist)malloc(sizeof(Node));
Node *start,*p,*s;
int y,n,x,i,c;
printf("请输入总人数:\n");
scanf("%d",&n);
L->data=1; //编号
L->next=NULL;
p=L;
for (i=2;i<=n;i++)
{
s=(Node*)malloc(sizeof(Node));
s->data=i;
s->next=p->next;
p->next=s;
p=p->next;
}
p->next=L; //围圈
TraverseList(L);
for (x=1;x<2;x++) //先固定x只能为1
{
for (i=1,p=L;i<x;i++) p=p->next;
start=p;
for(y=2;y<n;y++) //y可从2~n-1变化
{
if (f(start,n,y,L)==1) printf("x:%d\t y:%d\n",x,y); //如果返回值为1,说明最后剩下了1,输出x,y的值
Linklist L; //由于前面删除了链表,所以重新建立单循环链表
L=(Linklist)malloc(sizeof(Node));
L->data=1;
L->next=NULL;
p=L;
for (i=2;i<=n;i++)
{
s=(Node*)malloc(sizeof(Node));
s->data=i;
s->next=p->next;
p->next=s;
p=p->next;
}
p->next=L;
TraverseList(L);
}
}
getch();
return 0;
}