algorithm
Katalansk nummeralgoritm

Katalansk nummeralgoritm grundläggande information

Katalansk talalgoritm är dynamisk programmeringsalgoritm.

I kombinatorisk matematik bildar de katalanska siffrorna en sekvens av naturliga nummer som förekommer i olika räkningsproblem, ofta involverar rekursivt definierade objekt. De katalanska siffrorna på icke-negativa heltal n är en uppsättning siffror som uppstår i trädtalsproblem av typen, "På hur många sätt kan en vanlig n-gon delas upp i n-2 trianglar om olika orienteringar räknas separat?"

Tillämpning av katalansk nummeralgoritm:

1. Antalet sätt att stapla mynt på en bottenrad som består av n på varandra följande mynt i ett plan, så att inga mynt får läggas på de två sidorna av bottenmynten och varje ytterligare mynt måste ligga över två andra mynt, är det nionde katalanska numret.
2. Antalet sätt att gruppera en sträng med n par parenteser, så att varje öppen parentes har en matchande stängd parentes, är det nth katalanska numret.
3. Antalet sätt att skära en n + 2-sidig konvex polygon i ett plan i trianglar genom att ansluta hörn med raka, icke-korsande linjer är det nionde katalanska talet. Detta är applikationen där Euler var intresserad av.

Med hjälp av nollbaserad numrering ges det n: a katalanska talet direkt i termer av binomialkoefficienter genom följande ekvation.

Exempel på katalanska nummer:

Här värdet av n = 4. (Bästa exemplet - Från Wikipedia)

Hjälprum: O(n)
Tidskomplexitet: O(n^2)

C # Implementering

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