Dzisiaj rozwiążemy następujące zadanie rekrutacyjne:
W turnieju szachowym gra n graczy. Turniej będzie trwał n-1 dni i w każdym dniu, każdy szachista będzie rozgrywał jedną partię. Każdy z zawodników powinien zagrać z każdym innym dokładnie raz. Napisz program, który stworzy rozpiskę rozgrywek.
Zaczniemy jak zawsze od pytań do rekrutera.
Kandydat: Czy możemy założyć, że n jest potęgą dwójki?
Rekruter: Nie
Algorytm działający dla potęg dwójki jest zbyt ładny, aby go tu nie opisać (i dużo łatwiejszy do wymyślenia podczas rekrutacji). Więc załóżmy, że odpowiedź rekrutera na zadane mu pytanie, brzmiała “Tak”.
Przyjmijmy, że n = 8. Możemy ustawić 4 graczy w pierwszej kolumnie i 4 graczy w kolumnie drugiej. Gracze, którzy znajdują się w tym samym wierszu, grają ze sobą. Następnego dnia dokonujemy rotacji drugiej kolumny (patrz tabelka poniżej). Powtarzamy to przez 4 dni:
| 1 – 5 2 – 6 3 – 7 4 – 8 | 1 – 6 2 – 7 3 – 8 4 – 5 | 1 – 7 2 – 8 3 – 5 4 – 6 | 1 – 8 2 – 5 3 – 6 4 – 7 |
Teraz wszyscy gracze z pierwszej kolumny grali z wszystkimi graczami z kolumny drugiej. Jedyne mecze jakie nam pozostają to mecze pomiędzy graczami z pierwszej kolumny i mecze pomiędzy graczami z drugiej kolumny. I tutaj pada magiczne słowo: rekurencja.
Możemy wywołać naszą procedurę rekurencyjnie, tak aby ułożyć osobno terminarz dla graczy z pierwszej kolumny i dla graczy z drugiej kolumny. Na końcu musimy te terminarze skleić w jedną tabelę.
void terminarz_rek(const vector<string>& zawodnicy, int l, int r,
vector<vector<pair<string, string>>> &terminarz, int index)
{
if (r - l > 1)
{
int h = (r - l) / 2; // połowa n
for (int i = 0; i < h; i++)
{
for (int j = 0; j < h; j++)
{
terminarz[index + i].push_back(make_pair(zawodnicy[l+j],
zawodnicy[l+h+(i+j)%h]));
}
}
terminarz_rek(zawodnicy, l, l+h, terminarz, index + h);
terminarz_rek(zawodnicy, l+h, r, terminarz, index + h);
}
}
vector<vector<pair<string, string>>> skonstruuj_terminarz(const vector<string>& zawodnicy)
{
vector<vector<pair<string, string>>> odpowiedz(zawodnicy.size() - 1);
terminarz_rek(zawodnicy, 0, zawodnicy.size(), odpowiedz, 0);
return odpowiedz;
}W rozwiązaniu przedstawionym powyżej: tworzymy terminarz mając dostępne nazwiska zawodników w postaci wektora napisów (vector<string>). Wynik przedstawiamy jako wektor rozgrywek opisanych dzień po dniu. W każdym dniu przedstawiamy który z graczy gra z którym w postaci wektora par napisów. Ostatecznie tworzymy vector<vector<pair<string, string>>>.
W funkcji rekurencyjnej: l oraz r oznaczają przedział zawodników którymi w tym momencie się zajmujemy. Natomiast index to numer dnia w którym obecnie jesteśmy, albo inaczej: numer indeksu tablicy wyjściowej (terminarz) do którego powinniśmy pisać.
Co jednak jeśli liczba zawodników nie jest potęgą dwójki? Wróćmy szybciutko do pytań do rekrutera:
Kandydat: Czy n może być nieparzyste? Co w takiej sytuacji?
Rekruter: Może. W takiej sytuacji w każdym dniu jeden zawodnik pauzuje, a turniej trwa nie n-1 a n dni.
Zacznijmy od przypadku nieparzystego. Możemy zauważyć, że każdego dnia musi pauzować inny z zawodników. Niech zatem w dniu i-tym pauzuje zawodnik z numerem i. Pozostałych zawodników dzielimy w następujący sposób. Zawodnika z numerem i – 1 łączymy z zawodnikiem z numerem i + 1, zawodnika z numerem i – 2 łączymy z zawodnikiem i + 2 i tak dalej. Oczywiście numery liczymy modulo n. Dlaczego taki algorytm ma działać poprawnie? Każdy z zawodników pauzuje tylko raz, a wszyscy pozostali danego dnia grają tylko jedną partię. Pozostaje udowodnić, że każdy gracz gra z każdym przeciwnikiem dokładnie raz. Aby to udowodnić, należy zauważyć, że każdego dnia grają ze sobą pary graczy, których suma numerów przystaje do siebie modulo n. Dla przykładu: niech n = 7 i niech pauzuje gracz z numerem 3. Wtedy grają ze sobą następujące pary: (2, 4), (1, 5) (7, 6). Sumy ich numerów to odpowiednio: 6, 6 i 13. Modulo 7 dają one: 6, 6 i 6. Ponadto każdego dnia suma modulo jest inna i jest równa podwojonemu numerowi gracza, który pauzuje modulo n. Wnioskujemy z tego, że każda para występuje w naszym terminarzu dokładnie raz.
Jeśli liczba jest parzysta to usuwamy ostatniego zawodnika i rozwiązujemy problem dla n – 1 graczy. Następnie osoby które miały pauzować, będą grały z graczem z numerem n.
vector<vector<pair<string, string>>> skonstruuj_terminarz(const vector<string>& zawodnicy)
{
int n;
if (zawodnicy.size() % 2 == 1) n = zawodnicy.size();
else n = zawodnicy.size() - 1;
vector<vector<pair<string, string>>> terminarz(n);
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= n / 2; j++)
terminarz[i].push_back(make_pair(zawodnicy[(i + j) % n],
zawodnicy[(i - j + n) % n]));
if (zawodnicy.size() % 2 == 0)
terminarz[i].push_back(make_pair(zawodnicy[i], zawodnicy[n]));
}
return terminarz;
}Algorytm ten nazywa się systemem kołowym i został wymyślony przez austriackiego szachistę Johanna Bergera. Dociekliwy Czytelnik zechce samodzielnie się zastanowić co należy zrobić, jeśli dodamy wymaganie, aby każdy z zawodników połowę meczy rozpoczynał kolorem białym a połowę kolorem czarnym.
