3
CHƯƠNG 1
MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

Trong các bước giải quyết một bài toán trên máy tính, công
đoạn lập trình có vai trò quan trọng nhất.Việc ứng dụng tin học
ngày càng phát triển,các yêu cầu của thực tiễn ngày càng đa
dạng. Điều đó đòi hỏi phải thiết kế các giải thuật giải quyết một
cách hiệu quả nhất vấn đề đặt ra.
Trong chương này chúng ta xem xét một số khái niệm cơ bản
về cấu trúc dữ liệu và giải thuật,các phương pháp thiết kế giải
thuật thông dụng .
1. 1 MỘT SỐ KHÁI NIỆM VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI
THUẬT

Quá trình giải quyết một bài toán trên máy tính bao gồm
nhiều công đoạn . Bước thứ nhất là xác lập mô hình của bài
toán,tức là xác định cấu trúc toán học của bài toán đặt ra. Thực tế
cho thấy ,đối với các cơ sở thực tiễn người ta chỉ phác hoạ ra các
yêu cầu cần giải quyết một cách hình thức dưới dạng các yêu cầu,
mong muốn. Nhiệm vụ của phân tích viên hệ thống là phải
chuyển các yêu cầu rất hình thức đó thành các cấu trúc chặt chẽ
dưới dạng một mô hình toán học . Mô hình này là cơ sở để thiết
kế các bước tiếp theo giải quyết bài toán bắt đầu từ việc thiết kế
cấu trúc dữ liệu, thiết kế giải thuật, lựa chọn ngôn ngữ diễn đạt
giải thuật, đến việc thử nghiệm chương trình và phân tích kết quả
của chương trình nhằm đánh giá chất lượng của chương trình.
Qui trình giải một bài toán trên máy tính gồm 7 bước được
biểu diễn trong hình vẽ sau đây:
3

4

1

X©
y dùng m« h×
nh

2

ThiÕt kÕCSDL

3

ThiÕt kÕgi¶i thuËt

4

Chän ng«n ng÷lËp tr×
nh

5

ViÕt ch ¬ng tr×
nh

6


Thö nghiÖm ch ¬ng tr×
nh

7

Ph©
n tÝch kÕt qu¶

Về bản chất của kỹ thuật lập trình ,người ta thường đưa ra
một định nghĩa ngắn gọn như sau:
Programs = Data structure + Algorithm
Chương trình = Cấu trúc dữ liệu + Giải thuật
Định nghĩa này đã nêu lên thực chất của kỹ thuật lập trình:
Kỹ thuật lập trình là công việc lao động trí tuệ và sáng tạo trong
đó các nhà lập trình phải thực hiện hai công đoạn quan trọng:
• Công đoạn thiết kế cấu trúc dữ liệu
• Công đoạn thiết kế giải thuật.
4


5

Việc xây dựng phần mềm là một quá trình phức tạp, nó là
một nghệ thuật đồng thời cũng là một khoa học.Nó là một nghệ
thuật bởi vì nó đòi hỏi trí tưởng tượng tốt,óc sáng tạo cộng thêm
sự khéo léo.Là một khoa học bởi vì ở đó các kỹ thuật và phương
pháp tiêu chuẩn được sử dụng.Thuật ngữ công nghệ phần mềm
(Software Engineering) đã được dùng để chỉ việc nghiên cứu và
sử dụng những kỹ thuật này.Cả hai công đoạn đều đòi hỏi tính
sáng tạo rất cao,vì đứng trước mỗi bài toán đặt ra ,người lập trình

phải biết lựa chọn một cấu trúc dữ liệu phù hợp nhất,và trên cơ sở
đó tiến hành thiết kế một giải thuật hiệu quả nhất.
Định nghĩa
Giải thuật (Algorithm) là một dãy các qui tắc chặt chẽ xác
định một trình tự các thao tác trên một đối tượng cụ thể để
giải quyết một vấn đề hoặc để hoàn thành một mục đích cuối
cùng nào đó .
Trong tin học , thuật ngữ giải thuật dùng để chỉ một thủ
tục có thể thực hiện được bằng máy tính , và điều này dẫn đến
một số hạn chế đối với các lệnh tạo nên thủ tục:
1 - Chúng phải được xác định và không nhập nhằng để có thể biết
rõ lệnh đó làm gì?
2 - Chúng phải đủ đơn giản để máy tính hiểu được
3 - Chúng phải kết thúc sau một số hữu hạn các phép toán
Các giải thuật luôn luôn được thiết kế bởi ba cấu trúc điều khiển
sau đây:
• Cấu trúc tuần tự ( Sequential) các bước được thực hiện theo
trình tự một cách chính xác, mỗi bước được thực hiện đúng một
lần.
5


