algorithm
Kataloński algorytm liczbowy

Kataloński algorytm liczbowy Podstawowe informacje

Kataloński algorytm liczbowy jest algorytmem programowania dynamicznego.

W matematyce kombinatorycznej liczby katalońskie tworzą sekwencję liczb naturalnych występujących w różnych problemach zliczania, często obejmujących obiekty zdefiniowane rekurencyjnie. Liczby katalońskie na nieujemnych liczbach całkowitych n są zbiorem liczb pojawiających się w problemach z wyliczaniem drzew typu: „Na ile sposobów można podzielić zwykły n-gon na trójkąty n-2, jeśli różne orientacje są liczone osobno?”

Zastosowanie katalońskiego algorytmu liczbowego:

1. Liczba sposobów na ułożenie monet w dolnym rzędzie składającym się z n kolejnych monet w płaszczyźnie, tak aby nie można było umieszczać monet po obu stronach dolnych monet, a każda dodatkowa moneta musi znajdować się powyżej dwóch innych monet, n-ta liczba katalońska.
2. Liczba sposobów grupowania ciągu n par nawiasów, tak aby każdy otwarty nawias miał pasujący zamknięty nawias, jest n-tą liczbą katalońską.
3. Liczba sposobów cięcia n + 2-stronnie wypukłego wielokąta w płaszczyźnie na trójkąty poprzez połączenie wierzchołków z prostymi, nie przecinającymi się liniami to n-ta liczba katalońska. Jest to aplikacja, która była zainteresowana Euler.

Stosując numerację zerową, n- ta liczba katalońska jest podawana bezpośrednio w kategoriach współczynników dwumianowych za pomocą następującego równania.

Przykład liczby katalońskiej:

Tutaj wartość n = 4. (Najlepszy przykład - z Wikipedii)

Przestrzeń pomocnicza: O(n)
Złożoność czasu: O(n^2)

Implementacja 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;
    }
}