algorithm
Алгоритм каталонского номера
Поиск…
Алгоритм каталонского номера Основная информация
Алгоритм каталитических чисел - алгоритм динамического программирования.
В комбинаторной математике каталонские числа образуют последовательность натуральных чисел, которые встречаются в различных задачах подсчета, часто включающие рекурсивно определенные объекты. Каталонские числа на неотрицательных целых числах представляют собой набор чисел, возникающих в задачах нумерации деревьев типа: «Сколько способов можно разделить обычный n-угольник на n-2 треугольники, если разные ориентации подсчитываются отдельно?»
Применение алгоритма каталонского номера:
- Количество способов укладки монет в нижнем ряду, состоящее из n последовательных монет в плоскости, так что никакие монеты не могут быть помещены на две стороны нижних монет, и каждая дополнительная монета должна быть выше двух других монет, n-е каталонское число.
- Количество способов группировки строки из n пар круглых скобок, так что каждая открытая скобка имеет соответствующую закрытую скобку, является n-м каталонским числом.
- Количество способов разрезания n + 2-стороннего выпуклого многоугольника в плоскости на треугольники путем соединения вершин с прямыми непересекающимися линиями является n-м каталонским числом. Это приложение, в котором интересовался Эйлер.
Используя нулевую нумерацию, n- е каталонское число задается непосредственно в терминах биномиальных коэффициентов следующим уравнением.
Пример каталонского номера:
Здесь значение n = 4. (Лучший пример - из Википедии)
Вспомогательное пространство: O(n)
Сложность времени: O(n^2)
Реализация C #
public class CatalanNumber
{
public static int Main(int number)
{
int result = 0;
if (number <= 1) return 1;
for (int i = 0; i < number; i++)
{
result += Main(i)*Main(number - i - 1);
}
return result;
}
}