6

• Cấu trúc chọn lọc ( Selection ) một trong nhiều thao tác được
chọn và thực hiện.
• Cấu trúc chu trình( Repetition) một hay nhiều bước được thực
hiện lặp lại .
Ba cơ chế điều khiển chương trình này tuy đơn giản nhưng
trong thực tế đủ mạnh để xây dựng bất cứ giải thuật nào.

Nguyên tắc quan trọng để tạo ra một chương trình có chất lượng
cao là đảm bảo rằng chương trình phải có cấu trúc tốt. Muốn vậy
chúng ta nên thực hiện các vấn đề sau đây:
• Sử dụng phương hướng tiếp cận từ đỉnh xuống ( Top Down
Design ) để viết các chương trình phức tạp
• Sử dụng các cấu trúc diều khiển cơ bản để thiết kế cho từng
đơn thể của chương trình( Program Module)
• Sử dụng các biến cục bộ( Local variables) trong các chương
trình con
• Sử dụng các tham số để truyền tham số . Tránh dùng các biến
toàn cục( Global variables) để truyền tham số giữa các chương
trình con , bởi vì điều đó làm phá vỡ tính độc lập của các chương
trình con
Để chứng minh tính đúng đắn của một giải thuật, chúng ta
phải chứng minh một cách suy diễn rằng những bước trong giải
thuật xử lý đầu vào đúng đắn và tạo ra đầu ra theo yêu cầu. Như
vậy, một chứng minh tính đúng đắn của giải thuật bắt đầu bằng
một khẳng định( Giả thiết ) về dữ liệu vào ( Data Input) và dùng
các lý luận lôgic để chỉ ra rằng việc thực hiện giải thuật sẽ cho ta
một khẳng định( Kết luận) đúng về dữ liệu ra ( Data Output)
Định nghĩa

6


7

Một tập hợp các phần tử dữ liệu ban đầu trong một bài toán
được gọi là dữ liệu cơ sở
Ví dụ : Chúng ta xem xét bài toán kinh tế sau đây:

Trong hệ thống quản lý Ngân hàng, giả sử ta cần tính số
dư tiết kiệm của khách hàng, khi biết họ tên khách hàng, số tiền
gửi ban đầu, số tháng gửi và lãi suất hàng tháng. Trong trường
hợp này các dữ liệu cơ sở là :
- Họ tên người gửi
- Số tiền gửi ban đầu
- Lãi suất
- Kỳ gửi
Định nghĩa
Cấu trúc dữ liệu là sự kết hợp các dữ liệu cơ sở theo một
phương thức nào đó nhằm liên kết chúng thành một cấu trúc
thống nhất tiện lợi cho quá trình xử lý
Việc lựa chọn các cấu trúc dữ liệu, việc thiết lập các giải
thuật đúng đắn có cấu trúc tốt và hiệu quả , là những vấn đề mấu
chốt của việc thiết lập phần mềm.Hai khía cạnh này của việc phát
triển phần mềm có tầm quan trọng như nhau, và trong thực tế
chúng không thể tách rời . Không thể nói tới cấu trúc dữ liệu mà
không đề cập đến các giải thuật tác động lên các cấu trúc dữ liệu .
Ngược lại, mỗi giải thuật đều liên quan đến một cấu trúc dữ liệu
cụ thể , không thể có giải thuật chung chung cho mọi cấu trúc dữ
liệu . Khi cấu trúc dữ liệu thay đổi thì giải thuật cũng phải thay
đổi cho phù hợp để có thể xử lý một cách hiệu quả cấu trúc dữ
liệu ấy.
7


8

Để minh hoạ cho ý tưởng này ,chúng ta xét bài toán tạo
lập hồ sơ ban đầu trong phân hệ tin học quản lý nhân sự của một

cơ quan. Giả sử mỗi hồ sơ bao gồm các trường: Họ tên , tuổi, địa
chỉ, số năm công tác, mức lương.
Trước hết là việc chọn cấu trúc dữ liệu để giải quyết bài toán. Ta
có thể chọn 3 cấu trúc dữ liệu sau đây:
Cấu trúc dữ liệu tệp File
Cấu trúc dữ liệu động kiểu con trỏ Pointer
Cấu trúc dữ liệu mảng Array
Giải thuật tạo lập hồ sơ ban đầu trong 3 trường hợp sẽ như sau :
Trường hợp 1: Sử dụng cấu trúc dữ liệu tệp File
Program CreateFile;
Type
nhansu = record
Stt : integer;
(* Số thứ tự *)
Hoten : String [30];
( * Họ và tên * )
Tuoi : integer;
( * Tuổi
*)
namct : integer;
( * Số năm công tác *)
diachi : String [30];
( * Địa chỉ *)
Luong : real;
( * Lương * )
end;
Var
F : file of nhansu ;
Nguoi : nhansu ;
OK : char;

