PHÒNG GIÁO DỤC TÂN THÀNH
TRƯỜNG THCS TÓC TIÊN

Tài liệu
BỒI DƯỠNG HỌC SINH GIỎI
MÔN TIN HỌC (THCS)
(Tài liệu lưu hành nội bộ)
Người biên soạn : Lê Đắc Ước
ĐT : 0907090779 – E-mail :
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 2
Tháng 2 năm 2010
Phần 1 : LÝ THUYẾT
Chương I : MỘT SỐ VẤN ĐỀ TOÁN HỌC
I. HỆ ĐẾM :
1. Hệ đếm thập phân (Decimal): Gồm 10 chữ số biểu diễn (0,1,2,3,4,5, 6,7,8,9)
Dạng tổng quát : a
1
a
2…
a
n
= a
1
.10
n-1
+ a
2
.10
n-2
+… +a
n

0
VD : 1010
2
= 1.2
3
+ 0.2
2
+ 1.2
1
+ 0.2
0
= 10
(Lưu ý : Đây chính là cách quy đổi từ hệ nhị phân sang hệ thập phân)
b)
Cách quy đổi từ thập phân sang nhị phân :
- Bước 1 : Chia liên tiếp số cần đổi cho 2 đến khi thương bằng 0.
- Bước 2 : Viết ngược lại số dư, ta được số mới trong hệ nhị phân.
VD : Đổi số 6 từ hệ thập phân sang hệ nhị phân, ta làm như sau :
6 2
0
3 2
1
1 2
1
0
Kết quả : 6 = 110
2
3. Hệ đếm thập lục phân (Hexa) :
Gồm 16 chữ số biểu diễn (0,1,2,3,4,5, 6,7,8,9,A,B,C,D,E,F)
a)

- Bước 1 : Chia liên tiếp số cần đổi cho 16 đến khi thương bằng 0.
- Bước 2 : Viết ngược lại số dư, ta được số mới trong hệ Hexa.
(Lưu ý : Nếu số dư lớn hơn 9 ta quy đổi thành A, B, C, D, E, F)
 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Giáo dục có rễ đắng mà trái
ngọt.
Aristote (384-322 T.C.N)
Ngừng chia
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 3
c)
Cách quy đổi nhanh từ hệ Hexa sang hệ nhị phân và ngược lại :
Nhận xét : Số lớn nhất trong hệ Hexa có thể đổi ra 4 chữ số trong hệ nhị
phân (1111=F). Do đó muốn đổi từ hệ Hexa ra hệ nhị phân, ta đổi từng con số
Haxa ra nhóm 4 số nhị phân (nếu chưa đủ 4 chữ số nhị phân ta phải thêm các chữ
số 0 vào phía trước). Ngược lại, muốn đổi từ hệ nhị phân sang Hexa, ta nhóm từ
phải sang trái, mỗi nhóm 4 số rồi quy đổi từng nhóm sang hệ Hexa.
II. TẬP HỢP :
1. Phép hợp (Union) : A  B = {x | x ∈ A hoặc x ∈ B}
2. Phép giao (Intersection) : A  B = {x | x ∈ A và x ∈ B}
(Lưu ý : Khi A  B = φ ta nói rằng A và B là hai tập phân biệt)
3. Phép trừ (Difference) : A \ B = {x | x ∈ A và x ∉ B}
4. Phép nhân (Multiplication) : A × B = {(a,b) | a ∈ A và b ∈ B}
5. Phép phân hoạch (Partition) :
Cho X là một tập hợp (X ≠ φ).
Tập X được chia ra thành các tập con A
i
(A
i
≠ φ), họ các tập con A
i

Nếu a = 0 thì (1) ⇔ b = 0. Khi đó : b ≠ 0 thì phương trình vô nghiệm;
b = 0 thì PT có vô số nghiệm.
Nếu a ≠ 0 thì phương trình có nghiệm là x = -
a
b
2. Phương trình bậc hai : ax
2
+ bx + c = 0 (a ≠ 0). Ta tính ∆ = b
2
– 4ac
Nếu ∆ < 0 thì phương trình vô nghiệm.
Nếu ∆ = 0 thì phương trình có 1 nghiệm x = -
a
b
2
Nếu ∆ > 0 thì phương trình có 2 nghiệm phân biệt : x
1
=
2
b
a
− + ∆
;x
2
=
2
b
a
− − ∆
3. Bất phương trình bậc nhất : ax + b > 0 (2)

