首页 > 代码库 > ytu 1067: 顺序排号（约瑟夫环）

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

2024-07-07 15:41:35   224人阅读

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

 
　　水题，约瑟夫环。
　　最近快考试了，趁机刷刷水题，正好夯实一下基础。
　　思路：用链表做的，写的时候很容易出问题。
　　代码：
 1 #include <iostream>
 2 
 3 using namespace std;
 4 struct Node{
 5     int data;
 6     Node* next;
 7 };
 8 int main()
 9 {
10     Node *head = new Node;
11     Node *p = head;
12     int i,n;
13     cin>>n;
14     for(i=1;i<=n;i++){
15         if(i==1){
16             p->data=http://www.mamicode.com/i;
17             p->next = NULL;
18             continue;
19         }
20         //cout<<p<<endl;
21         Node *t = new Node;
22         t->data =http://www.mamicode.com/ i;
23         t->next = NULL;
24         p->next = t;
25         p = p->next;
26     }
27     p->next = head;
28     p = head;
29     /* 输出测试
30     int t = head.data;
31     do{
32         cout<<p->data<<‘ ‘;
33         p = p->next;
34     }while(p->data!=t);
35     cout<<endl;
36     */
37     //模拟报数
38     int num = 1;
39     while(1){
40         if(num==2){
41             if(p->next->next==p)
42                 break;
43             else{
44                 Node * t = new Node;
45                 t = p->next;
46                 p->next = t->next;
47                 //cout<<t->data<<endl;
48                 delete(t);
49                 p = p->next;
50                 num=1;
51             }
52         }
53         else{
54             p = p->next;
55             num++;
56         }
57     }
58     cout<<p->data<<endl;
59     return 0;
60 }

 

Freecode : www.cnblogs.com/yym2013


联系
我们