M
mikelhpdatke
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Người viết: Thầy 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 aij 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 aij được chọn. Các bạn xem trong chương trình cài đặt cụ thể dưới đây trên TP:
Mã:
{$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;
function max(a,b : integer): integer;
begin
if a > b then max := a else max := b;
end;
begin
for i := 1 to n do begin
for j := 1 to m do
if a[i] = b[j] then
L[i,j] := L[i-1,j-1] + 1
else
L[i,j] := max(L[i-1,j],L[i,j-1]);
end;
end;
(*****************************************)
procedure xuly;
begin
qhd;
trace;
end;
(*****************************************)
procedure inkq;
var
f : text;
i : integer;
begin
assign(f, out);
rewrite(f);
writeln(f, z);
for i := 1 to n do
if d[i] = 1 then write(f,’ ’,a[i]);
close(f);
end;
(*****************************************)
begin
nhap;
xuly;
inkq;
end.Câu trả lời là: TP là môi trường lập trình 16 bit trên HĐH DOS do đó nó có nhiều hạn chế. Han chế thứ nhât là kích thước của biến và kiểu &l; 64KB, trong đó có biến mảng và kiểu mảng. Đó là do dùng số 16 bit thì chỉ có thể chỉ số hoá được 216 = 64K giá trị thôi. Khi ta khai báo max = 1000 thì mảng L của ta có kích thước 1000x1000x2 (2 là kích thước kiểu integer)=2.106>>64K nên TP báo lỗi "structure too large" (kiểu cấu trúc quá lớn) là đúng rồi.
Vậy bây giờ thay vì khai báo mảng L là mảng 2 chiều, ta sẽ khai báo L thành rất nhiều mảng nhỏ hơn. Bạn cứ thử thế mà xem. Nếu TP không báo lỗi "structure too large" thì cũng báo lỗi là "too many varibles". Đó là do hạn chế thứ 2 của TP: tổng kích thước các biến toàn cục (global) cũng ≤ 64KB . Bạn có chia L thành bao nhiêu mảng con thì TP vẫn bắt tổng kích thước của chúng ≤ 64KB.
Vẫn còn giải pháp nữa: thay vì dùng mảng tĩnh thì dùng mảng động. Khai báo L là mảng 1000 con trỏ, mỗi con trỏ trỏ đến một mảng 1000 phần tử. (L:Array[1...max] of ^mang1). May quá, TP không báo lỗi khi dịch. Nhưng khi chạy thì ôi thôi, lỗi "Heap overflow" (tràn heap). Nguyên nhân là hạn chế của DOS: toàn bộ bộ nhớ DOS có thể sử dụng ≤ 640 KB. Mà các chương trình hệ thống và IDE của TP cũng chiếm mất hơn 300KB rồi. Tức là chương trình của bạn dù có tận dụng hết bộ nhó còn lại cũng chỉ được 300KB nữa thôi. (Khi bạn nhấn F9 để dịch, TP báo xxxKB free memory, đó chính là phần heap tối đa hệ thống có thể cấp phát cho các biến động đó).
Vẫn còn nhiều giải pháp có thể giải quyết: dùng 2 mảng một chiều tính lẫn nhau và đánh dấu lần vết bằng bit; ghi ra file; dùng mảng răng lược… Nhưng dù sao thì cũng chỉ là giải pháp tình thế, hơn nữa lại rất phức tạp. Giải pháp tốt nhất là dùng một môi trường lập trình mạnh hơn. Và IOI đã chọn FP.
Tôi đem chương trình trên với khai báo max =1000 chạy trên FP và mọi chuyện đều ổn, chẳng có lỗi nào xảy ra hết. Đối với FP, bộ nhớ không bị hạn chế bởi con số 64KB nữa (free mà).
Điều đó có được là nhờ những đặc tính tuyệt vời của FP:
a. FP là môi trường lập trình 32 bit. Dùng một số 32 bit thì có thể chỉ số hoá được 232 = 4G giá trị, vậy nên biến trong FP có thể có kích thước 4GB. Các bạn chú ý: 4GB=4x1024MB. Trong khi đó máy tính chúng ta thường dùng thường có chừng 128MB RAM. Mảng L kích thước ≤ 2MB thì nhằm nhò gì.
b. FP là môi trường lập trình chạy trên nền các HĐH 32 bit (Windows, Linux, BeOS, OS/2… và cả DOS nữa. Nhưng đó là phiên bản DOS 32 bit mở rộng). Đây cũng là điều quan trọng. Vì nếu cho FP chạy trên DOS 16 bit (nếu có chạy được), thì với bộ nhớ chật hẹp 640KB, FP cũng phải bó tay không phát huy được tài năng. Ngược lại do TP là 16 bit, nên có cho chạy trên Windows 32 bit, thì cũng chỉ phát huy được tài năng đến mức của 16 bit mà thôi. Chạy trên môi trường 32 bit, ngoài RAM (đã rất nhiều), HĐH còn có có chế bộ nhớ ảo (virtual memory) sử dụng một phần HĐ làm bộ nhớ tạm nên FP có thể cung cấp cho bạn dung lượng nhớ có thể nói là thoải mái (free mà).
c. FP là tương thích hoàn toàn với TP. Đây cũng là một điều thú vị. Chương trình ở phàn trên tôi viết trong TP, đem sang FP vẫn chạy ngon lành, chẳng phải sửa đổi gì hết (thực ra thì có sửa giá trị max từ 100 thành 1000). IDE của FP thì giống hệt TP (tất nhiên có nhiều chức năng tiên tiến hơn, nhưng những gì bạn làm được với TP đều làm được trên FP).
Tôi nghĩ vậy là quá đủ để chúng ta thay thế TP bằng FP. Nếu bạn còn băn khoăn, hãy đợi các bài viết tiếp theo để tìm hiểu tiếp về những điều kì diệu mà FP có còn TP thì không. Còn nếu bạn háo hức muốn dùng thử, hãy làm theo chỉ dẫn cài đặt dưới đây.
2. Cài đặt và sử dụng FP
a. Tải bộ cài đặt
FP có rất nhiều phiên bản, cả các phiên bản đã sử dụng chính thức và phiên bản còn đang phát triển. Theo tôi thì các bạn nên sử dụng các phiên bản chính thức vì chúng ổn định hơn. (Tôi hiện đang dùng phiên bản 1.0.6).
Để cài đặt bạn vào website của ISM (http://www.thnt.com.vn), hoặc nếu thích có thể đến thẳng website của FP (http://www.freepascal.org), vào mục download và tải file zip chứa bộ cài. Chú ý là có nhiều phiên bản của FP cho các hệ điều hành khác nhau nên bạn phải chú ý:
- Tải bộ cài các phiên bản chính thức. Các phiên bản chính thức có chữ số cuối cùng là số chẵn (như bản của tôi là 1.0.6, có thể bây giờ có nhiều bản mới hơn rồi).
- Tải bộ cài cho HĐH Windows và DOS. Bạn có thể nhận biết điều này qua tên file zip. Như file của tôi là dosw32106full.zip, có nghĩa là bộ cài đầy đủ cho HĐH Windows và DOS, phiên bản 1.0.6.
b. Unzip và Install
Sau khi đã tải được bộ cài (tất cả ở trong một file zip), bạn unzip file đó ra một folder rồi chạy file Install.exe. Giao diện cài đặt hiện ra, yêu cầu bạn lựa chọn thư mục cài đặt cho FP (mặc định là C
P). Và tiếp theo là một bảng lựa chọn các cấu hình cài đặt. Theo tôi thì bạn nên chọn các cấu hình mặc định, và đơn giản là nhấn Enter để bộ cài tự làm việc của mình. c. Chạy và cấu hình IDE
Sau khi cài xong, toàn bộ IDE, chương trình dịch, tài liệu, ví dụ,… của FP được copy vào thư mục bạn đã chọn khi cài đặt (mặc định là C
P). Có 2 bản cho cả Windows và DOS (32bit). Nếu chỉ dùng FP thay thế TP trong học tập thì theo tôi bạn nên sử dụng bản cho DOS. Vì qua sử dụng tôi thấy IDE của FP trên DOS hoạt động ổn định hơn IDE của FP trên Windows. Để sử dụng IDE của FP trên DOS, bạn vào thư mục con bingo32v2 và chạy file fp.exe. (Có thể sẽ cần nhấn Alt-Enter để chương trình chạy toàn màn hình full screen. Bạn sẽ thấy ngạc nhiên, hoặc cũng chẳng ngạc nhiên lắm, vì giao diện IDE của FP giống hệt TP. (Tôi thì thấy ân tượng hơn, nhất là hình ảnh nền).
Đến đây thì mọi chuyện như trên TP thôi. Nhưng để thuận tiện hơn trong sử dụng, bạn nên thiết lập một số thông số cấu hình như sau:
- Vào menu CompileTarget: chọn DOS (để nhấn Ctrl-F9 là chương trình của bạn có thể chạy ngay lập tức như trong TP. Vì compiler ta dùng cũng đang chạy trên DOS mà. Nhưng đây là DOS 32 bit đấy, không hạn chế như DOS 16 bit đâu).
- Vào menu OptionsMode: chọn Normal (để FP sẽ hỗ trợ chúng ta debug dễ chịu nhất).
- Vào menu OptionsCompiler:
ở tab Syntax các bạn chỉ chọn các mục:
+ TP/BP compatibily: để tương thích với TP (sau này khi quen với FP rồi thì không cần nữa, còn bây giờ thì chọn chức năng này cho dễ sử dụng).
+ Stop after first error: bình thường FP dịch sẽ thông báo một loạt lỗi (giống C, Delphi…), nhưng ta quen với việc thông báo lỗi đầu tiên gặp của TP nên chọn mục này cho thân thiện. Sau này có thể không cần nữa.
+ C-like operators: đây là một điều thú vị của FP (các bạn hãy đón đọc trong kì sau nhé).
ở tab Code generaion các bạn chọn
+ Toàn bộ các mục phần Run-time checks: cho an toàn các bạn ạ, tránh trường hợp ta lập trình sai như: truy cập ngoài mảng, tính toán tràn số mà máy vẫn không thông báo gì.
+ Target processor: chọn PPro/PII. Hầu hết máy của chúng ta là máy Pen III, Pen IV, thế thì nên để FP tận dụng hết tiềm năng của chúng để chương trình của chúng ta chạy hiệu quả hơn.
