Le Triangle de Pascal

En mathématiques, le triangle de Pascal est une présentation des coefficients binomiaux dans un triangle. Il fut nommé ainsi en l’honneur du mathématicien français Blaise Pascal. Celui ci permet de résoudre le problème du Lattice Path ou il faut calculer le nombre de chemins possible pour traverser un carré un partant du coin supérieur droit pour arriver au point en bas à gauche en se déplacent uniquement sur la droite et le bas.

Les classes

Pour calculer le triangle de Pascal nous allons devoir utiliser un tableau, composé de lignes et de cellules, un uses sur l’unité System.Generics.Collections est nécessaire. Les valeurs étant exponentielles c’est la raison à l’utilisation d’une variable de type Int64 plutôt que integer.

type
   TCellule = class
      Value: Int64;
   end;
 
   TLigne = class(TObjectList<TCellule>)
   public
      function ToString: string;
   end;
 
   TTableau = TObjectList<TLigne>

Pour afficher le résultat (dans un mémo par exemple), une procédure ToString est ajoutée sur le TLigne qui va retourner toutes les valeurs des cellules.

function TLigne.ToString: string;
var
   i: Integer;
begin
   Result := '';
 
   for i := 0 to Count - 1 do
      Result := Result + Items[i].Value.ToString;
end;

Traitement

Sur le triangle de Pascal chaque lignes commence par 1 et se termine par 1. Les cellules suivantes correspondent à la somme sur la ligne précédente de la cellule de même index plus celle de même index – 1. Nous allons créer une procédure qui prendra en paramètre la valeur recherchée.

procedure Calculer(aValue: integer);
var
   Tab    : TTableau;
   Ligne  : TLigne;
   Cellule: TCellule;
   i, j   : integer;
   Chrono : TStopwatch;
begin
   // création du tableau
   Tab    := TTableau.Create;
   // démarrage d'un chrono pour mesurer le temps de traitement
   Chrono := TStopwatch.StartNew;
 
   try
      // il faut prendre la valeur présente sur l'abscisse x aValue
      // et sur l'ordonnée y aValue * 2 il faut donc calculer jusqu'a cette valeur
      for i := 0 to aValue * 2 do
      begin
         // création d'une nouvelle ligne
         Ligne := TLigne.Create;
 
         // il faut boucler sur la variable i car à chaque fois qu'une
         // nouvelle ligne est ajoutée elle contient une cellule de plus
         // que la précédente
         for j := 0 to i do
         begin
            // création d'une cellule
            Cellule := TCellule.Create;
 
            // chaque ligne commence et termine par un 1
            if (j = 0) or (j = i) then
            begin
               Cellule.Value := 1;
            end
            else
            begin
               // la valeur de la cellule est égale à la somme sur la ligne précédente
               // de la valeur de la cellule du même index - 1 plus la valeur de la cellule du même index
               Cellule.Value := Tab[Tab.Count - 1][j - 1].Value + Tab[Tab.Count - 1][j].Value;
            end;
 
            // ajout de la cellule dans la ligne
            Ligne.Add(Cellule);
         end;
 
         // ajout de la ligne dans le tableau
         Tab.Add(Ligne);
      end;
 
      // arrêt du chrono
      Chrono.Stop;
 
      // affichage du nombre de chemin possible et du temps d'excéution du traitement (en ms)
      // le résultat correspond à la cellule aValue de la ligne aValue * 2
      LabelResultat.Caption := Tab[aValue * 2][aValue].Value.ToString + ' ' + Chrono.ElapsedMilliseconds.ToString + ' ms.';
   finally
      FreeAndNil(Tab);
   end;
end;

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*