2000 - TAM GIÁC SỐUSES CRT;CONST INP='INPUT.TXT';VAR N,SMAX

Bài 38/2000 - Tam giác số

Uses Crt;

Const inp='INPUT.TXT';

Var N,Smax: integer;

a: array [1..100,1..100] of integer;

{---}

Procedure Nhap;

Var f: text;

i,j: integer;

Begin

Assign(f,inp);

Reset(f);

Readln(f,n);

For i:=1 to N do

begin

For j:=1 to i do Read(f,a[i,j]);

Readln(f);

end;

Close(f);

End;

Procedure Thu(S,i,j: integer);

Var k,S_new: integer;

S_new:=S+a[i,j];

If i=N then

If S_new>Smax then Smax:=S_new;

end

else

For k:=j to j+1 do Thu(S_new, i+1, k);

BEGIN

Nhap;

Smax:=0;

Thu(0,1,1);

Write('Smax = ',Smax);

Readln;

END.

Dưới đây các bạn có thể tham khảo lời giải của bạn Phạm Đức Thanh dùng phương pháp quy hoạch động

trên mảng hai chiều:

Program bai38;

Uses crt;

Type mang = array[1..100,1..100] of integer;

Var

f:text;

i,j,n:integer;

a,b:mang;

Procedure Input;

clrscr;

Assign(f,'input.txt');

reset(f);

readln(f,n);

for j:=1 to n do

begin

for i:=2 to j+1 do

read(f,a[j,i]);

end;

close(f);

end;

Function Max(m,n:integer):integer;

if n>m then Max:=n

else Max:=m;

Procedure MakeArrayOfQHD;

b[1,2]:=a[1,2];

for j:=1 to n do b[j,1]:=-maxint;

for i:=3 to n do b[1,i]:=-maxint;

for j:=2 to n do

begin

for i:=2 to j+1 do

b[j,i]:=a[j,i]+max(b[j-1,i],b[j-1,i-1]);

end;

Procedure FindMax;

var max:integer;

max:=b[n,1];

for i:=2 to n do

if b[n,i]>max then max:=b[n,i];

writeln('Smax:=',max);

readln;

Input;

makearrayofQHD;

FindMax;

Nhận xét: Lời giải dùng thuật toán quy hoạch động của Phạm Đức Thanh tốt hơn rất nhiều so với thuật toán

đệ quy quay lui.