Calculer les nombres de catalan en C++ et Python

On note cette suite C0, C1, C2, ..., Cn, .... Le n-ième nombre de Catalan est donné par la formule fermée suivante :

Les premières valeurs sont :

C0 = 1
C1 = 1
C2 = 2
C3 = 5
C4 = 14
C5 = 42

Problème

Écrire un programme qui lit un entier n et affiche la valeur du nombre de Catalan Cn.

Entrée

L’entrée contient un entier n.

Sortie

Afficher la valeur du nombre de Catalan Cn.

Exemples

10

16796

8

1430

25

4861946401452

Relation de récurrence

Les nombres de Catalan vérifient également une relation de récurrence fondamentale :

C0 = 1

Pour n ≥ 0 :
C(n+1) = C0·Cn + C1·C(n-1) + ... + Cn·C0
       = Σ[k=0..n] Ck · C(n-k)

Cette relation exprime chaque terme à partir des termes précédents. Elle est particulièrement utile pour construire une solution récursive ou une solution par programmation dynamique.

Solution 1 : approche récursive

On applique directement la relation de récurrence. Le cas de base est C0 = 1 et C1 = 1. Pour n > 1, on somme tous les produits :

$$ C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i} $$

#include <iostream>
using namespace std;

unsigned long long catalan(int n) {
    if (n <= 1)
        return 1ULL;

    unsigned long long val = 0;
    for (int i = 0; i < n; i++)
        val += catalan(i) * catalan(n - 1 - i);

    return val;
}

int main() {
    int n;
    cin >> n;
    cout << catalan(n);
    return 0;
}

def catalan(n):
    if n <= 1:
        return 1

    val = 0
    for i in range(n):
        val += catalan(i) * catalan(n - 1 - i)

    return val

n = int(input())
print(catalan(n))

Solution 2 : programmation dynamique

Dans la version récursive, les mêmes valeurs de Ck sont recalculées plusieurs fois. L’idée de la programmation dynamique consiste à stocker les valeurs déjà calculées dans un tableau puis à construire progressivement les termes de C0 jusqu’à Cn.

#include <iostream>
#include <vector>
using namespace std;

unsigned long long catalan(int n) {
    vector<unsigned long long> dp(n + 1, 0);

    dp[0] = 1;
    if (n >= 1)
        dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }

    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << catalan(n);
    return 0;
}

def catalan(n):
    dp = [0] * (n + 1)

    dp[0] = 1
    if n >= 1:
        dp[1] = 1

    for i in range(2, n + 1):
        for j in range(i):
            dp[i] += dp[j] * dp[i - 1 - j]

    return dp[n]

n = int(input())
print(catalan(n))

Solution 3 : formule fermée avec le coefficient binomial

Lorsque l’on souhaite une méthode plus rapide, on peut utiliser directement la formule :

Il suffit donc de calculer efficacement le coefficient binomial \(\binom{2n}{n}\), puis de diviser le résultat par n+1.

#include <iostream>
using namespace std;

unsigned long long coef_binomial(int n, int k) {
    if (k > n - k)
        k = n - k;

    unsigned long long coef = 1;
    for (int i = 0; i < k; i++) {
        coef *= (n - i);
        coef /= (i + 1);
    }

    return coef;
}

unsigned long long catalan(int n) {
    unsigned long long c = coef_binomial(2 * n, n);
    return c / (n + 1);
}

int main() {
    int n;
    cin >> n;
    cout << catalan(n);
    return 0;
}

def coef_binomial(n, k):
    if k > n - k:
        k = n - k

    coef = 1
    for i in range(k):
        coef = coef * (n - i)
        coef = coef // (i + 1)

    return coef

def catalan(n):
    c = coef_binomial(2 * n, n)
    return c // (n + 1)

n = int(input())
print(catalan(n))

Comparaison des trois approches