Free Pascal: Yes, Turbo Pascal: No!

Free Pascal: Yes, Turbo Pascal: No!

Nguyễn Thanh Tùng

Các bạn đã bao giờ nghe đến cái tên Free Pascal (FP) chưa? Nếu chưa thì tôi xin giới

thiệu một cách ngắn gọn: FP là một môi trường lập trình rất tuyệt vời và mạnh mẽ, hoàn

toàn tương thích Turbo Pascal (TP) và điều đáng chú ý nhất là FP là được chọn làm môi

trường chuẩn thay thế TP trong các kì thi IOI. Vì sao vậy? Chúng ta hãy cùng tìm hiểu

những điều thú vị của FP mà TP không có để thấy câu trả lời nhé!!!

1. Bộ nhớ rộng rãi

Trong chúng ta, chắc có rất nhiều người biết về bài toán tìm dãy con chung dài nhất. Bài

toán phát biểu ngắn gọn như sau:

Cho 2 dãy A và B. Dãy A có các phần tử là a1, a2,…an, dãy B có các phần tử là là b1, b2,

…bn. Hãy tìm dãy C là dãy con của cả A và B và có nhiều phần tử nhất.

Chẳng hạn, nếu dãy A là 5 3 2 1 4 và B là 3 2 5 4 1 thì C là dãy 3 2 4.

Đây là một bài toán quy hoạch động kinh điển và có công thức quy hoạch động được thiết

lập như sau:

Gọi L(i,j) là độ dài dãy con chung lớn nhất của dãy Ăi) gồm các phần tử a1, a2,…ai và dãy

B(j) có các phần tử là là b1, b2,…bj.

Thế thì:

L(0,j)=L(i,0)=0.

Nếu ai</SUB>=Bj thì L(i,j)=L(i-1,j-1)+1.

Nếu ai ≠bj thì L(i,j)= max(L(i-1,j), L(i,j-1)).

Trường hợp 2 và 3 áp dụng với tất cả các chỉ số i từ 1 đến n và j từ 1 đến m. Nếu bạn chưa

tin vào tính đúng đắn của công thức thì tôi xin giải thích như sau:

Trường hợp 1 hiển nhiên.

Với công thức ở trường hợp 2 và 3 ta thấy: nếu ai =bj thì ta phải chọn ngay cặp phần tử

chung đó, các phần tử còn lại của 2 dãy là a1, a2,…a i−1 và b1, b2,…b j −1 có dãy con

chung lớn nhất gồm độ dài L(i-1,j-1), do đó L(i,j)=L(i-1,j-1) + 1. (Tư tưởng quy hoạch

động thể hiện ở chỗ L(i,j) đạt max thì L(i-1,j-1) cũng phải đạt max).

Còn nếu ai ≠bj thì ta có 2 lựa chọn: hoặc không xét phần tử ai và so dãy là a1, a2,…ai-1

với dãy b1, b2,…bj để được dãy con chung dài nhất L(i-1,j) phần tử; hoặc không xét phần

tử bj và so dãy là a1, a2,…ai với dãy b1, b2,…bj-1 để được dãy con chung dài nhất L(i,j-1)

phần tử. (Chú ý định nghĩa của L(i-1,j) và L(i,j-1)). Vì có 2 lựa chọn nên ta chọn hướng tốt

hơn, do đó L(i,j)=max(L(i-1,j) , L(i,j-1)).

Các bạn có thể băn khoăn là ở trường hợp 2 cũng có thể lựa chọn cả 2 tình huống trên chứ?

Thực chất không cần như vậy, vì dễ thấy L(i,j)≤ min(i,j) do đó L(i-1,j-1) + 1 chắc chắn

không nhỏ hơn cả L(i-1,j) và L(i,j-1).

Sau khi tính được xong toàn bộ L(i,j) thì ta sẽ được: dãy C có L(n,m) phần tử, để xác định

đó là các phần tử nào thì ta lần vết trên L theo 3 trường hợp trên để tìm các cặp

ai</SUB>=Bj được chọn. Các bạn xem trong chương trình cài đặt cụ thể dưới đây trên TP:

{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+}

program daycon;

const

inp = ’daycon.in0’;

out = ’daycon.out’;

max = 100;

type

mang1 = array[0..max] of integer;

mang2 = array[0..max] of mang1;

var

n,m,z : integer;

a,b,d : mang1;

L : mang2;

(*****************************************)

procedure nhap;

var

i : integer;

f : text;

begin

assign(f, inp);

reset(f);

readln(f, n, m);

for i := 1 to n do read(f,a[i]);

readln(f);

for i := 1 to m do read(f,b[i]);

close(f);

end;

(*****************************************)

procedure trace;

var

i,j : integer;

begin

i := n; j := m; z := L[n,m];

repeat

if L[i,j] = L[i-1,j-1] + 1 then begin

d[i] := 1;

i := i - 1; j := j - 1;

end

else

if L[i,j] = L[i-1,j] then

i := i - 1

else j := j - 1;

until (i=0) or (j=0)

end;

(*****************************************)

procedure qhd;

var

i,j : integer;