algorithm
Algorithme catalan

Algorithme des nombres catalans Informations de base

L'algorithme des nombres catalans est l'algorithme de programmation dynamique.

En mathématiques combinatoires, les nombres catalans forment une séquence de nombres naturels qui se produisent dans divers problèmes de comptage, impliquant souvent des objets définis récursivement. Les nombres catalans sur les entiers non négatifs n sont un ensemble de nombres apparaissant dans les problèmes de dénombrement du type: «De combien de manières un n-gon ordinaire peut-il être divisé en n-2 triangles si différentes orientations sont comptées séparément?

Application de l'algorithme des nombres catalans:

1. Le nombre de manières d'empiler des pièces sur une rangée inférieure constituée de n pièces consécutives dans un plan, de sorte qu'aucune pièce ne puisse être placée des deux côtés des pièces du bas et que chaque pièce supplémentaire soit supérieure à deux autres pièces, est le nième numéro catalan.
2. Le nombre de façons de regrouper une chaîne de n paires de parenthèses, de sorte que chaque parenthèse ouverte ait une parenthèse fermée, est le nième numéro catalan.
3. Le nombre de façons de découper en triangles un polygone convexe à 2 faces n + dans un plan en reliant des sommets à des lignes droites sans intersection est le nième nombre catalan. C'est l'application dans laquelle Euler était intéressé.

En utilisant la numérotation de base zéro, la n - ième nombre de Catalan est donnée directement en termes de coefficients binomiaux par l'équation suivante.

Exemple de numéro catalan:

Ici valeur de n = 4. (meilleur exemple - de Wikipedia)

Espace auxiliaire: O(n)
Complexité temporelle: O(n^2)

Implémentation 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;
    }
}