Dérécursification du triangle de Pascal

 

On veut réaliser de façon itérative le programme qui affiche le triangle de Pascal. On suppose pour cela que nous pouvons afficher seulement 25 lignes, donc on utilise un tableau de 26 entiers. Bien évidemment, on peut modifier sa taille si on veut. Pour afficher les lignes du triangle de Pascal, on entre manuellement le nombre de lignes, et on fait ensuite une boucle:

- qui appelle la procédure de calcul des lignes

- qui les affiche.

On sait que, pour les deux premières lignes, le tableau ne contient que des 1, donc on va l'initialiser manuellement. La procédure de calcul se charge du reste. Le programme sera donc :

tab_coef[1]:=1;tab_coef[2]:=1;

for ligne:=2 to nombre_lignes do

    calculer(ligne);

On sait que, dans le triangle de Pascal, chaque coefficient est égal à la somme du nombre immédiatement supérieur et du nombre au dessus à gauche.

0 : 1          (a+b)0 = 1

1 : 1 1        (a+b)1 = 1*a + 1*b

2 : 1 2 1      (a+b)2 = 1*a2 + 2*a*b + 1*b2

3 : 1 3 3 1    (a+b)3 = 1*a3 + 3*a²*b + 3*a*b² + 1*b3

4 : 1 4 6 4 1  (a+b)4 = 1*a4 + 4*a3*b + 6*a²*b² + 4*a*b3 + 1*b4

Nous n'avons ici qu'un tableau à une dimension que nous allons progressivement modifier. On dispose dès le départ de la ligne 1, et si on veut calculer la ligne 2 on n'a qu'à rajouter un 1 à la fin du tableau (qui correspond à la diagonale) et modifier le contenu du tableau en faisant les sommes qui conviennent.

Il faut faire attention : supposons qu'on a déjà calculé la ligne 2, et qu'on veut calculer la ligne 3. Le deuxième élément de la ligne 3 est égal à la somme du premier élément de la ligne 2 et du deuxième élément de la ligne 2. On le calcule et on le met dans le tableau, pour obtenir : 1 3 1 1. Et quand on calcule le troisième élément, on obtient 1 3 4 1 au lieu de 1 3 3 1.

L'erreur vient du fait qu'on n'a pas utilisé l'ancienne valeur "2" du tableau, mais la nouvelle valeur "3" et "3+1=4". Il faut donc parcourir le tableau en sens inverse. En effet :

- on a 1 2 1.

- on rajoute un 1 à la fin : 1 2 1 1

- on parcourt le tableau en sens inverse à partir de l'avant dernière position (la troisième position) :

    tab_coef[3]:=tab_coef[2]+tab_coef[3] = 3 donc on a 1 2 3 1

- on avance vers le début (en deuxième position):

    tab_coef[2]:=tab_coef[1]+tab_coef[2] = 3 donc on a 1 3 3 1

On remarque que la valeur est la bonne. Nous nous sommes arrêtés à la valeur 2, donc la boucle sera de la forme :

    for i:=j downto 2 do

Voici donc le programme affichant le triangle de Pascal de façon itérative :

 

procedure TForm1.Button1Click(Sender: TObject);
var ligne: integer;
  tab_coef: array[1..26] of integer;
 
  procedure calculer(j: integer);
  var i: integer;
    s: string;
  begin
    tab_coef[j + 1] := 1;
    for i := j downto 2 do
      tab_coef[i] := tab_coef[i - 1] + tab_coef[i];
    s := '';
    for i := 1 to j + 1 do s := s + inttostr(tab_coef[i]) + '  ';
    memo1.lines.add(s);
  end;
begin
  if strtoint(edit1.text) > 25 then
  begin
    showMessage('La valeur doit être inférieure à 25 !');
    exit;
  end;
  fillchar(tab_coef, sizeof(tab_coef), #0);
  tab_coef[1] := 1; tab_coef[2] := 1;
  for ligne := 2 to strtoint(edit1.text) do
    calculer(ligne);
end;

 

Télécharger le code source Delphi