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