D cb' - c'b
c' b'
x
 
 
 
= =

a c
D ac' - a'c
a' c'
y
 
 
 
= =
Nếu D = 0 thì : + Nếu D
x
≠ 0 hoặc D
y
≠ 0 thì hệ PT vô nghiệm;
+ Nếu D
x
= D
y
= 0 thì hệ PT có vô số nghiệm.
Nếu D ≠ 0 thì hệ PT có nghiệm duy nhất :
D
D
x

VIII. HÌNH HỌC :
1. Định lí Py-ta-go : ∆ ABC vuông tại A ⇒ BC
2
= AB
2
+ AC
2
.
2. Hệ thức lượng trong ∆ vuông : b
2
=ab’(c
2
=ac’); h
2
=b’c’;
2 2 2
1 1 1
h b c
= +
 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 5
Chương II : MỘT SỐ VẤN ĐỀ CƠ BẢN TRONG PASCAL
I. GIẢI THUẬT :
1. Khái niệm :
- Giải thuật (còn gọi là thuật toán) là một tập hữu hạn các thao tác (các công
việc, các phép toán…) có thể đặt tên được và chúng được thực hiện theo một
trình tự thích hợp đối với một số đối tượng nào đó để đạt được điều mong muốn.
2. Biểu diễn giải thuật :
Thông thường, người ta sử dụng một trong 4 cách sau để biểu diễn giải thuật :
- Liệt kê : Là hình thức liệt kê từng bước bằng ngôn ngữ tự nhiên.

Từ khai báo Phạm vi biểu diễn Kích thước (Byte)
BYTE 0 255 1
SHORTINT -128 +128 1
INTEGER -32768 32767 2
WORD 0 65535 2
LONGINT -2147483648 2147483647 4
 Mở rộng kiểu số thực :
Từ khai báo Phạm vi biểu diễn Chữ số có nghĩa Kích thước (Byte)
REAL 2.9E-39 1.7E+38 11-12 6
SINGLE 1.5E- 45 3.4E+38 7-8 4
DOUBLE 5.0E-324 1.7E+308 15-16 8
EXTENDED 3.4E- 4951 1.1E+4932 19-20 10
(Thông thường chỉ dùng kiểu Real. Muốn sử dụng các kiểu thực
khác thì phải dùng hướng dẫn dịch {N+} ở đầu chương trình)
V. CÁC THỦ TỤC CƠ BẢN CỦA TP :
1. Thủ tục nhập : READ
- Read (DS biến); hoặc Readln (DS biến); {Nhập vào biến giá trị từ bàn phím}
- Read (F, DS biến); hoặc Readln (F, DS biến); {Đọc từ tệp F vào DS biến}
- Readln; {Chờ nhấn phím Enter}
Thủ tục nhập đặc biệt: Readkey;
{Cho kí tự khi gõ phím mà không cần nhấn Enter}
Hàm KeyPressed
cho giá trị True nếu bàn phím có kí tự gõ, ngược lại có giá trị False.
2. Thủ tục xuất : WRITE
- Write (DS dữ liệu xuất); hoặc Writeln (DS dữ liệu xuất); {Xuất ra màn hình}
- Write (n:d); hoặc Writeln (n:d); {Dành d vị trí để xuất biến nguyên}
- Write (x:d:d1); hoặc Writeln (x:d:d1);
{Dành d vị trí để xuất biến thực với d1 kí số thập phân}
- Write (F, DSDL xuất); hoặc Writeln (F, DSDL xuất);{Ghi dữ liệu vào tệp F}
- Write (LST, DSDL xuất); hoặc Writeln (LST, DSDL xuất);{Xuất ra máy in}

END;
(Lưu ý : CASE kết thúc bằng END; Trước ELSE của CASE được chấm phẩy )
3. Điều khiển lặp FOR…TO/ FOR…DOWNTO :
Dạng 1 : FOR <Biến đếm> := <Trị đầu> TO <Trị cuối> DO <Câu lệnh>;
Dạng 2 : FOR <Biến đếm> := <Trị đầu> DOWNTO <Trị cuối> DO <Câu lệnh>;
4. Điều khiển lặp REPEAT…UNTIL : Ngừng lặp khi <Điều kiện> ĐÚNG.
REPEAT
<Câu lệnh 1>;
<Câu lệnh 2>;
<Câu lệnh 3>;
…
<Câu lệnh n>;
UNTIL <Điều kiện>;
5. Điều khiển lặp WHILE…DO : Ngừng lặp khi <Điều kiện> SAI.
WHILE Điều kiện DO Câu lệnh;
(Sau DO chỉ có 1 câu lệnh, do đó muốn lặp nhiều phát biểu ta phải dùng phát biểu ghép)
6. Lệnh ghép : Ở những chỗ ta chỉ được sử dụng 1 câu lệnh, nhưng ta lại muốn
sử dụng nhiều hơn 1 câu lệnh thì phải sử dụng lệnh ghép. Lệnh ghép có dạng :
BEGIN
<Câu lệnh 1>;
<Câu lệnh 2>;
<Câu lệnh 3>;
…
<Câu lệnh n>;
END;
 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 8
