871
京东网上商城
九度题目1188：约瑟夫环
题目1188：约瑟夫环
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：1500
解决：665
题目描述：
N个人围成一圈顺序编号，从1号开始按1、2、3......顺序报数，报p者退出圈外，其余的
人再从1、2、3开始报数，报p的人再退出圈外，以此类推。
请按退出顺序输出每个退出人的原序号。
输入：
包括一个整数N(1<=N<=3000)及一个整数p。
输出：
测试数据可能有多组，对于每一组数据，
按退出顺序输出每个退出人的原序号。
样例输入：
7 3
样例输出：
3 6 2 7 5 1 4
来源：
2003-2005年华中科技大学计算机研究生机试真题
链表环模拟
AC代码：
#include<stdio.h>
struct Node
{
int data;
bool out;
Node *next;
};
int main()
{
int i,j,n,m,count;
while(scanf("%d %d",&n,&m)!=EOF)
{
Node *Head=new Node();
Head->data=1;
Head->out=false;
Node *temp=Head;
for(i=2;i<=n;i++)
{
Node *node=new Node();
node->data=i;
node->out=false;
temp->next=node;
temp=node;
}
temp->next=Head;//组成了一个链表环
Node *p=Head;
count=0;
while(p&&n>0)
{
if(p->out==false)
{
count++;
if(count==m)
{
if(n>1)
printf("%d ",p->data);
else
printf("%d\n",p->data);
p->out=true;
count=0;
n--;
}
}
p=p->next;
}
}
return 0;
}
最后更新：2017-04-03 05:39:36