问题描述
N个小孩围成一圈,从第M个开始循环报数(从1开始报),每报到R时这个人出列,然后接着从下一个人开始报数,同样报到R的人出列,直到所有的小孩都出列。编写程序输出出列的顺序。
基本思路
使用循环列表
#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(BOY)
typedef struct node
{
int no;
struct node *next;
}BOY;
void print(BOY *head)
{
BOY *p=head->next;
printf("%d ",p->no);
p=p->next;
while(p!=head->next)
{
printf("%d ",p->no);
p=p->next;
}
putchar('\n');
}//print
void creatLoopLink(int n,BOY *head)
{
BOY *p=head,*q;
q=(BOY*)malloc(LEN);
q->no=n;
if(head->next==NULL)
{
head->next=q;
q->next=q;
}
else
{
p=head->next;
while(p->next!=head->next) p=p->next;
q->next=p->next;
p->next=q;
}
}//creatLoopLink
void findBoy(BOY *head,int m,int r)
{
BOY *p=head->next,*t=head->next;
int i;
for(i=1;i<m;i++) //p指向第一个报数者
p=p->next;
while(p!=p->next)
{
for(i=1;i<r;i++) //循环报数
{
p=p->next;
}
while(t->next!=p) t=t->next; //找到报数者的前一个
printf("%d ",p->no);//打印报数者编号
t->next=p->next;//删除报数者
free(p);
p=t->next;//指向下一个开始报数者
}
printf("%d\n",p->no);
}//findBoy
int main()
{
int n,m,r,i;
BOY *head;
head=(BOY*)malloc(LEN);
head->no=-1;
head->next=NULL;
scanf("%d%d%d",&n,&m,&r);
for(i=1;i<=n;i++)
{
creatLoopLink(i,head);
}
print(head);
findBoy(head,m,r);
return 0;
}//main