Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

Calculer les nombres de catalan en C++ et Python

 

Calculer les nombres de catalan en C++ et Python

Les nombres catalans sont une suite d'entiers positifs qui apparaissent dans de nombreux problèmes de dénombrement en combinatoire. Ils comptent certains types de chemins de réseau, de permutations, d'arbres binaires et de nombreux autres objets combinatoires. Ils satisfont une relation de récurrence fondamentale et ont une formule de forme fermée en termes de coefficients binomiaux.

Les nombres catalans \(C_0, C_1, \dots, C_n, \dots \) sont donnés par la formule : $$ C_n=\frac{1}{n+1} \binom{2n}{n} $$

Les premiers nombres catalans sont :

$$C_0=1, C_1=1, C_2=2, C_3=5, C_4=14, C_5=42$$

Entrée
Sortie
  Exemples
Entrée du programmeSortie du programme
1016796
81430
254861946401452

Solution 1 : Récursive

Les nombres catalans satisfont la relation de récurrence ci-dessous :

$$ C_{n+1}=C_0C_n + C_1C_{n-1} + \dots + C_nC_0=\sum_{k=0}^{n} C_kC_{n-k} . $$ $$C_0=1$$

#include <iostream>

using namespace std;

unsigned long long catalan(int n){

    // cas de base
    if (n <= 1)
        return 1;
 
    unsigned long long val = 0;
    for(int i=0;i<n;i++)
        val += catalan(i) * catalan(n-i-1);
 
    return val;

}

int main()
{
    int n;
    cin >> n;
    
    cout << catalan(n);
    
    return 0;
}
                    
from ctypes import c_longlong as ll

def catalan(n):

    # cas de base
    if n <= 1:
        return 1
 
    val = 0
    for i in range(n):
        val += catalan(i) * catalan(n-i-1)
 
    return val

n=int(input())
print(ll(catalan(n)))
                    
Complexité :

La valeur du nième nombre catalan est exponentielle ce qui rend la complexité temporelle exponentielle.

Solution 2 : Programmation dynamique

Nous pouvons observer que l'implémentation récursive ci-dessus fait beaucoup de travail répété. Puisqu'il y a la propriété chevauchement de sous-problème, nous pouvons utiliser la programmation dynamique.

#include <iostream>

using namespace std;

unsigned long long catalan(int n){

    unsigned long long DP[n + 1];
    DP[0] = DP[1] = 1;

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

}

int main()
{
    int n;
    cin >> n;
    
    cout << catalan(n);
    
    return 0;
}
                    
from ctypes import c_longlong as ll

def catalan(n):

    DP=[0 for _ in range(n+1)]
    DP[0]=1
    DP[1]=1

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

n=int(input())
print(ll(catalan(n)))
                    
Complexité :
  •  Complexité temporelle : \(O(n^2)\)
  •  Complexité spatiale : \(O(n)\)

Solution 3 : En utilisant le coefficient binomial

En utilisant la solution linéaire de calcul du coefficient binomial, nous pouvons réduire la complexité du calcul du nombre catalan à linéaire.

$$C_n=\frac{1}{n+1} \binom{2n}{n} $$

Visitez le cours suivant pour la solution du coefficient binomial : Cliquez ici

#include <iostream>

using namespace std;

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

    unsigned long long coef=1;

    /* 
        Calculer la valeur de [n * (n-1) *---* (n-k + 1)]
        / [k * (k-1) *----* 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;
    C=coefBinomial(2*n,n);
 
    return C/(n+1);

}

int main()
{
    int n;
    cin >> n;
    
    cout << catalan(n);
    
    return 0;
}
                    
from ctypes import c_longlong as ll

def coefBinomial(n, k):
    if(k>(n-k)):
        k=n-k
    
    coef=1
    # Calculer la valeur de [n * (n-1) *---* (n-k + 1)]
    # / [k * (k-1) *----* 1]
    for i in range(k):
        coef=coef*(n-i)
        coef=coef//(i+1)

    return coef

def catalan(n):

    C=coefBinomial(2*n,n)
    return C//(n+1)

n=int(input())
print(ll(catalan(n)))
                    
Complexité :
  •  Complexité temporelle : \(O(n)\)
  •  Complexité spatiale : \(O(1)\)

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.