Tin học Cấu trúc trong pascal

M

mituot_palapala

2, free pascal có nhiều tính năng dễ sd và hiệu quả hơn Ngoài tính năng thích hợp với mọi hệ điều hành thì Free Pascal cho phép sử dụng bộ nhớ lên 64 bit . Cụ thể trong Free Pascal sử dụng các kiểu mở rông như Single, Double , Extended mà không cần đổi tham số Option như Turbo Pascal. Dễ thấy nhất là kiểu Int64 là kiểu số nguyên
đến 64 bit mà trong Turbo không có. Nhờ đó khi xử lý các số nguyên lớn ta không cần chuyển
qua dạng chuỗi hoặc đa thức như trong TP . Hiện nay chưa có sách nào nói về Free Pascal
nên mình cũng không biết gì nhiều hơn.

:)>-
 
A

auauau97

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.
Thuật toán có thời gian thực thi cỡ O(n2). Với n,m =100 thì chương trình chạy trong chớp mắt. Vậy thì tại sao không thử giải với n=1000 (ai mà không muốn chương trình của mình mạnh hơn). Vậy ta sửa hằng số max trong chương trình thành 1000. Và, TP báo lỗi "structure too large"!!! Tại sao lại thế???
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.

2.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:pP). 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.
- Vào menu OptionsEnviroimentEditor: đặt các thông số soạn thảo mà bạn thích. Tôi thì thường chỉ đặt các mục sau:
Các mục mà TP mặc định (và FP cũng thế):
+ Insert mode: chế độ gõ chèn.
+ Auto indent mode: đặt lề tự động.
+ Backspace unindent.
+ Tab size: 4. Indent size: 4.
Những thông số này giúp chương trình dễ đọc hơn (có cấu trúc, thẳng lề, các đầu dòng thò thụt đều đặn theo khoảng cách 4 kí tự).
Syntax highlight: hiện sáng từ khoá (trong TP cũng có).
Persirtent block: khối sau khi đánh dấu sẽ hiển thị cho đến khi dùng lệnh ẩn khối.
Auto closing brackets: tự động thêm kí tự đóng ngoặc. Đây là điều đặc sắc không có trong TP. Bình thuờng trong TP bạn gõ các kí tự mở ngoặc như (, [, { thì phải tự thêm kí tự đóng ngoặc cho đúng. Nếu không chú ý thì rất dễ lẫn. Còn trong FP nếu đặt chức năng này thì khi ta gõ kí tự mở ngoặc, FP cũng thêm luôn kí tự đóng ngoặc, do đó chúng ta không sợ các lầm lẫn thừa thiếu đóng mở ngoặc nữa.

bạn vào đây để xem thêm nhá:
(nguồn:http://vnoi.info)
Mã: 
http://vnoi.info/index.php?option=com_content&task=view&id=161&Itemid=83
 
You must log in or register to reply here.
Top Bottom