X, Y : integer;
Begin
Assign ( F, ' nhansu. dat ' );
Rewrite ( F );
OK : = ' C ' ;
8


9

Nguoi. Sott : = 1;
While ( OK = ' C ' ) or ( OK = ' c ' ) do
Begin
ClrScr;
GotoXY (20, 2 ); Write ( ' Program CreateFile ' );
X : = 12 ; Y : = 10 ;
GotoXY ( X,Y ) ; Write ( ' Sott : ' );
GotoXY ( X, Y+1 ); Write ( ' Hoten : ' );
GotoXY (X, Y+2 ); Write ( ' Tuoi : ' );
GotoXY ( X,Y+3); Write ( ' Nam cong tac');
GotoXY ( X, Y+4); Write (' Dia chi ');
Goto XY ( X, Y+5 ); Write ( ' Luong :' );
X : = X+14 ;
With Nguoi do
Begin
GotoXY ( X,Y ); Write ( SoTT );
GotoXY ( X, Y+1 ); Readln (Hoten ) ;
GotoXY ( X, Y+2 ); Readln ( Tuoi );
GotoXY ( X, Y+3); Readln( Namct);
GotoXY( X, Y+4); Readln (Diachi);

GotoXY ( X, Y+5 ); Readln ( Luong );
End;
If Nguoi. Hoten < > ' ' then
Begin
Write ( F, Nguoi );
Nguoi. SoTT : = Nguoi. SoTT +1;
End;
GotoXY (20, 20 ) ;
Write ( ' Tiep tuc nua khong ? ( C/ K )' );
Readln(OK);
End;
9


10

Close ( F );
End.
Trường hợp 2 : Sử dụng kiểu con trỏ [3]
Giải thuật:
Type
PointerN = ^ Nhan_Su ;
Nhan_Su = Record
Hoten : String[30];
Tuoi : integer;
Namct : Integer;
diachi :String [30];
Luong : real;
Next: PointerN;
End;

Var
Last , Ptr, p, q : PointerN;
HeapTop: ^ integer;
Name : String[30];
Begin
Last: = Nil ;
Mark ( HeapTop);
Repeat
Writeln;
Write(' Ho ten: ' ); Readln( Name);
If Name < > ' ' then
Begin
New( Ptr);
Ptr ^. hoten : = Name;
Write( ' Tuoi: ' ); Readln( Ptr ^. Tuoi)
10


11

Write (' Năm ctac'); Readln( Ptr ^. namct);
Write (' Địa chỉ: ' ); Readln( Ptr ^. diachi);
Write( ' luong ' ); Readln( Ptr ^. luong);
Ptr ^. Next : = Last;
Last: = Ptr;
End;
Until Name =";
(* Đọc lại toàn bộ danh sách *)
Writeln(' Danh sách cán bộ' );
Ptr: = Last ;

While Ptr < > nil do
Begin
Writeln(' Ho ten:', Ptr ^. hoten)
Writeln(' Tuoi:', Ptr ^. Tuoi);
Writeln(' Nam ctac' , Ptr^. namct);
Writeln(' Dia chi' , Ptr^. diachi);
Writeln ('luong' , Ptr ^.luong);
Writeln; Ptr: = Ptr ^. Next;
End;
Release( HeapTop);
end;
Trường hợp 3: Sử dụng cấu trúc dữ liệu mảng
Giải thuật:
Type
mt1 = Array[1 . . n ] of string;
mt2 = Array[1 . . n ] of real;
mt3 = Array [1 . . n] of integer;
( * n là số lượng cán bộ *)
Var
tuoi, namct : mt3;
11


12

luong : mt2;
Hoten,Diachi : mt1;
i: Integer;
Begin
For i : = 1 to n do

