Triangle de Pascal et factorielle

Version imprimable

Bonjour,

J'ai tenté ce programme pour répondre à l'exercice , pourriez vous me dire mes erreurs?
Je vous remercie de votre aide précieuse!
voici l'énoncé:

Écrire un programme qui affiche les n premières lignes du triangle de Pascal (calcul des
coefficients binomiaux) de la façon suivante (ici : n = 5) :

Citation:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Pour rappel, l'élément qui se trouve à la ligne i et la colonne j représente le coefficient
binomial : Ci= i!/(j! (i -j)!)

N.B. : On pourra supposer, dans un premier temps, que l’on dispose d’une fonction
factorielle(k) permettant de calculer k! On écrira ensuite cette fonction

et voici mon programme.

Code:

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
Program Triangle ;
 
Var
  factdif,facti, temp,factj,c,n,i,j : integer ;            //fact di est la fact de i-j//
 
Begin
   writeln('entrez la taille du triangle');
   read(n);
 
   facti:=1;
   factj:=1;
   factdif:=1;
   for i:=1 to n do
      begin
          write('1');
             for j:=2 to n do
                       begin
                        if (i>j) then
                          begin
                            for i:=i downto 1  do
                             facti:=facti*i;
                            for j:=j downto 1 do
                               factj:=factj*j;
                            for temp:=(i-j)downto 1 do
                               factdif:= factdif*temp  ;
                            c:=(facti)/(factj*factdif);
                         end;
                        if i=j then
                              write('1');
 
                      end;
 
             for j=n-1 to 1 do
                begin
                     write(' ');
                end;
          writeln;
          readln;
      end;
end.

17/04/2016, 14h56
FChrisF

Sans porter de jugement sur l'algorithme lui-même, il me semble que le compilateur vous fournit déjà les informations nécessaires quant aux erreurs de syntaxe:

Citation:

Free Pascal Compiler version 3.0.0 [2016/02/14] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling triangle.pas
triangle.pas(20,34) Error: Illegal assignment to for-loop variable "i"
triangle.pas(22,34) Error: Illegal assignment to for-loop variable "j"
triangle.pas(26,39) Error: Incompatible types: got "Extended" expected "SmallInt"
triangle.pas(33,19) Fatal: Syntax error, ":=" expected but "=" found
Fatal: Compilation aborted

Ce qui suit n'est pas autorisé (2 premières erreurs): vous n'avez pas le droit de modifier le compteur d'une boucle dans la boucle elle-même. Utilisez une autre variable intermédiaire:

Code:

for i:=i downto 1 do // Dejà dans la boucle for "i:=1 to n do"

Le symbole "/" s'applique par définition à des nombres décimaux (3ième erreur). Pour une division concernant des entiers (et si le résultat attendu est entier aussi), utilisez l'instruction "div " (exemple: z := x div y ):

Code:

c:=(facti)/(factj*factdif);

Erreur évidente (4ième erreur): "=" au lieu de ":=":

Code:

for j=n-1 to 1 do

Accessoirement pour cette dernière instruction, si vous voulez faire une boucle dégressive, il faut utiliser l'instruction "for ... downto ...", plutôt que "for ... to ...".
17/04/2016, 15h08
Prof

Bonjour.

Apprendre la programmation sur le papier, c'est particulièrement difficile.
Comme il faut nécessairement contrôler ce qu'on écrit, on a besoin d'un accès à quelque chose ou quelqu'un qui puisse faire ce contrôle.

Le quelqu'un peut se trouver sur un forum, par exemple celui-ci.
Mais la démarche a ses limites, car il n'est pas possible de demander constamment de l'aide.
Surtout quand il s'agit de corriger des erreurs de débutant et qu'elles sont nombreuses dans le programme source.

Le quelque chose s'appelle un compilateur.
On le télécharge sur Internet, on l'installe sur son ordinateur, puis on le sollicite à chaque fois qu'on écrit un programme.
Il est disponible jour et nuit et signale inlassablement les erreurs d'écriture dans le programme.
Quand le programme s'exécute et qu'il ne fait pas ce qu'on souhaitait qu'il fasse, alors il est possible de demander de l'aide sur le forum.
Comme cela, celui qui apportera son aide n'aura pas à perdre son temps sur des bêtises du style

Citation:

for i:=i downto 1 do

D'où mon conseil : télécharger Free Pascal et utilisez-le pour corriger vos programmes.
Puis revenez nous demander conseil si l'un d'eux n'a pas le comportement voulu.

Je vous remercie pour votre réponse, j' ai modifié mon programme en prenant en compte vos remarques et j'ai ainsi réussi à le tester mais il ne m'affiche pas le triangle voulu.
C'est surtout la partie algorithmique qui me pose problème. Mon programme me semble aussi bien compliqué... Pourriez vous m'aiguiller pour trouver un algorithme plus convenable?

Code:

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
Program Triangle ;
 
Var
  factdif,facti, temp,factj,c,n,i,j : integer ;            //fact di est la fact de i-j//
 
