双向约瑟夫环。
数据规模只有20,模拟掉了。(其实公式我还是不太会推,有空得看看)
值得注意的是两个方向找值不是找到一个去掉一个,而是找到后同时去掉。
还有输出也很坑爹!
在这里不得不抱怨下Uva的oj,少了个s,少了个空行什么的都不会显示pe,就给个wa,让人还以为算法有问题。原本以为Uva没有pe,然后据说这边的输出空行如果不对的话就会显示pe。。。
代码:
#include <cstdio>
#include <cstring>
const int maxn = 22; int N;
bool d[maxn]; int cw(int pos, int k) {
int cnt = 0;
for ( ; cnt != k; pos++) {
if (pos == N) pos = 0;
if (d[pos]) cnt++;
}
return --pos;
} int w(int pos, int m) {
int cnt = 0;
for (; cnt != m; pos--) {
if (pos == -1) pos = N - 1;
if (d[pos]) cnt++;
}
return ++pos;
}
int main() {
int k, m;
while (scanf("%d%d%d", &N, &k, &m) && N && k && m) {
memset(d, 1, N);
int tot = N, flag = 0, a = 0, b = N - 1;
while (tot) {
a = cw(a, k), b = w(b, m);
tot--;
if (flag) printf(",");
d[a] = d[b] = false;
flag = 1;
if (a == b)
printf("%3d", a + 1);
else {
printf("%3d%3d", a + 1, b + 1);
tot--;
}
}//while find out all
printf("\n");
}//while
return 0;
}