poj3750-小孩报数问题(约瑟夫环)

一，题意：
　　中文题。
二，思路：
　　1，输入。
　　2，无限循环1~n~1~n，直到输出n次，再跳出。
　　3，输出名字，并标记。

普通模拟版：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int main() {
 5     char name[56][16];
 6     int n, w, s;
 7     cin >> n;
 8     for (int i = 1; i <= n; i++) {
 9         cin >> name[i];
10     }
11     scanf("%d,%d", &w, &s);
12     int count = 0;                            //记录经过未标记的名字几次
13     int k = 0;                                //记录输出的次数
14     for (int i = w; k!=n ; i++) {            //输出 n 次，跳出
15         if (i > n) i = i % n;                //循环 1~n~1~n
16         if (strcmp(name[i], "1")) count++;    //经过未标记的名字时 count++
17         if (count == s) {                    //经过s次未被标记的名字时
18             cout << name[i] << endl;
19             k++;                            //输出一次 k++
20             count = 0;                        //输出以后count重新记数
21             w = i;                            //输出之后，w 重新从 i 开始
22             strcpy(name[i], "1");            //已经输出的名字标记为 1 
23         }
24     }
25     return 0;
26 }

View Code

线性表模拟版：

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 
 5 class SeqList {
 6 public:
 7     SeqList(string str[], int n);            //构造函数，创建长度为n 的线性表
 8     string Delete(int i);                    //输出并删除结点
 9     int getLength() { return length; }        //获取长度
10 private:
11     int length;
12     string name[65];
13 };
14 
15 SeqList::SeqList(string str[], int n) {        //实现构造函数
16     for (int i = 0; i < n; i++) {
17         name[i] = str[i];
18     }
19     length = n;
20 }
21 
22 string SeqList::Delete(int i) {
23     string x = name[i - 1];                    //定义一个x接收被删除的字符串
24     for (int j = i; j < length; j++) {        //从被删除的结点开始，后面的向前移动，覆盖被删除的结点
25         name[j - 1] = name[j];                        
26     }
27     length--;                                //删除一个结点，长度减 1
28     return x;
29 }
30 
31 int main() {
32     string str[65];
33     int n, w, s;
34     cin >> n;
35     for (int i = 0; i < n; i++) {
36         cin >> str[i];
37     }
38     scanf("%d,%d", &w, &s);
39     SeqList S(str, n);
40     while(n--) {
41         int ans = (w + s - 1);                 //ans 表示要输出的名字的序号
42         if ( ans==S.getLength() ) {
43             w = ans;
44             cout << S.Delete(w) << endl;
45         }
46         else {
47             if (ans % S.getLength() != 0) {
48                 w = ans % S.getLength();
49                 cout << S.Delete(w) << endl;
50             }
51             else {
52                 cout << S.Delete(w--) << endl;
53             }
54             
55         }
56 
57     }
58     return 0;
59 }

View Code