Begin
   writeln('entrez la taille du triangle');
   read(n);
 
   facti:=1;
   factj:=1;
   factdif:=1;
   for i:=1 to n do
      begin
          write('1');
             for j:=2 to n do
                       begin
                        if (i>j) then
                          begin
                            while i>0 do
                              begin
                               facti:=facti*i;
                               i:=i-1;
                              end;
                            while j>0 do
                              begin
                                factj:=factj*j;
                                 j:=j-1;
                               end;
                            while(i-j)>0 do
                              begin
                               factdif:= factdif*temp  ;
                               temp:=(i-j)-1;
                               end;
                            c:=(facti)div(factj*factdif);
                         end;
                        if i=j then
                              write('1');
 
                      end;
 
             for j:=n-1 to 1 do
                begin
                     write(' ');
                end;
          writeln;
          readln;
      end;
end.

17/04/2016, 15h21
wattelal

Je m'excuse, j'avais testé sur le compilateur dev pascal justement mais je ne retrouvais pas mon erreur... Je suis débutante en programmation. Mais je tient compte de votre remarque .
17/04/2016, 19h57
Prof

Re-bonjour.

Tout d'abord, il est INDISPENSABLE d'utiliser les balises [code] et [/code] pour afficher le code source lorsqu'il y a plus de deux ou trois lignes.
En effet l'utilisation de ces deux balises permet de conserver l'indentation du code et en facilite la lecture.
Sinon, votre code est indigeste et on n'a pas envie de le lire pour trouver les erreurs, comme c'est le cas dans votre post ci-dessus.

Ensuite, l'énoncé demande d'utiliser dans un premier temps une fonction qui retourne la factorielle, puis de définir cette fonction.
Il faut respecter l'énoncé et donc construire cette fonction.
Si vous n'y arrivez pas, on peut vous aider.
18/04/2016, 13h51
FChrisF
Comme indiqué précédemment par Prof, dans un premier temps et pour ne pas compliquer les choses commencez d'abord par décomposer votre problème en éléments simples:
- construisez d'abord une fonction qui calcule la factorielle de la valeur n,
- puis construisez une fonction qui calcule le coefficient binomial (ou nombre de combinaisons) des valeurs n et k; cette fonction utilisera votre fonction factorielle précédente.
Une fois cela réalisé et opérationnel, la résolution de votre problème devient très simple: 2 boucles imbriquées, l'appel à votre fonction de calcul du coefficient binomial, quelques instructions "write"/"writeln", et le tour est joué.