Begin
Write (' Hoten [',i ,' ] = '); Readln ( Hoten [i]);
Write (' Tuoi[',i,'] = ' ); Readln( Tuoi[i]);
Write (' Namct[',i,'] = '); Readln( Namct[i]);
Write (' Diachi[',i,'] =' ); Readln(Diachi[i]);
Write ( ' Luong[',i,'] ='); Readln(Luong[i]);
end;
end;
Qua ba trường hợp trình bày trên đây chúng ta thấy, tuy
cùng giải quyết một bài toán nhưng căn cứ vào cấu trúc dữ liệu
được lựa chọn mà các giải thuật có thể sẽ rất khác nhau. Điều này
khẳng định một lần nữa mối liên hệ không thể tách rời của hai
khái niệm cấu trúc dữ liệu ( Data structure ) và giải thuật
( Algorithm ) . Bây giờ chúng ta xem xét một vài khái niệm cơ
bản khác .
Định nghĩa
Phương thức biểu diễn một cấu trúc dữ liệu trong bộ nhớ
được gọi là cấu trúc lưu trữ ( Storage Structure ) của cấu trúc
dữ liệu ấy .
Hai khái niệm cấu trúc dữ liệu ( Data structure ) và cấu
trúc lưu trữ ( Storage Structure) không hoàn toàn đồng nhất. Thật
vậy , với cùng một cấu trúc dữ liệu có thể có nhiều cấu trúc lưu
trữ khác nhau. Chẳng hạn, với cấu trúc dữ liệu mảng hai chiều,có
12


13

hai cấu trúc lưu trữ rất thông dụng là cấu trúc lưu trữ ưu tiên
dòng(Row major order) và cấu trúc lưu trữ ưu tiên cột ( Colunm

major order). Mặt khác , nhiều cấu trúc dữ liệu lại có thể được
biểu diễn bằng một cấu trúc lưu trữ duy nhất. Chẳng hạn, cấu trúc
dữ liệu danh sách kiểu LIFO, cấu trúc danh sách kiểu FIFO, cấu
trúc dữ liệu cây Tree) đều có thể được thể hiện trong một cấu trúc
lưu trữ duy nhất là lưu trữ kế tiếp(Sequential storage allocation).
Trong môn học Cấu trúc dữ liệu , người ta thường nghiên
cứu các loại cấu trúc cơ bản sau đây :
• Mảng ( Array )
• Danh sách kiểu LIFO (Stack)
• Danh sách kiểu FIFO ( Queue)
• Danh sách liên kết đơn ( Singly linked list )
• Danh sách liên kết vòng ( Circularity linked list)
• Danh sách liên kết kép ( Double Linked list)
• Cấu trúc dữ liệu phi tuyến cây ( Tree)
• Cấu trúc dữ liệu phi tuyến kiểu đồ thị ( Graph )
1. 2 HIỆU SUẤT CỦA GIẢI THUẬT ( ALGORITH EFFICIENCY)

Mỗi cấu trúc dữ liệu đều có thể được cài đặt bằng nhiều
cách khác nhau , do đó giải thuật xử lý các dữ liệu ấy cũng khác
nhau. Việc đánh giá những cách cài đặt khác nhau của cấu trúc dữ
liệu dựa trên hai điều kiện chính:
Một là , khối lượng bộ nhớ để lưu trữ cấu trúc dữ liệu ấy
Hai là , thời gian cần thiết để thực hiện giải thuật xử lý
dữ liệu
Trong hai chỉ tiêu trên đây thì chỉ tiêu thứ hai ,tức là thời
gian thực hiện một giải thuật thường được xem là quan trọng

13



14

hơn. Chúng ta sẽ xem xét xem chỉ tiêu này được đánh giá như thế
nào?
Thời gian thực hiện một giải thuật chịu ảnh hưởng của
nhiều yếu tố. Một yếu tố quan trọng là kích thước đầu vào,bởi vì
số các mục đầu vào thường ảnh hưởng đến thời gian xử lý
chúng.Ví dụ , thời gian cần thiết để sắp xếp thứ tự danh sách các
mục phụ thuộc vào số lượng các mục trong danh sách.Như vậy
,thời gian thực hiện T của một giải thuật như một hàm T(n) của
độ lớn của dữ liệu đầu vào n .Các kiểu lệnh ( Instruction) và vận
tốc của máy tính thực hiện những lệnh đó cũng ảnh hưởng đến
thời gian thực hiện một giải thuật.Tuy nhiên những yếu tố này
phụ thuộc vào máy tính đang sử dụng vì vậy chúng không thể
biểu diễn giá trị của T(n) bằng các đơn vị thời gian đầy đủ chẳng
hạn như bằng giây [1]. Thay vào đó, T(n) sẽ được tính gần đúng
như là số lượng các lệnh (Instruction) thực hiện. Một yếu tố khác
có ảnh hưởng đến thời gian thực hiện giải thuật là chất lượng của
chương trình do chương trình dịch tạo ra. Không phải mọi
chương trình dịch đều cho ta các chương trình có hiệu suất như
nhau. Như vậy, T(n) không thể tính như số lượng các lệnh máy
( Machine instruction) Hàm T(n) sẽ được tính như là số lần thực
hiện các lệnh trong giải thuật. Sau đây là bảng giá trị của một số
hàm thường dùng để đánh giá độ phức tạp của giải thuật :

