algorithm
Katalanischer Zahlenalgorithmus

Grundlegende Informationen zum Algorithmus des katalanischen Zahlens

Katalanischer Zahlenalgorithmus ist ein dynamischer Programmieralgorithmus.

In der kombinatorischen Mathematik bilden die katalanischen Zahlen eine Folge von natürlichen Zahlen, die bei verschiedenen Zählproblemen vorkommen und häufig rekursiv definierte Objekte beinhalten. Die katalanischen Zahlen für nichtnegative Ganzzahlen n sind eine Anzahl von Zahlen, die bei Baumaufzählungsproblemen des Typs auftreten: "Inwiefern kann ein normales n-Gon in n-2 Dreiecke unterteilt werden, wenn unterschiedliche Ausrichtungen separat gezählt werden?"

Anwendung des Katalanischen Zahlenalgorithmus:

1. Die Anzahl der Möglichkeiten, Münzen in einer untersten Reihe zu stapeln, die aus n aufeinanderfolgenden Münzen in einer Ebene besteht, so dass keine Münzen auf die beiden Seiten der untersten Münzen gelegt werden dürfen und jede weitere Münze über zwei anderen Münzen liegen muss, ist die n-te katalanische Nummer.
2. Die Anzahl der Möglichkeiten zum Gruppieren eines Strings von n Paaren von Klammern, so dass jede offene Klammer eine passende geschlossene Klammer hat, ist die n-te katalanische Zahl.
3. Die Anzahl der Möglichkeiten, ein n + 2-seitiges konvexes Polygon in einer Ebene in Dreiecke zu schneiden, indem Scheitelpunkte mit geraden, nicht schneidenden Linien verbunden werden, ist die n-te katalanische Zahl. Dies ist die Anwendung, an der Euler interessiert war.

Unter Verwendung der auf Null basierenden Nummerierung wird die n- te katalanische Nummer direkt in Form von Binomialkoeffizienten durch die folgende Gleichung angegeben.

Beispiel für eine katalanische Nummer:

Hier Wert von n = 4. (Bestes Beispiel - Von Wikipedia)

Hilfsraum: O(n)
Zeitkomplexität: O(n^2)

C # -Implementierung

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