総当たり戦の日程作成
Posted feedbacks - C++
半日ほど、全部の組み合わせを求めてフィルタする方法を考えてたんですが、ギブアップして参考URLの考え方を見ました。シンプルなアルゴリズムに感動。
簡単なテストケースをつけました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #include <string>
#include <sstream>
#include <vector>
#include <iostream>
using namespace std;
typedef vector <string> VS;
VS kirkman(int n) {
VS result;
int ring[n-1], vertex[n-1];
for (int i(0); i<n-1; i++)
ring[i] = i+2;
for (int i(0); i<n-1; i++) {
// rotate ring
for (int j(0); j<n-1; j++)
vertex[j] = ring[(j+i) % (n-1)];
stringstream ss("");
// 1 is special case
ss << "1-" << vertex[0] << ' ';
for (int j(0); j<n/2-1; j++)
ss << vertex[j+1] << '-' << vertex[n-2-j] << ' ';
string s(ss.str());
result.push_back(string(s, 0, s.size()-1)); // chop tail ','
}
return result;
}
void test(string expected[], int n) {
VS vs(expected, expected+n-1);
VS result(kirkman(n));
if (vs != result) {
cerr << "failed:" << endl;
cerr << " expected: ";
for (VS::iterator i(vs.begin()); i!=vs.end(); i++) {
cerr << *i << ", ";
} cerr << endl;
cerr << " actual: ";
for (VS::iterator i(result.begin()); i!=result.end(); i++) {
cerr << *i << ", ";
} cerr << endl;
}
}
void test_0() {
string ss[] = {"1-2 3-4", "1-3 4-2", "1-4 2-3"};
test(ss, 4);
}
void test_1() {
string ss[] = {
"1-2 3-6 4-5", "1-3 4-2 5-6", "1-4 5-3 6-2",
"1-5 6-4 2-3", "1-6 2-5 3-4"};
test(ss, 6);
}
int main(int argc, char **argv) {
test_0();
test_1();
return 0;
}
|
ryugate
#5661()
Rating2/2=1.00
see: カークマンの組分け
[ reply ]