GIỚI THIỆU TRÌNH BIÊN
DỊCH FREE PASCAL
GV: Ngô Trung Tưởng
Trường THPT chuyên Lê Hồng Phong


I. Bộ nhớ rộng rãi
-

-

Free Pascal (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 thầy cô chú ý: 4GB=4×1024MB. Trong khi đó máy
tính ở phòng máy chúng ta thường dùng có chừng 512M RAM. (Turbo
Pascal cho phép khai báo biến 64 KB)
FP là môi trường lập trình chạy trên nền các HĐH 32 bit (Windows,
Linux, OS/2… và cả DOS nữa nhưng đó là phiên bản DOS 32 bit mở
rộng).
FP tương thích hoàn toàn với TP. Đây cũng là một điều thú vị. 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.


II. Kiểu dữ liệu

- Tất cả các kiểu dữ liệu có trong TP đều có trong
FP. Ngoài ra FP còn có thêm một số kiểu dữ liệu

mới
a. Kiểu số nguyên lớn
- Với lợi thế 32 bit (gấp đôi TP), FP cung cấp kiểu số
nguyên 64 bit. Với Int64 các bạn có thể tìm được
các số nguyên tố 18 chữ số (cỡ tỉ tỉ) hay tính được
giai thừa của 20.
- Hai kiểu số nguyên lớn là int64 và qword:
+ int64 kích thước 8 byte, có giá trị từ: -2 63 … 263 -1
+ qword kích thước 8 byte, có giá trị từ: 0 … 264-1
263 =
9223372036854775808
264 =


II. Kiểu dữ liệu
b. Kiểu xâu lớn:
- Khi lập trình, chúng ta rất nhiều lần gặp vấn đề với các
xâu tối đa 255 kí tự của TP (chẳng hạn bài toán xâu đối
xứng, bài toán đếm từ…). Ta có thể giải quyết vấn đề
bằng mảng kí tự (array of char) nhưng khi đó ta lại không
thể dùng các phép toán trên xâu rất mạnh của Pascal.
Không chỉ có cải tiến về kiểu nguyên, kiểu string trong FP
cũng rất tuyệt vời. String trong FP không còn hạn chế 255
kí tự của TP nữa mà có kích thước tối đa là 2.. tỉ kí tự.
Bây giờ bạn có thể viết chương trình giải bài xâu đối
xứng, xâu con chung với kiểu string của trên FP và hạn
chế n cỡ 1000 một cách rất dễ dàng.
- Tên kiểu xâu lớn là: ansistring



III. Viết hàm thuận lợi
- FP có rất nhiều cải tiến trong cách viết các hàm. Để so
sánh, chúng ta xem ví dụ hàm tính giai thừa của số n.
Trong Turbo Pascal

Trong Free Pascal

function gt(n:integer):integer;
var
i,tg: integer;
begin
tg:=1;
for i:=1 to n do tg:=tg*i;
gt:=tg;
end;

function gt(n: integer): int64;
var
i: integer;
begin
gt := 1;
for i := 1 to n do gt := gt * i;
end;

trong TP với tên hàm ta chỉ được sử dụng
duy nhất lệnh gán trị. Nếu đưa tên hàm
vào biểu thức thì sẽ thực hiện lời gọi hàm
(đệ qui)

FP cho phép sử dụng tên hàm như một

biến. Khi đó tên hàm có thể xuất hiện ở
trong các biểu thức tính toán ngay trong
thân hàm mà không tạo ra lời gọi đệ quy


III. Viết hàm thuận lợi
- Vậy khi ta muốn gọi đệ quy thì sao? Thì chỉ việc thêm
cặp dấu () và truyền tham số cần thiết. FP sẽ biết ta
muốn gọi đệ quy khi ta có thêm cặp (). Hàm giai thừa
viết kiểu đệ quy như sau:
function Gt(n: integer): int64;
begin
if n=0 then exit(1)
else exit(n*gt(n-1));
end;

- Trong cách viết này ta còn thấy một điều tiện lợi của
FP: dùng lệnh exit để trả lại kết quả cho hàm. Bạn sẽ
thấy sự tiện lợi của cách viết này khi viết các hàm
dạng “phát hiện được phần tử đầu tiên rồi thoát”.


III. Viết hàm thuận lợi
- Ví dụ cách viết hàm trong TP và FP cho bài toán tìm
vị trí đầu tiên x trong mảng a có n phần tử
Trong Turbo Pascal
function Find(x: integer): integer;
Var
i : integer;
begin

for i := 1 to n do
if a[i] = x then begin
Find := i;
exit;
end;
Find := 0;
end;

Trong Free Pascal
function Find(x: integer): integer;
Var
i : integer;
begin
for i := 1 to n do
if a[i]=x then exit(i);
exit(0);
end;


IV. Tính thời gian thực hiện chương trình giữa TP và FP
Trong TP chúng ta dùng từ khoá absolute để xác
định một vị trí cố định trong bộ nhớ. Khai báo
đó gọi là địa chỉ tuyệt đối. Chẳng hạn để đo thời
gian chạy chương trình, người ta khai báo biến
time kiểu longint tại địa chỉ 0:$46C, bởi vì vị trí
đó là nơi máy tính lưu bộ đếm của đồng hồ. Tần
số cập nhật của nó là 18.2 lần/giây

FP chạy trong môi trường 32 bit, không có khái
niệm địa chỉ tuyệt đối. Để đo thời gian chạy

chương trình ta sử dụng hàm DecodeDateTime có
sẵn trong thư viện DateUtils và thêm thư viện
SysUtils chứa mã thời gian.

VAR
time : LongInt absolute 0:$46C;
start, i, n : LongInt;
BEGIN
start := time;
for i := 1 to 100000000 do n := i;
write(’Runned in: ‘,(time-start)/18.2:0:3);
readln;
END.

USES sysutils,dateutils;
VAR s,ss,i,n:longint;
y,mon,d,h,m,s1,s2,ss1,ss2:word;
BEGIN
decodeDateTime(now,y,mon,d,h,m,s1,ss1);
for i := 1 to 1000000000 do n := i;
decodeDateTime(now,y,mon,d,h,m,s2,ss2);
ss:=ss2-ss1;
if ss<0then begin ss:=ss+1000;s1:=s1+1;end;
s:=s2-s1;
if s<0 then s:=s+60;
writeln('Runned in: ',s,':',ss);
readln;
END.



Một số định hướng trong dạy HSG
môn tin học khi sử dụng FP
1.Bài thi chấm bằng test, có so sánh thời gian chạy
chương trình cho mỗi test (thông thường không quá 1s
cho mỗi test)
- Chương trình phải đưa ra được kết quả đúng
- Tìm ra kết quả đúng với thời gian nhanh nhất có
thể (đây là tiêu chí phân loại học sinh)
2. FP sử dụng bộ nhớ rộng rãi, không quan tâm việc tiết
kiệm bộ nhớ. Nên tập trung nhiều vào việc cải tiến các
giải thuật sao cho tối ưu.
3. Các bài toán trong tin học hiện nay thường giải quyết
bằng rất nhiều lớp giải thuật khác nhau. Nên ta biết
nhiều thuật toán tối ưu giúp tìm ra kết quả tốt nhất.


Giới thiệu 2 thuật toán tối ưu và rất
hay gặp trong các bài thi tin học
1.

Thuật toán sắp xếp Quicksort

2.

Thuật toán tìm kiếm nhị phân.


Một số bài tập
Bài tập 1:


Cho số nguyên dương n và dãy số nguyên A: a 1, a2, …, an. (|ai|<=109)
Yêu cầu: đếm số lượng dãy con liến tiếp trong dãy A sao cho tổng các
số trong dãy con này bằng 0.
Ví dụ: n=5 và dãy A=(5, 6, -13, 2, 11)
Trong dãy A có 2 dãy con thỏa mãn yêu cầu là (5, 6, -13, 2) và (-13, 2,
11).

Phân loại bài làm học sinh cho bài tập 1
- 30% số điểm với n<=102
- 60% số điểm với n<=104
- 100% số điểm ứng với n<=106


Phân tích từng lớp giải thuật:
- C1: làm được 30% số điểm rất đơn giản là duyệt mọi dãy con
liên tiếp
kq:=0;
for i:= 1 to n do
for j:= i to n do
begin
s:=0;
for k:=i to j do
s:=s+a[k];
if s=0 then kq:=kq+1;
end;


C2: Cải tiến cách 1, để tính tổng các số từ i đến j ta không cần dùng đến vòng lặp để tính. Sử
dụng mảng tính trước: s[i]: là tổng các số từ 1 đến i.


s[0]:=0;
for i:=1 to n do s[i]:=s[i-1]+a[i];
kq:=0;
for i:= 1 to n do
for j:= i to n do
if s[j]-s[i-1]=0 then kq:=kq+1;


C3: cải tiến cách 2, ta có nhận xét sau:
Ta có s[j]-s[i-1]=0 => s[j]=s[i-1]. Như vậy nếu s[j]=s[i-1] thì tức là
tổng các số từ i đến j trong dãy A bằng 0.
Từ nhận xét trên ta có thuật toán cách 3 được 100% số điểm như
sau:
+ sắp xếp mảng s theo thứ tự tăng (hoặc giảm) dần
2
+ Mỗi phần tử s[j] gọi x[i] là tần số xuất hiện của
nó trong mảng S.

∑C

x[ i ]

⇒Kết quả bài toán là kq=
Một số chú ý: do |ai|<=109 nên mảng s để không bị
tràn số ta khai báo kiểu int64 và kq cũng vậy.
Với n=106 thì c3 chạy 0.266s, c2 chạy cỡ 133000s,
c1 …


Bài tập 2

ĐÓNG GÓI ĐƯỜNG
An là nhân viên giao hàng ở nhà máy đường. Nhiệm vụ của An lần này là phải giao đúng n kg đường cho
một xí nghiệp bánh kẹo. Ở nhà máy, đường được đóng gói trong 2 loại túi: túi đựng được 3 kg và túi 5 kg,
số lượng đường trong mỗi túi phải được đóng đúng với sức chứa của nó, không thừa và không thiếu.
Ví dụ, để giao 18 kg đường An có thể mang 6 túi loại 3 kg hoặc 3 túi loại 5 kg và 1 túi loại 3 kg. An luôn luôn
muốn chọn phương án sao cho số túi cần mang là ít nhất.
Yêu cầu: Cho n. Hãy xác định số túi ít nhất cần mang. Nếu không có cách mang thì đưa ra số -1.
Dữ liệu: Vào từ tệp văn bản TUIDUONG.INP gồm một dòng chứa số nguyên n.
Kết quả: Đưa ra tệp văn bản TUIDUONG.OUT một số nguyên – kết quả xác định được.
Ví dụ:

TUIDUONG.INP
-

30% số điểm
18 ứng với n<=104
60% số điểm ứng với n<=108
100% số điểm ứng với n<=10 18

TUIDUONG.OUT
4


Phân tích giải thuật bài tập 2
C1: Thử tất cả các trường hợp bằng 2 vòng lặp đơn giản:
Gọi a là số lượng túi 3kg tối đa dùng để chứa n kg đường
=> a=n div 3
Gọi b là số lượng túi 5kg tối đa dùng để chứa n kg đường
=> b= n div 5
Duyệt tìm kết quả

Min:=10000;
For i:= 0 to a do
For j:=0 to b do
If (i*3+j*5=n) and (i+jMin:=i+j;
Kết quả tìm được là Min


Phân tích giải thuật bài tập 2
C2: Cải tiến cách 1, chỉ sử dụng một vòng lặp
Nếu i là số túi loại 3 kg thì ta dễ dàng tính được số túi
loại 5 kg là (n-i*3) div 5
Cải tiến như sau:
Min:=100000000;
For i:= 0 to a do
Begin
j:=(n-i*3) div 5;
If (i*3+j*5=n) and (i+jMin:=i+j;
End;


Phân tích giải thuật bài tập 2
C3: Nhận xét sau: để sử dụng số túi ít nhất thì ta phải
đóng với số túi 5Kg nhiều nhất có thể. Từ đó ta thấy
không cần sử dụng vòng lặp để làm.
a= n div 5;//số túi 5kg, b số túi 3Kg
Du= n mod 5;//Du chỉ nhận giá trị 0 đến 4
Dựa vào Du ta tính số túi còn lại
-Du = 0 thì b=0;

-Du = 1 thì bớt a đi 1 và b=2
-Du = 2 thì bớt a đi 2 và b=4
-Du = 3 thì a không thay đổi, b=1
-Du = 4 thì a bớt đi 1 và b = 3

Chú ý: Có một số trường hợp vô nghiêm khi n bé.


Bài tập 3

HÀNG CÂY
Trong khu vườn, người ta trồng một hàng cây chạy dài gồm có N cây, mỗi cây có độ cao là a 1, a2,…
a N.
Người ta cần lấy M mét gỗ bằng cách đặt cưa máy sao cho lưỡi cưa ở độ cao H (mét) để cưa tất cả
các cây có độ cao lớn hơn H (dĩ nhiên những cây có độ cao không lớn hơn H thì không bị cưa).
Ví dụ: Nếu hàng cây có các cây với độ cao tương ứng là 20; 15; 10 và 18 mét, cần lấy 7 mét gỗ.
Lưỡi cưa đặt tại độ cao hợp lí là 15 mét thì độ cao của các cây còn lại sau khi bị cưa tương ứng
là 15; 15; 10 và 15 mét. Tổng số mét gỗ lấy được là 8 mét (dư 1 mét).
Yêu cầu: Hãy tìm vị trí đặt lưỡi cưa hợp lí (số nguyên H lớn nhất) sao cho lấy được M mét gỗ và số
mét gỗ dư ra là ít nhất.
Dữ liệu: Vào từ tệp văn bản WOOD.INP
Dòng thứ nhất chứa 2 số nguyên dương N và M (1≤N≤10 6; 1≤M≤2x109) cách nhau một dấu cách.
Dòng thứ hai chứa N số nguyên dương ai là độ cao của mỗi cây trong hàng (1≤a i≤109; i=1…N), mỗi
số cách nhau ít nhất một dấu cách.
Kết quả: Đưa ra tệp WOOD.OUT là một số nguyên cho biết giá trị cần tìm.
Ví dụ:
WOOD.INP
47
20 15 10 18
WOOD.OUT

15


Tìm cách chia các TH để phân loại bài
làm học sinh


Xin chân thành cám
ơn các thầy cô!