UniLecs #112. Совещание
UniLecsЗадача: начинается совещание за круглым столом. Собралось N человек. Как им одновременно пожать руки друг другу так, чтобы руки никаких людей не пересекались. Вам необходимо вычислить кол-во вариантов, ктр они могут это сделать. Порядок расположения за столом люди не меняют.
Входные данные: N - четное натуральное число от 2 до 100.
Вывод: кол-во способов, ктр они могут пожать друг другу руки.
Пример: N = 4
Answer = 2
Идея: эта задача - одна из вариаций класс.задачи из дискретной математики про рукопожатия и связана она с числами Каталана.
Рассмотрим наш случай: люди от 1 до N (или 1, 2, ..., 2*k = N) сидят за столом. Пусть f(k) - кол-во спосбов, ктр они могут пожать друг другу руки.
Давайте рассмотрим первого человека: он может пожать руку только тому человеку, кто имеет четный номер. Т.е. если первый человек жмет руку (2*t)-му, то их рукопожатие условно делит стол на две части:
- на одной стороне останется 2*t - 2 людей, и ктр могут пожать руки f(t - 1) способами;
- на другой стороне будет 2*k - 2*t людей, ктр смогу пожать руки f(k - t) способами.
Обощая этот случай для всех пар людей за столом получим, т.е. от 1 до k:
f(k) = f(0)*f(k - 1) + f(1)*f(k - 2) + ... + f(t - 1)*f(k - t) + ... + f(k - 1)*f(0),
f(1) = 1, f(0) = 1
Или:
Ck = Сумма(f(i)*f(k - i - 1)), где i от 0 до k - 1
а это и есть числа Каталана.
Также эту задачу можно свести к другим конструкциям, например:
- Триангуляции многоугольника. Количество различных триангуляций выпуклого многоугольника диагоналями равно числу Каталана.
- Разбиение вершин многоугольника на пары. Четное число точек на окружности можно объединить в пары непересекающимися хордами. Число способов таких объединений также равно числу Каталана.
Эти конструкции также приводят к появлению чисел Каталана.
Более подробно про числа Каталана и их свойства мы можете почитать тут:
Реализация:
https://gist.github.com/unilecs/4a2354aca2d84b2287b3657a3a22bd2d
Test:
https://dotnetfiddle.net/BjI9sU
P.S.
- наш канал @UniLecs
- наш чат: @UniLecs_Chat