VII. CÁCH ĐẶT TÊN TRONG PASCAL - TỪ KHÓA:
1. Cách đặt tên trong Pascal (chương trình, biến, hằng, nhãn, thủ tục, hàm… ) :
Tên có thể được đặt bằng một dãy bao gồm chữ cái, chữ số, dấu “_” (gạch

ORD (ch) : Cho thứ tự của kí tự ch trong bảng ASCII
(VD : ORD (‘A’)=65, ORD (‘a’)=97).
CHR (i) : Cho kí tự có thứ tự là i trong bảng ASCII
(VD : CHR (65) = ‘A’).
ODD (n) : Cho giá trị True nếu n là số lẻ.
SOUND(F) : tạo âm thanh tần số F tính theo Hz cho đến khi gặp lệnh OSOUND.
NOSOUND; : Ngừng thực hiện hàm SOUND.
DELAY (T) : tạo thời gian trể T tính theo đơn vị Mili giây (T là số nguyên).
READKEY; : Nhận một kí tự từ bàn phím không đưa ra màn hình và không cần
gõ phím Enter. (VD : Ch := Readkey;)
WHEREX : Cho giá trị cột hiện thời của con trỏ.
WHEREY : Cho giá trị dòng hiện thời của con trỏ.
LENGTH (Chuỗi) : Cho độ dài thật của chuỗi.
<Chuỗi>[k] : cho kí tự thứ k trong chuỗi. Đặc biệt : Chuỗi [0]=Length(chuỗi).
VD : For i:=1 to length(st) do
If ord(st[i]) >= 97 then st[i] := chr(ord(st)-32);
{Duyệt chuỗi st để đổi chuỗi st bất kỳ thành chuỗi gồm toàn chữ in hoa}
LENGTH (S,P,N) : xóa trong chuỗi S đi N ký tự kể từ vị trí P.
POS (S1,S) : Tìm kiếm chuỗi S1 trong chuỗi S. (Hàm cho giá trị là vị trí đầu tiên)
 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 9
Chương III : CHƯƠNG TRÌNH CON : THỦ TỤC VÀ HÀM
I. THỦ TỤC (PROCEDURE) VÀ HÀM (FUNCTION) :
1. Xét ví dụ sau đây : Chương trình tính tổ hợp chập k của n phần tử.
Program Tinh_To_Hop_Chap_K_Cua_N_Phan_Tu;
Uses Crt;
Var n,k: Byte; Tohop : Real;
Procedure Nhap; {Thu tuc nhap du lieu}
Begin
Clrscr;

Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 10
- Cách viết các chương trình con cũng gần giống như chương trình chính, cũng
có thể có các phần khai báo (biến, hằng,…), thân thủ tục cũng trong cặp từ khóa
Begin … End nhưng kết thúc bằng dấu chấm phẩy.
3. Sự khác nhau giữa thủ tục và hàm :
- Sự khác nhau cơ bản giũa thủ tục và hàm là ở chỗ : Hàm cho ta kết quả là một
giá trị thông qua tên của nó, còn thủ tục thì chỉ thực hiện một khối thao tác mà
không cho kết quả qua tên thủ tục.
II. TRUYỀN THAM SỐ CHO CHƯƠNG TRÌNH CON :
III. BIẾN TOÀN CỤC VÀ BIẾN ĐỊA PHƯƠNG :
IV. TÍNH ĐỆ QUY CỦA CHƯƠNG TRÌNH CON :
 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 11
Chương IV : KIỂU DỮ LIỆU CÓ CẤU TRÚC
I. KIỂU MẢNG :
1. Khai báo :
- Cách 1 : TYPE <Kiểu mảng> = ARRAY [Chỉ số đầu Chỉ số cuối] OF
<Kiểu phần tử>;
VAR <Biến mảng> : <Kiểu mảng>;
VD : TYPE mangnguyen = ARRAY [1 10] OF Integer;
VAR A,B,C : mangnguyen;
- Cách 2 : VAR <Biến mảng> : ARRAY [Kiểu chỉ dẫn] OF <Kiểu phần tử>;
VD : VAR A,B,C : ARRAY [1 10] OF Integer;
2. Truy nhập vào phần tử mảng :
<Tên mảng> [Chỉ số] {VD: Viết A[5] là truy nhập vào phần tử thứ 5 của mảng A;
3. Duyệt mảng :
Dùng lệnh FOR duyệt qua từng phần tử của mảng để thao tác với phần tử.
VD : For i:=1 to 10 do {Nhập dữ liệu vào mảng A}
Begin
Writeln (‘A[‘,i,’]=’);

Exit;
End;
p:=2;
f:= True;
While (p <= Sqrt(x)) and f do
If x mod p = 0 then
f := false
Else
p := p+1;
If f then
SNT:=True
Else
SNT:=False;
End;
2. Sàng số nguyên tố :
Procedure SSNT (n: Byte); {Thu tuc sang so nguyen to}
Var TapNT,Sang : Set of Byte;
p,i : Byte;
Begin
TapNT := []; {Tap chua so nguyen to. Khoi tao bang rong}
Sang := [2 n]; {Cai sang}
p := 2;
Repeat
While not(p in Sang) do p := p + 1;
TapNT := TapNT + [p];
i := p;
While i <= n do
Begin
Sang := Sang -[i];
i := i + p;

Function UCLN (a,b : Integer) : Integer; {Tim UCLN bang de quy}
Begin
If b=0 then
UCLN:=a
Else
UCLN:=UCLN(b,a mod b);
End;
Lưu ý : Tính BCNN(a,b) theo công thức : BCNN(a,b) = a*b div UCLN(a,b))
Function UCLN (a,b : Integer) : Integer; {Thu tuc tim UCLN bang de quy}
Begin
If b=0 then
UCLN:=a
Else
UCLN:=UCLN(b,a mod b);
End;
 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 14
4. Đổi từ cơ số thập phân sang cơ số khác :
…………
5. Đổi từ cơ số khác sang cơ thập phân :
…………
6. Tính lũy thừa X
n
:
…………
7. Tính giai thừa :
…………
II. GIẢI THUẬT XỬ LÝ CHUỖI :
1. Đổi chuỗi kí tự thường sang kí tự in hoa :
…………

Ví dụ : Lập chương trình xây dựng một dãy gồm N chữ số (N là số nguyên
nhập từ bàn phím) từ 3 chữ số cho trước 1, 2, 3 sao cho không có hai dãy con chữ
số liên tiếp nào giống nhau. Chẳng hạn, với N=10, ta có dãy 1213123132 là chấp
nhận được, còn dãy 1213 121312 là không chấp nhận được; với N=20, ta có dãy
12131231321231213123 là chấp nhận được, còn dãy 121312313 12131231312 là
không chấp nhận được.
Để giải quyết bài toán này, ta dùng một biến chuỗi S lưu trữ dãy đang xây
dựng. Ta từng bước kiểm tra xem trong chuỗi S có 2 chuỗi con liên tiếp nào
giống nhau hay không. Giả sử độ dài chuỗi S (đến thời điểm hiện tại đang kiểm
tra) là m=Length(S) thì 2 chuỗi con liên tiếp cần kiểm tra có độ dài không vượt
quá L=m div 2.
 Hàm Copy :
Cú pháp : Copy (S : String, P : Integer, N : Integer)
Ý nghĩa : Hàm cho giá trị là xâu ký tự con có N ký tự được lấy ra từ xâu
ký tự S bắt đầu từ vị trí thứ P.
Ta tăng L từ 1 đến m div 2 để tách các chuỗi con có 1, 2, 3, …, L ký tự từ
chuỗi S và so sánh bằng biểu thức :
Copy(S,m-2*L+1,L)<>Copy(S,m-L+1,L)
Nếu chuỗi S tốt (Good) thì ta cho kéo đỗ dài chuỗi S bằng thủ tục Extend,
nếu chuỗi S là không tốt (có 2 chuỗi con liên tiếp giống nhau) thì ta thay đổi
chuỗi S bằng thủ tục change. Chương trình hoàn chỉnh như sau :
Program Taobangkyhieu;
Uses Crt;
Var S:String;
N:Integer;
Good:Boolean;
Procedure Extend;
Begin
S:=S+'1';
End;

2. Phương pháp Vét cạn :
Phương pháp vét cạn là phương pháp duyệt qua tất cả mọi trường hợp
có thể xảy ra và chọn lựa xem trường hợp đang xét có thỏa mãn yêu cầu của
đề bài hay không.
Ví dụ : Lập chương trình tìm tất cả các số có 3 chữ số abc sao cho tổng các
lập phương của các chử số thì bằng chính số đó. Có nghĩa là : abc = a
3
+b
3
+c
3
.
Trong trường hợp này, ta sẽ cho máy tính quét hết các khả năng các số có
3 chữ số và thử. Đó chính là “Vét cạn”.
Cách 1 : ta dùng 3 vòng lặp
Program Vetcan1;
Uses Crt;
Var a,b,c:Integer;
Begin
Clrscr;
For a:=1 to 9 do
For b:=0 to 9 do
For c:=0 to 9 do
If a*a*a+b*b*b+c*c*c = 100*a+10*b+c then
Writeln(a,b,c);
Readln;
End.
Cách 2 : ta dùng 1 vòng lặp
Program Vetcan2;
 Lê Đắc Ước Tân Thành - ĐT: 0907090779

) = a
7
Trong đó a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
là số thực nhập từ bàn phím.
Bài 2 : Lập chương trình tìm cách điền 9 chữ số khác nhau 1, 2, 3, 4, 5, 6,
7, 8, 9 vào bảng vuông 3x3 sao cho a’b’c’=2a”b”c”=3abc (như hình vẽ dưới).
a b c
a’ b’ c’
a” b” c”
V. KỸ THUẬT DUYỆT ĐỆ QUY QUAY LUI (BACKTRACKING) :
Kỹ thuật quay lui (Backtracking) như tên gọi của nó, là một quá trình phân
tích đi xuống. Tại mỗi bước phân tích chúng ta chưa giải quyết được vấn đề do
còn thiếu cứ liệu nên cứ phải phân tích cho tới các điểm dừng, nơi chúng ta xác
định được lời giải của chúng hoặc là xác định được là không thể (hoặc không
nên) tiếp tục theo hướng này. Từ các điểm dừng này chúng ta quay ngược trở lại
theo con đường mà chúng ta đã đi qua để giải quyết các vấn đề còn tồn đọng và
cuối cùng ta sẽ giải quyết được vấn đề ban đầu.

