Un petit souvenir des séminaires avec les nombres de Catalan

Un petit souvenir des séminaires avec les nombres de Catalan

Cette semaine, c'est Alexandre qui vous propose un #KataOfTheWeek : Les nombres de Catalan

Briefing du Kata : Les nombres de Catalan apparaissent dans divers domaines des mathématiques dans des problématiques de dénombrement… Contrairement à ce que leur nom indique, ils n'ont rien de catalan. Ils sont nommés en l'honneur du mathématicien Belge Éponyme.

Je vous propose de faire un petit peu de maths puis d'implémenter différentes solution et de comparer leurs performances.

Les nombres de Catalan apparaissent par exemple dans le décompte du nombre d'association de paires de parenthèses, c'est aussi la manière la plus simple de faire apparaître une hypothèse de récurrence : n: nombre de paires de parenthèses Cn: nombre de possibilité d'association de ces paires n = 0 - - Cn = 1

n = 1 - () - Cn = 1

n = 2 - (()), ()() - Cn = 2

n = 3 - ((())), (()()), (())(), ()(()), ()()() - Cn = 5

n = 4 - (((()))), ((()())), ((())()), (()(())), (()()()), … - Cn = 14

Pour ceux qui voudraient retrouver la solution de récurrence, arrêtez vous ici et prenez un petit bout de papier.

Pour les autres vous trouverez la relation de récurence suivante:

katalan_recursive

C'est parti :

  • implémente cette fonction
  • calcule sa complexité
  • teste le calcul sur des valeurs élevées de n (pas la peine de trop s'énerver non plus)

On voit que la méthode récursive "simple" s'effondre assez rapidement.

Comparons maintenant la solution recursive à l'analytique :

katalan_recursive

(Rappelez vous que factoriel 21 explose MAX_LONG…)

Il existe une autre relation de récurrence beaucoup plus performante :

katalan_recursive

Compare ces différentes méthodes, laquelle est la plus performante, la plus élégante…?

Saurez-vous résoudre le problème ?

Bon courage ! Retrouvez la solution dans cet article 😉