algorithm
Алгоритм каталонского номера

Алгоритм каталонского номера Основная информация

Алгоритм каталитических чисел - алгоритм динамического программирования.

В комбинаторной математике каталонские числа образуют последовательность натуральных чисел, которые встречаются в различных задачах подсчета, часто включающие рекурсивно определенные объекты. Каталонские числа на неотрицательных целых числах представляют собой набор чисел, возникающих в задачах нумерации деревьев типа: «Сколько способов можно разделить обычный n-угольник на n-2 треугольники, если разные ориентации подсчитываются отдельно?»

Применение алгоритма каталонского номера:

1. Количество способов укладки монет в нижнем ряду, состоящее из n последовательных монет в плоскости, так что никакие монеты не могут быть помещены на две стороны нижних монет, и каждая дополнительная монета должна быть выше двух других монет, n-е каталонское число.
2. Количество способов группировки строки из n пар круглых скобок, так что каждая открытая скобка имеет соответствующую закрытую скобку, является n-м каталонским числом.
3. Количество способов разрезания 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;
    }
}