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 programme | Sortie du programme |
|---|---|
| 10 | 16796 |
| 8 | 1430 |
| 25 | 4861946401452 |
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)\)