end;
end;
end;
Ví dụ : chương trình xếp n quân hậu trên bàn cờ có n*n ô sao cho không quân
nào ăn được quân nào. Chẳng hạn, với bàn cờ 8x8=64 ô, ta có một trong 92
cách xếp như sau :
Giả sử bàn cờ 4x4, ta làm như sau :
 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 19

Giải: Ta xếp n con hậu trên n dòng, theo nguyên lý nhân ta có n
n
cách sắp.
Để làm điều đó ta dùng thủ tục đệ quy mô tả ở trên để giải. Ta đánh ghi số cột và
dòng của bàn cờ từ 1 đến n, mỗi cách sắp xếp ứng với 1 bộ gồm a
1
,a
2
, ,a
n
với a
i
= j (j=1,2, ,n) có nghĩa là con hậu thứ i đặt vào cột j. Giả sử ta chọn được i-1 con
hậu bằng cách duyệt tất cả các khả năng của nó.
Quan trọng nhất là ta tìm điều kiện chấp nhận j, một con hậu đứng ở một ô
trong bàn cờ nó có nhiều nhất bốn hướng đi(đường dọc, đường ngang và hai
đường chéo).
Vậy điều kiện chấp nhận thứ i thoả mãn không nằm trên đường đi của tất
cả i-1 con hậu đã xếp. Bởi vì n con hậu xếp ở hàng nên đường đi ngang của
chúng là không chiến nhau, do đó khi chọn con hậu thư i chỉ cần kiểm tra xem