Log2

n

n


n Log2

n2

n3

2n

n
14


15

0
1
2
3
4
5

1
2
4
8
16
32

0

2
8
24
64
160

1
4
16
64
256
1024

1
8
64
512
4096
32768

2
4
16
256
65536
2147483648

Các hàm như 2 N , n! được gọi là các hàm mũ . Các giải thuật có
thời gian thực hiện là một hàm mũ thường có tốc độ tính toán rất
chậm . Còn các hàm đa thức như n , n 2 , n 3 , Log2 n , n Log2 n

có tốc độ thực hiện tốt hơn .
Giả sử rằng mỗi lệnh trong giải thuật được thực hiện trong
1 micrô giây . Thời gian cần thiết để thực hiện f(n) lệnh đối với
các hàm thông dụng với n= 256 cho trong bảng sau đây :
Hàm
Logn
n
nLogn
n2
n3

Thời gian
8 Micrô giây
0. 25 Micrô giây
2 Micrô giây
65 Micrô giây
17 Micrô giây

Các qui tắc xác định độ phức tạp của giải thuật :
QUI TẮC CỘNG

Giả sử T1( n ) và T2( n) là thời gian thực hiện hai giải thuật A1
và A2 với T1(n) = O(f(n)) và T2 = O(f(n)) . Khi đó thời gian thực

15


16

hiện A1 rồi đến A2 sẽ là T = T1(n) + T2 (n) và được đánh giá

