【基础】出圈

Description

设有n个人围坐一圈并按顺时针方向从1到n编号，从第1个人开始进行1到m的报数，报数到第个m人，此人出圈，再从他的下一个人重新开始1到m的报数，如此进行下去直到所剩下一人为止。

Input

输入多行，每行２个数，分别表示n和m.

Output

计算每一行中最后剩下这个人的编号．

Sample Input

10 3

Sample Output

Source

#include<iostream>
using namespace std;
struct child
{
 int num;
 struct child *next;
};
typedef    child Node;
typedef  Node *Link;
int n;
//  creat a link
Link creat(int s)
{
 n=0;
 int i=1;
 Link p1,p2,head;
 head=NULL;
 p1=p2=new Node;
 p1->num=i;
 while(1)
 {
  if(p1->num!=0)
  {
   i++;  
      n++;
   if(n==1)
    head=p1; 
   else
   {
    p2->next=p1;
    p2=p1;
   }
   p1=new Node;
   p1->num=i;
   if(i>s)
   {
    p2->next=NULL;
    break;
   }
  }
 }
 return head;
}

int main()
{
 int m,s;
while(cin>>s>>m)
{
 int i=1;
 Link head,p1,p2;
 head=creat(s);
 p1=p2=head;
 while(n!=1)
 {
  if(i%m==0)
  {
   if(p1->next==NULL)
    p2->next=head;
   else
    p2->next=p1->next;
   delete p1;
   n--;
   p1=p2->next;
   i++;
  }
  else
  {
   p2=p1;
   if(p1->next==NULL)
    p1=head;
   else
    p1=p1->next;
   i++;
  }
 }
 cout<<p1->num<<endl;
}
 return 0;

}