Begin
If i > n then
Print
Else
For j:=1 to n do
If Not(a[j]) and Not(b[i+j]) and Not(c[i-j]) then
Begin
x[i]:=j;
a[j]:=True;
b[i+j]:=True;
c[i-j]:=True;
Try(i+1);
a[j]:=False;
b[i+j]:=False;
c[i-j]:=False;
End;
End;
Procedure Init;
Var j : Integer;
Begin
Fillchar (a,sizeof(a),False);
Fillchar (b,sizeof(b),False);
Fillchar (c,sizeof(c),False);
End;
Begin {Main Program}
Clrscr;
Repeat
Write('Nhap n (n<=',Max,') : ');
Readln(n);
 Lê Đắc Ước Tân Thành - ĐT: 0907090779

For i:=1 to n*2 do write('Ä');
End;
{****************************************}
Function Deduoc(h,c: Integer) : Boolean; {Kiem tra xem co de duoc con hau o vi
tri h,c ? }
Begin
Deduoc := False;
{Kiem tra xem hang h da co con hau nao chua ?}
for i:= 1 to c do
if banco[h,i] then exit;
{ Kiem tra xem duong cheo tu tren trai xuong duoi phai }
{ xuyen qua vi tri h,c da co con hau nao chua ?}
i:= h-1; j:= c-1;
While (i>0) and (j>0) do
 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 22
