retwas

Présentation
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.



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

Code delphi :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
type
   TCellule = class
      Value: Int64;
   end;
 
   TLigne = class(TObjectList<TCellule>)
   public
      function ToString: string;
   end;
 
   TTableau = TObjectList<TLigne>;

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

Code delphi :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
function TLigne.ToString: string;
var
   i: Integer;
begin
   Result := '';
 
   for i := 0 to Count - 1 do
      Result := Result + Items[i].Value.ToString;
end;

Calculer
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 - 1 plus celle de même index. Nous allons créer une procédure qui prendra en paramètre la valeur recherchée.

Code delphi :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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;