九度题目1188:约瑟夫环

  1. 云栖社区>
  2. 博客>
  3. 正文

九度题目1188:约瑟夫环

光仔december 2014-07-28 21:25:00 浏览795
展开阅读全文

题目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;
}

网友评论

登录后评论
0/500
评论
光仔december
+ 关注