Begin
If banco[i,j] then exit;
i:=i-1;
j:=j-1;
End;
{ Kiem tra xem duong cheo tu tren phai xuong duoi trai }
{ xuyen qua vi tri h,c da co con hau nao chua ?}
i:= h+1; j:= c-1;
While (i<=n) and (j>0) do
Begin
If banco[i,j] then exit;
i:=i+1;
j:=j-1;
End;

 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 23
Daxet[Dangxet] := Hang; {giu lai hang da xet}
goto Xettiep;
End;
End;
Hang := Hang+1;
End;
Dangxet := Dangxet - 1; {Lui lai con hau truoc}
if Dangxet = 0 then Exit; { da thu het cac kha nang }
Hang := Daxet[Dangxet]; {Lay lai hang da xet}
Banco[Hang,Dangxet] := False;
Hang := Hang + 1; {Tiep tuc xet tiep}
Until False;
End.
 Lê Đắc Ước Tân Thành - ĐT: 0907090779
Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 24
3. Phương pháp Hướng đích :
…………
4. Phương pháp Quy hoạch động :
…………
5. Phương pháp Tham lam :
Giải thuật tham lam (Greedy algorithm) là một thuật toán giải quyết một
bài toán theo kiểu metaheuristic để tìm kiếm lựa chọn tối ưu địa phương ở mỗi
bước đi với hy vọng tìm được tối ưu toàn cục. Chẳng hạn áp dụng giải thuật tham
lam với bài toán hành trình của người bán hàng ta có giải thuật sau: "Ở mỗi bước
hãy đi đến thành phố gần thành phố hiện tại nhất".
Nói chung, giải thuật tham lam có năm thành phần:
Một tập hợp các ứng viên (candidate), để từ đó tạo ra lời giải
Một hàm lựa chọn, để theo đó lựa chọn ứng viên tốt nhất để bổ sung vào

Tài liệu bồi dưỡng học sinh giỏi tin học bậc THCS Trang 25
màu đồ thị và tất cả các bài toán NP-đầy đủ khác, không một thuật toán tham lam
đã được biết nào đảm bảo tìm thấy các lời giải tối ưu. Tuy nhiên, các thuật toán
này vẫn hữu ích vì chúng dễ thiết kế và cho ra các ước lượng tốt về lời giải tối
ưu.
Nếu có thể chứng minh rằng một thuật toán tham lam cho ra kết quả tối ưu
toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ trở thành phương
pháp được chọn lựa, vì nó chạy nhanh hơn các phương pháp tối ưu hóa khác như
quy hoạch động. Các ví dụ cho giải thuật loại này là thuật toán Kruskal và thuật
toán Prim dành cho bài toán cây bao trùm nhỏ nhất, thuật toán Dijkstra dành cho
bài toán đường đi ngắn nhất nguồn đơn, và thuật toán tìm cây Huffman tối ưu.
Chương trình giải bài toán người bán hàng bằng phương pháp tham lam
(viết bằng ngôn ngữ c ++)với ma trận trọng số của đồ thị như sau:
0 15 30 50 20
15 0 10 35 32
30 10 0 15 40
50 35 15 0 43
20 32 40 43 0
chương trình :
#include "iostream"
#include "fstream"

using namespace std;
int n,a[25][25],b[25],k;
int NhapFile(char TenFile[], int &n)
{
ifstream iFile;
iFile.open(TenFile);
if (!iFile.is_open())
return 0;