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.
Bạn đang xem bài 38/ - 100 DE TIN HSG CO DAP AN