ytu 1067: 顺序排号（约瑟夫环）

1067: 顺序排号

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 31  Solved: 16
[Submit][Status][Web Board]

Description

有n人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来的第几号的那位。

Input

初始人数n

Output

最后一人的初始编号

Sample Input

3

Sample Output

2

HINT

 

Source

freeproblemset

---

 

　　水题，约瑟夫环。

　　最近快考试了，趁机刷刷水题，正好夯实一下基础。

　　思路：用链表做的，写的时候很容易出问题。

　　代码：

 #include <iostream>

 using namespace std;

 struct Node{

     int data;

     Node* next;

 };

 int main()

 {

     Node *head = new Node;

     Node *p = head;

     int i,n;

     cin>>n;

     for(i=;i<=n;i++){

         if(i==){

             p->data=i;

             p->next = NULL;

             continue;

         }

         //cout<<p<<endl;

         Node *t = new Node;

         t->data = i;

         t->next = NULL;

         p->next = t;

         p = p->next;

     }

     p->next = head;

     p = head;

     /* 输出测试

     int t = head.data;

     do{

         cout<<p->data<<' ';

         p = p->next;

     }while(p->data!=t);

     cout<<endl;

     */

     //模拟报数

     int num = ;

     while(){

         if(num==){

             if(p->next->next==p)

                 break;

             else{

                 Node * t = new Node;

                 t = p->next;

                 p->next = t->next;

                 //cout<<t->data<<endl;

                 delete(t);

                 p = p->next;

                 num=;

             }

         }

         else{

             p = p->next;

             num++;

         }

     }

     cout<<p->data<<endl;

     return ;

 }

Freecode : www.cnblogs.com/yym2013