bằng đại lượng O ( max( f(n),g(n)).
QUI TẮC NHÂN

Giả sử T1( n ) và T2( n) là thời gian thực hiện hai giải thuật A1
và A2 với T1(n) = O(f(n)) và T2 = O(f(n)) . Khi đó thời gian thực
hiện A1 và A2 lồng nhau sẽ là T1(n)T2 (n) = O ( f(n),g(n)).
Ví dụ 1
Trong chương trình chúng ta phải thực hiện 3 giải thuật liên tiếp
nhau với các độ phức tạp là O( n 2 ) , O ( n 3 ) và O (n Log2 n ) .
Khi đó thời gian thực hiện chương trình sẽ là O( n 3 )
Ví dụ 2
Câu lệnh gán x : = x+1; có độ phức tạp là C ( hàng số ) nên theo
ký pháp cữ O lớn ta có O(1).
Ví dụ 3
Câu lệnh chu trình For i : = 1 to n do x : = x+1; cơ độ phức tạp
là O(n.1) = O(n)
Ví dụ 4
Câu lệnh chu trình lồng nhau For i : = 1 to n do
For j : = 1 to n do x : = x+1;
2
có độ phức tạp O (n.n) = O( n )
16


17

Để minh hoạ ,chúng ta xem xét giải thuật tìm giá trị trung bình
của n số.
GIẢI THUẬT TÍNH GIÁ TRỊ TRUNG BÌNH


Cho năng suất lao động trung bình của n doanh nghiệp . Tính
năng suất lao động trung bình ?
1. Đọc n
2. Cho giá trị ban đầu Sum =0
3. Cho chỉ số ban đầu i =1
4. Tính Sum= Sum + [ NSLĐ ] i
5. Tăng i: i=i+1
6 . Kiểm tra điều kiện i<= n . Nếu đúng thì thực hiện bước 4 .
Nếu không thì chuyển xuống bước 7
7. Tính năng suất trung bình = Sum / n
Trong giải thuật này , các lênh 1,2,3 thực hiện một lần. Các
lệnh 5,6,7 tạo ra thân của vòng lặp và được thực hiện n lần. Câu
lệnh 4 kiểm tra sự lặp lại sẽ được thực hiện n+1 lần. Sau khi kết
thúc vòng lặp, lệnh 8 chỉ thực hiện một lần. Kết quả phân tích
cho trong bảng sau đây:

Lệnh
1
2
3

Số lần thực hiện
1
1
1
17


18


4
5
6
7
Tổng cộng

n
n
n
1
3n+4

chúng ta thấy rằng thời gian thực hiện của giải thuật này là T(n)=
3n+4 . Khi giá trị n tăng lên , giá trị của T(n) cũng tăng lên theo
một cách tuyến tính. Chúng ta nói rằng, T(n) có "bậc" là n và
được ký hiệu theo " ký pháp chữ O lớn" của toán học như sau:
T(n)= O(n)
Một cách tổng quát , thời gian tính toán T(n) của một giải thuật
được gọi là có bậc f(n) ,ký hiệu bởi T(n)= O(f(n)) nếu tồn tại các
số dương C và No sao cho :
T(n)<=C .f(n) với mọi n>=N0
nghĩa là T(n) bị chặn trên bởi một hằng số nhân với f(n) với mọi
giá trị của n từ một điểm nào đó. Độ phức tạp của giải thuật này
được gọi là O(F(n))
Ví dụ, độ phức tạp của giải thuật trên đây là O(n) bởi vì
thời gian tính được là T(n)=4n+5 và vì 4n+5<= 4n+n với mọi
n>5. Ta có T(n) <=5n với mọi n>5 .
Như vậy, ta chỉ cần chọn F(n)=n, No=5 và C=5 chúng ta
có thể viết: T(n)= O(n) . Đương nhiên là bất đẳng thức cũng
đúng khi ta viết T(n)=O(5280n) hay T(n)=O(4n+5) hay T(n)=

(3.1416 n+ 2.71828) nhưng chúng ta chọn các hàm đơn giản hơn
như n,Log để biểu diễn độ phức tạp của giải thuật.

18


19

Chúng ta xét thêm giải thuật tìm kiếm tuyến tính sau đây : Tìm
phần tử có giá trị Item cho trước trong mảng A[1], A[2]...A[n]và
nếu có thì xác định vị trí của nó.
GIẢI THUẬT TÌM KIẾM TUYẾN TÍNH

( Tìm Item trong danh sách A[i] . Found sẽ có giá trị đúng và
Loc có giá trị là vị trí của Item. Nếu không Found sẽ có giá trị
sai)
1. Gán giá trị sai cho Found
2. Gán giá trị 1 cho Loc
3. While Loc<= n and not Found , thực hiện các bước sau đây:
4. If Item =A[Loc] then
5. Gán giá trị đúng cho Found
6. Else
Tăng Loc thêm
Trường hợp xấu nhất là không tìm thấy Item trong danh sách và
trong trường hợp này thời gian tính TL(n) cho giải thuật tìm
kiếm tuyến tính như sau:
Lệnh
1
2
3

4
5
6
Tổng cộng

Số lần thực hiện
1
1
n+1
n
0
n
3n+3

19


20

Như vậy, TL (n)= 3n+3 hay TL(n)= O(n) bởi vì 3n+3<=4n với
mọi n>=3. Nếu danh sách đã dược sắp xếp thì quá trình tìm kiếm
sẽ nhanh hơn rất nhiều . Giải thuật tìm kiếm nhị phân sau đây tiến
hành như sau:
Nếu Item < A[Mid] : tìm trong nửa đầu của danh sách
Nếu Item > A[Mid] : tìm trong nửa cuối của danh sách
Nếu Item =A[Mid] : tìm ra Item
Trong đó Mid là phần tử ở giữa của danh sách.
GIẢI THUẬT TÌM KIẾM NHỊ PHÂN

( Tìm kiếm nhị phân phần tử Item trong danh sách. Found sẽ có

giá trị đúng và Mid có giá trị là vị trí của Item nếu tìm được. Nếu
không Found sẽ có giá trị là sai)
1. Gán giá trị sai cho Found
2. Gán 1 cho First
3. Gán n cho Last
4. While First <= Last and not Found thực hiện các bước sau dây:
5. Tính Mid=(First+Last)/2
6. If Item 7. Gán giá trị Mid=1 cho Last
8. Else If Item >A[Mid] then
9. Gán giá trị Mid+1 cho First
10. Else gán giá trị đúng cho Found
Trong giải thuật này các lệnh 1,2 và 3 được thực hiện
đúng một lần và để tính độ phức tạp cho trường hợp xấu nhất
TX(n) chúng ta phải tính số lần thực hiện của vòng lặp chứa các
lệnh từ 4 đến 10. Mỗi lần đi qua vòng lặp này độ lớn của danh
sách giảm đi một nửa. Lần cuối cùng đi qua danh sách có độ lớn
là 1. Như vậy số lần lặp lại tổng cộng của vòng lặp này là 1 cộng
20


21

với k lần đi qua vòng lặp để cuối cùng tạo ra danh sách con có độ
dài 1.
Vì độ lớn của danh sách con sau k lần đi qua nhiều nhất là N/ 2 N
ta có:
2K < 2
Log

2
nghĩa là N< 2 K +1 hay
n < k+1
Số lần đi qua vòng lập là số nguyên bé nhất thoả mãn bất

đẳng thức trên đây. nghĩa là phần nguyên của Log2 n . Như vậy
trong trường hợp xấu nhất , khi Item lớn hơn các phần tử
A[1],A[2]...A[n] ,lệnh 4 được thực hiện không nhiều hơn 2+
Log2

n lần, lệnh 5,6 và 8 không nhiều hơn 1+ Log2 n lần và

các lệnh 7,9 và 10 không lần. Thời gian tính tổng cộng như vậy
không quá 8+4 Log2 n lần, tức là TX(n)= O( Log2 n ). Bởi vì
Lôgarit cơ số hai xuất hiện rất thường xuyên trong phân tích giải
thuật chúng ta qui ước ký hiệu Log n là Log2 n .
Như vậy , chúng ta thấy độ phức tạp của giải thuật tìm
kiếm tuyến tính là O(n) còn của giải thuật tìm kiếm nhị phân là
O(Logn) rõ ràng là giải thuật tìm kiếm nhị phân có hiệu quả hơn
đối với các danh sách có qui mô lớn. Nhưng đối với các danh
sách có qui mô nhỏ giải thuật tìm kiếm tuyến tính vẫn có ưu thế.
Các nghiên cứu cho thấy, đối với các danh sách có không quá 20
phần tử, giải thuật tìm kiếm tuyến tính có hiệu quả hơn giải thuật
tìm kiếm nhị phân.
1. 3 PHƯƠNG PHÁP DIỄN ĐẠT GIẢI THUẬT

21


22

Để diễn đạt một giải thuật , thông thường người ta có thể dùng ba
phương pháp chủ yếu sau đây :
Phương pháp 1 Diễn đạt giải thuật bằng lời
Phương pháp 2 Diễn đạt giải thuật bằng sơ đồ khối
Phương pháp 3 Diễn đạt giải thuật bằng một ngôn ngữ lập trình
có cấu trúc.
Ta xét ví dụ biểu diễn giải thuật tính giá trị trung bình của một
dãy số A[1],A[2],... A[n]
Để diễn đạt giải thuật bằng lời ta có các dãy sau đây:
1. Đọc n
2. Cho Sum =0
3. Cho i=1
4. Tính Sum = Sum+ A[i]
5. Tăng I =I+1
6. Nếu I<= n thì chuyển lên bước 4; nếu không thì xuống bước
7. Tính Mean = Sum/n
8. In Mean
Bây giờ ta có biểu diễn bằng sơ đồ khối như sau :

22


23

N¹p A[i} i=1...n
Sum:=0; I:=1

Sum:=Sum+A[i];
I:=I+1;

F

I<=n

T

Mean :=Sum/n;
Printer Mean;

Nếu dùng ngôn ngữ PASCAL ta có đoạn chương trình sau
đây:
Read(n);
For i:= 1 to n do
read(A[i]);
Sum =0;
For i:= 1 to n do
Sum:= Sum+ A[i];
Mean:= Sum/n;
Writeln(' Gia tri trung binh:', Mean:12:2);
23


24

Chúng ta xét thêm một ví dụ khác. Trong phân hệ quản
lý của một doanh nghiệp, người ta yêu cầu tính giá trị tổng sản
lượng trong một năm . Giả sử rằng doanh nghiệp có n phân
xưởng cùng sản xuất ra m loại sản phẩm . Biết số lượng sản
phẩm của mỗi phân xưởng và đơn giá của mỗi sản phẩm.

Phương pháp 1 : Diễn đạt giải thuật bằng lời.
• Bước 1 : Nạp số liệu
• Bước 2 : Tính toán giá trị tổng sảnlượng của một phân xưởng
bằng cách lấy số lượng từng loại sản phẩm nhân với đơn giá .
• Bước 3 : Kiểm tra xem đã tính giá trị tổng sản lượng cho tất
cả các phân xưởng hay chưa?
• Bước 4 : Tinh giá trị tổng sản lượng của cả doanh nghiệp
• Bước 5 : In kết quả.
Phương pháp diễn đạt giải thuật bằng lời có ưu điểm là làm cho
người đọc dễ dàng nắm bắt được tư tưởng chủ đạo của giải thuật,
nhưng nó còn rất "thô" ,khi chuyển giải thuật sang một ngôn ngữ
lập trình cụ thể nào đó (C++ , Pascal,...)ta phải thiết kế làm "mịn"
dần trong rất nhiều công đoạn
Phương pháp 2 : Diễn đạt giải thuật bằng sơ đồ khối
Tư tưởng của phương pháp này là trên cơ sở ý đồ chủ đạo
của giải thuật, người ta tiến hành xây dựng các khối biểu diễn các
qui trình tính toán và mối liên hệ giữa các khối với nhau.
Phương pháp biểu diễn thuật toán bằng sơ đồ khối cho ta một cái
nhìn tổng thể về phương pháp giải quyết bài toán đặt ra. Trên cơ
sở của sơ đồ khối người ta đễ dàng chuyển thành chương trình
24


25

trong một ngôn ngữ lập trình cụ thể.Chẳng hạn ta xem xét sơ đồ
khối biểu diễn giải thuật tính giá trị tổng sản lượng của doanh
nghiệp sau đây:
GTSP i = 0 ; i=1,2...n
I=1

J=1
GTSP i = GTSP i +SLi j*GIAj
J =J +1
F

J <= M

T

I =I +1
F

I<= N

T

Tinh tong
In

Phương pháp 3 : Diễn đạt giải thuật bằng một ngôn ngữ lập
trình cụ thể
Theo phương pháp này người ta sử dụng một ngôn ngữ lập trình
có cấu trúc(như Pascal chẳng hạn) để biểu diễn thuật toán.
Chẳng hạn trong PASCAL giải thuật của bài toán tính giá trị tổng
sản lượng của doanh nghiệp được biểu diễn như sau:
Type
25


26

A = array [1...n,1...m] of real;
B = array [1...m] of real;
C = array [1...n] of real;
Var
Soluong : A ;
gtsp : C ;
gia : B ;
i , j : interger ;
tong : real;
Begin
For i : =1 to n do
For j : =1 to m do
Readln (soluong [i,J] );
For j : =1 to m do
Readln (gia [J] );
For i : =1 to n do
Begin
gtsp [i] : = 0;
For j : =1 to m do
gtsp [i] : = gtsp [i] +soluong [i, J] * gia [J] ;
end;
tong:= 0 ;
For I : =1 to n do Tong:= Tong + gtsp [i] ;
Write ('Gia tri tong san luong:');
WriteLn (tong:12:2);
end;
Như vậy , qua việc trình bày 3 phương pháp khác nhau
để diễn đạt một giải thuật chúng ta có một số nhận xét sau đây:
• Phương pháp diễn đạt giải thuật bằng lời giúp ta dễ nắm bắt tư

tưởng chủ đạo của giải thuật nhưng còn ở mức độ trừu tượng cao,
26


27

từ giải thuật đến chương trình cụ thể còn cần nhiều công đoạn
làm “mịn” ( Chi tiết dần đến mức từng lệnh cụ thể)
• Phương pháp sơ đồ khối cho ta một cái nhìn tổng quát về cấu
trúc của một giải thuật nhưng đối với các giải thuật phức tạp về
tính logic thì phương pháp này kém hiệu quả.
• Phương pháp diễn đạt bằng một ngôn ngữ thuật toán cụ thể tuy
phải tuân theo các qui định của ngôn ngữ đó nhưng việc lựa chọn
một ngôn ngữ có cấu trúc tiền định đủ mạnh ( như Pascal chẳng
hạn) sẽ cho phép chúng ta biểu diễn các giải thuật một cách ngắn
gọn, dễ dàng hình dung ra các công đoạn thiết kế giải thuật.
PASCAL có các cấu trúc dữ liệu đầyđủ, có thể biểu diễn các loại
cấu trúc dữ liệu từ đơn giản đến phức tạp , từ cấu trúc tuyến tính
đến cấu trúc phi tuyến .
Trong giáo trình này chúng tôi sử dụng Pascal để biểu
diễn các giải thuật. Trong một vài trường hợp sẽ sử dụng thêm cả
sơ đồ khối để minh hoạ .
1.4 GIẢI THUẬT ĐỆ QUI ( RECURSIVE ALGORITHM )

Giải thuật đệ qui có vai trò rất đặc biệt . Nhờ giải thuật đệ
qui mà chúng ta có thể thiết kế lời giải của một bài toán phức tạp
một cách rất ngắn gọn , cô đọng . Có một số vấn đề mà các giải
thuật đệ qui là thích hợp hơn cả để giải quyết chúng .
Trong phần này chúng ta sẽ xem xét giải thuật đệ qui ,
chứng minh tính đúng đắn của giải thuật đệ qui và hiệu suất của

giải thuật đệ qui so với giải thuật không đệ qui .
Trước hết , chúng ta làm quen với khái niệm đệ qui.
Chúng ta nói một đối tượng nào đó là đệ qui nếu nó bao hàm
chính nó như một bộ phận cấu thành . Hoặc nói một cách khác là
đối tượng đó được định nghĩa thông qua chính bản thân nó .
Định nghĩa đệ qui luôn luôn bao gồm hai phần :
27