![Pentru linia i pentru i<n se obtine astfel: C[i,j]=max{T[i,j]+C[i+1,j],T[i,j]+ +C[i+1,j+1]} i:=1,n-1; j:=1,i;](https://image.slidesharecdn.com/triunghi-1232705874927654-3/85/Triunghi-3-320.jpg)
![C [n,1]:=T[n,1]; T[1,1]=2; T[4,1]=5; C[n,2]:=T[n,2]; T[2,1]=3; T[4,2]=6; . T[2,2]=5; T[4,3]=1; . T[3,1]=6; T[4,4]=4. . T[3,2]=3; C[n,n]:=T[n,n]; T[3,3]=4; 2 5 3 4 5 6 1 4 T:](https://image.slidesharecdn.com/triunghi-1232705874927654-3/85/Triunghi-7-320.jpg)
![Implementarea programului: Pentru a tipari numerele luate 樽n calcul se folosete o matrice numit drum 樽n care pentru fiecare i,j se ob釘ine coloana 樽n care se gasete succesorul lui T [i,j]; n-num rul de linii ; t,c, drum -de tip matrice;](https://image.slidesharecdn.com/triunghi-1232705874927654-3/85/Triunghi-8-320.jpg)
![Programul program triunghi; type matrice=array[1..10,1..10]of integer; var t,c,drum:matrice; i,j:integer; Begin write(n=);readln(n); for i:=1 to n do for j:=1 to I do begin write(t[,i,,,j,]=);readln(t[i,j]);end; for j:=1 to n do c[n,j]:=t[n,j]; for i:= n-1 downto 1 do begin for j:=1 to I do if c[i+1,j]<c[i+1,j+1] then begin](https://image.slidesharecdn.com/triunghi-1232705874927654-3/85/Triunghi-9-320.jpg)
![c[i,j]:=t[i,j]+c[i+1,j+1]; drum[i,j]:=j+1;end else begin c[i,j]:=t[i,j]+c[i+1,j]; drum[i,j]:=j;end;end; writeln(suma maxima este,c[1,1]); i:=1;j:=1; while i<=n do begin writeln(t[i,j]); j:= drum[i,j]; i:=i+1;end; readln; End.](https://image.slidesharecdn.com/triunghi-1232705874927654-3/85/Triunghi-10-320.jpg)
More Related Content
What's hot (8)
Viewers also liked (16)
Triunghi
- 1. Elev: Sima Marcel Cls a XI-a B
- 2. Enuntul problemei Se consider un triunghi de numere naturale format din n linii. Prima linie con釘ine un numr,a doua dou numere, ... ,iar ultima,n numere naturale. Cu ajutorul acestui triunghi se pot forma sume de numere naturale 樽n felul urmtor: Se pornete cu numrul de pe linia 1; Succesorul unui numr se afl pe linia urmatoare plasat sub el(aceeai coloan) sau pe diagonal la dreapt(coloana crete cu 1);
- 3. Pentru linia i pentru i<n se obtine astfel: C[i,j]=max{T[i,j]+C[i+1,j],T[i,j]+ +C[i+1,j+1]} i:=1,n-1; j:=1,i;
- 4. T: 2 3 3 5 5 6 6 4 4 1 5 6 1 4 12 9 9 9 8 7 C: 6 6 6 + + + + + + 5 = = = = = = 11 11 12 < < < < 3 3 6 1 4 > 4 3 3 3 4 4 4 + + + + + 1 = = = = = 5 5 8 6 6 6 9 > 5 5 3 4 8 8 9 9 2 2 + = 3 5 5 5 7 12 8 9 9 9 7
- 5. 2 3 3 5 5 6 6 4 4 1 T: 5 6 1 4 C: 12 9 9 6 6 6 + + + + 5 = = = = 11 11 12 < 3 3 6 1 4 > 4 8 + = = < 4 4 4 + 1 5 5 8 12 + + + + + + 5 = = = = = = 17 3 3 9 12 15 15 12 5 9 8 14 14 13 13 > > 2 2 15 14 17 16 16 > 12 9 8 15 14 17
- 6. Algoritmul Pentru etapa i se trateaz linia i a triunghiului. Fie un ir de n numere care respect condi釘iile prolemei i care formeaz suma maxim, de aici considerm numrul care a fost preluat de pe linia i;vom forma un triunghi de la baz la v但rf cu sumele maxime care se pot forma cu fiecare numr.ntr-o matrice T citim t riunghiul de numere si 樽ntr-o matrice C vom avea urmtoarele rela釘ii:
- 7. C [n,1]:=T[n,1]; T[1,1]=2; T[4,1]=5; C[n,2]:=T[n,2]; T[2,1]=3; T[4,2]=6; . T[2,2]=5; T[4,3]=1; . T[3,1]=6; T[4,4]=4. . T[3,2]=3; C[n,n]:=T[n,n]; T[3,3]=4; 2 5 3 4 5 6 1 4 T:
- 8. Implementarea programului: Pentru a tipari numerele luate 樽n calcul se folosete o matrice numit drum 樽n care pentru fiecare i,j se ob釘ine coloana 樽n care se gasete succesorul lui T [i,j]; n-num rul de linii ; t,c, drum -de tip matrice;
- 9. Programul program triunghi; type matrice=array[1..10,1..10]of integer; var t,c,drum:matrice; i,j:integer; Begin write(n=);readln(n); for i:=1 to n do for j:=1 to I do begin write(t[,i,,,j,]=);readln(t[i,j]);end; for j:=1 to n do c[n,j]:=t[n,j]; for i:= n-1 downto 1 do begin for j:=1 to I do if c[i+1,j]<c[i+1,j+1] then begin
- 10. c[i,j]:=t[i,j]+c[i+1,j+1]; drum[i,j]:=j+1;end else begin c[i,j]:=t[i,j]+c[i+1,j]; drum[i,j]:=j;end;end; writeln(suma maxima este,c[1,1]); i:=1;j:=1; while i<=n do begin writeln(t[i,j]); j:= drum[i,j]; i:=i+1;end; readln; End.