Note: sur un plan purement didactique (c'est une autre histoire sur un plan pragmatique), votre fonction de calcul de factorielle pourra être écrite sous forme d'une fonction récursive; mais ce n'est bien évident pas une obligation.

**Edit**

L'utilisation d'une fonction factorielle implique implicitement un nombre maximal de lignes très réduit pour le triangle de Pascal (compte tenu des limitations de la taille des variables numériques). L'obtention d'un plus grand nombre de lignes nécessite ainsi "l'optimisation" de la fonction de calcul du coefficient binomial; ce qui pourrait être une seconde étape ...
18/04/2016, 15h16
droggo

Bonjour,

Citation:

Envoyé par FChrisF

Note: sur un plan purement didactique (c'est une autre histoire sur un plan pragmatique), votre fonction de calcul de factorielle pourra être écrite sous forme d'une fonction récursive; mais ce n'est bien évident pas une obligation.

Très mauvaise suggestion, il ne faut pas introduire la récursivité là où elle n'apparaît pas naturellement, et le calcul de factorielle est typiquement dans ce cas. :(
18/04/2016, 15h58
FChrisF

Citation:

Envoyé par droggo

Bonjour,

Très mauvaise suggestion, il ne faut pas introduire la récursivité là où elle n'apparaît pas naturellement, et le calcul de factorielle est typiquement dans ce cas. :(

Pour être tout à fait clair, je ne suis pas un partisan des fonctions récursives, loin de là. Mais la récursivité est typiquement un des sujets de cours en Pascal (tout au moins, cela l'était de mon temps).

Je ne suis par ailleurs pas certain de bien comprendre votre remarque sur la récursivité "naturelle" du calcul de factorielle.
Cf. ce lien: https://fr.wikipedia.org/wiki/Algori...la_factorielle

*Edit* Et aussi ce lien: http://recursivite.developpez.com/?page=page_2#LI-C
18/04/2016, 16h02
anapurna
salut,

au contraire la factoriel entre dans ce cas

pour rappel :

Citation:

Pour tout entier n > 0, n! = (n – 1)! × n.

ce qui peut tres simplement se traduire en pascal par
Code:

1 2 3 4 5 6 7 8 Function Factoriel(N:integer):integer; Begin If N > 1 Then Factoriel := n * Factoriel(N - 1) Else Factoriel := 1; End;
PS : arghh trop tard

Salut,

Un peu tardivement...pour le fun!

Pour la récursivité, je l'utilise quand elle est incontournable ou que la dérécursification de l'algorithme est trop complexe ou qu'elle réduit la compréhensibilité du code.

Pour la factorielle, l'emploi de la récursivité n'est d'aucun bénéfice, elle consomme plus de mémoire via la pile d'exécution donc je retiens l'algorithme itératif.

Le calcul direct des combinaisons peut être remplacé par un calcul légèrement moins lourd, en effet, on a C(n,p) = n! / p! * (n-p)! mais aussi C(n,p) = n*(n-1)*...*(n-p+1) / p!. En général on voit cela en cours donc je ne m'attarde pas.

Pour le triangle de Pascal, en utilisant la propriété C(n+1,p+1) = C(n,p) + C(n,p+1), on peut construire alors toute ligne du triangle à partir de celle qui la précède, sans passer par des factorielles. On commence par la première ligne associée à la puissance 0 et réduite à l'entier 1 puis on calcule celle de puissance 1, and so on...

En se débrouillant bien, un seul tableau suffit.

Code:

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
program Triangle;
 
{$MODE OBJFPC}
{$M+}
 
uses SysUtils;
 
// Version récursive, efficace mais consomme de la pile système
// suppose que N >= 0
function FactoRecurs(N: Integer): Integer;
begin
  if (N > 1) then
    Result := N * FactoRecurs(N-1)
  else
    Result := 1;
End;
 
// Version itérative, ne consomme que 2 variable (Result et i)
// la version récursive bien que jolie n'apporte pas grand chose...
function Facto(N: Integer): Integer;
var
  i: Integer;
begin
  Result := 1;
  for i := 2 to N do
    Result := Result * i;
End;
 
// dans la pratique, du fait du type entier choisi (Integer), on ne peut pas espérer dépasser 12!
// après c'est le dépassement de capacité au mieux, des calculs faux au pire.
 
// C(n,p) = n! / p! * (n-p)!
function CombinaisonBestiale(N, P: Integer): Integer;
begin
  if (N<P) then
    raise Exception.Create('CombinaisonBestiale : Paramètres incohérents');
  Result := Facto(N) div (Facto(P) * Facto(N-P));
End;
 
// Version moins chère en calcul : C(n,p) = n*(n-1)*...*(n-p+1) / p!
// retarde le dépassement de capacité des entiers en limitant l'amplitudes des multiplications.
function Combinaison(N, P: Integer): Integer;
var
  deno, numer: Integer;
begin
  if (N<P) then
    raise Exception.Create('Combinaison: Paramètres incohérents');
  if ((N-P) < P) then
    // par symétrie du calcul, cela réduira le nombre de boucle ci-dessous.
    P := N-P;
  numer := 1; deno := 1;
  while (P>0) do
  begin
    numer := numer * N; Dec(N);
    deno := deno *P; Dec(P);
  end;
  Result := numer div deno;
  // fait un peu moins de multiplications que la version bestiale.
End;
 
// Ce qui suit construit le triangle en n'utilisant que des additions, on évite ainsi le dépassement de capacité
// lié au calcul de factorielle et ne met en oeuvre que des additions.
 
procedure InitTableau(var Ligne: array of Integer);
var
  i: Integer;
begin
  for i := Low(ligne) to High(Ligne) do
    Ligne[i] := 0;
  Ligne[0] := 1;
End;
 
procedure EcritLigne(Ligne: array of Integer);
var
   i : Integer;
begin
   i := 0;
   while (i<=High(Ligne)) and (Ligne[i]<>0) do
   begin
     Write(Ligne[i]:7, ' ');
     Inc(i);
   end;
   WriteLn();
End;
 
procedure RemplirLigneParSomme(var Ligne: array of Integer);
var
  i: Integer;
begin
  // Fait la mise à jour à partir de la fin pour éviter de travailler avec 2 tableaux
  for i := High(Ligne) downto Low(Ligne)+1 do
    Ligne[i] := Ligne[i] + Ligne[i-1];
End;
 
procedure RemplirLigneParCombi(var Ligne: array of Integer; N: Integer);
var
  i: Integer;
begin
  for i := Low(Ligne) to N do
//     Ligne[i] := CombinaisonBestiale(N, i); // Echoue à NMax = 13 (limite des entiers)
    Ligne[i] := Combinaison(N, i);
End;
 
var
  ligne : array of Integer;
  NMax, i : Integer;
 
begin
  WriteLn('Entrez la longueur de la base du triangle');
  ReadLn(NMax);
  // Ajuster la taille du tableau
  SetLength(Ligne, NMax+1);
 
  WriteLn('Remplissage par somme');
  InitTableau(Ligne);
  EcritLigne(Ligne); // Puissance 0
  for i := 1 to NMax do
  begin
    RemplirLigneParSomme(Ligne);
    EcritLigne(Ligne);
  end;
  WriteLn();
 
  WriteLn('Remplissage par combinaison');
  InitTableau(Ligne);
  EcritLigne(Ligne); // Puissance 0
  for i := 0 to NMax do
  begin
    RemplirLigneParCombi(Ligne, i);
    EcritLigne(Ligne);
  end;
 
  ReadLn();
END.

Moralité : Un bien grand programme pour quelque chose sans utilité pratique.

tchüss...