出对序列
有N个人按照顺时针围成一圈,编号1到N。他们从1开始按顺时针报数,每报到M的人出列,并从下一个开始报数,报到M的人再出列,直到全部出列,请问你能给出这N个人的出队顺序吗?
输入格式
输入只有一行,包括两个整数N,M(2<=N,M<=1000)
输出格式
输出一行N个数,代表出队序列,每两个数之间用一个空格隔开。
样例输入
7 3
样例输出
3 6 2 7 5 1 4
#include<stdio.h>
#include<stdlib.h>
#define len sizeof(struct s)
struct s
{
int num;
struct s * next;
};
int main ()
{
int k,n,m,i,j,t;
struct s *p,*p1,*p2;
struct s *head,*head1,*last1,*last,*r;
scanf("%d %d",&n,&m);
for(i=0;i<n;i++)
{
t=1;
p1=(struct s*)malloc(len);
p2=p1;
p1->num=t;head=NULL;
while(t<n) //创建链表,每个节点的NUM为它的序号
{
if(t==1)
head=p1;
else
p2->next=p1;
p1=(struct s*)malloc(len);
t++;
p1->num=t;
}
p1->next=NULL;
last=p1;
p1=p2=head;
head1=NULL;
t=n;j=1;
while(t!=0)
{
if(t==n-1) //若只剩一个结点,直接放在新链表的表尾
{
p=head;
last1->next=p;
last=p;
p->next=NULL;
}
else
{
if(j==m) //若j等于m,则开始将此节点移除旧链表,插进新链表
{
p=p1; //先删
if(p1==last) //若在表尾,
{
p2->next=NULL;
last=p2;
p1=head;
}
else if(p1==head) //在表头
{
head=p1->next;
p1=p1->next;
p2=head;
}
else
{ //在表中
p2->next=p1->next;
p1=p1->next;
}
j=1;t--;p->next=NULL; //插入新表
if(head1==NULL)
{ //新表为空
head1=p;
last1=p;
}
else //插在表尾
{
last1->next=p;
last=p;
}
}
else //若j不等于m,
{
if(p1==last) //若轮到表尾,返回表头
{
p2=p1;
p1=head;
} //若在表中,正常往下轮
else
{
p2=p1;
p1=p1->next;
}
j++;
}
}
}
}
r=head1; // 输出新链表
while(r!=NULL)
{
printf("%d ",r->num);
r=r->next;
}
printf("\n");
return 0;
}