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. |
Triangle de Pascal et factorielle
Répondre avec citation
Envoyé par FChrisF
Partager