MỤC LỤC
NỘI DUNG.........................................................................................................................................................1
PHẦN I: MỘT SỐ THUẬT TOÁN CƠ BẢN.......................................................................................................1
1. Thuật toán.............................................................................................................................................3
2. Biễu diễn thuật toán.............................................................................................................................5
Phần II: BÀI TOÁN TÌM KIẾM........................................................................................................................8
3. Đánh giá hiệu quả của thuật toán........................................................................................................8
4. Giải thuật tìm kiếm...............................................................................................................................8
PHẦN III: BÀI TOÁN ÁP DỤNG....................................................................................................................11
1.Phát biểu bài toán...............................................................................................................................11
TÀI LIỆU THAM KHẢO......................................................................................................................................14

NỘI DUNG
PHẦN I: MỘT SỐ THUẬT TOÁN CƠ BẢN

1


Việc sử dụng máy tính điện tử để giải quyết một bài toán nào đó thường được hiểu
một cách không đầy đủ. Nhiều người cho rằng đó chỉ là việc lập trình thuần túy. Thực ra,
giải một bài toán trên máy tính điện tử là một quá trình phức tạp, bao gồm nhiều giai
đoạn phát triển, mà lập trình chỉ là một trong các giai đoạn đó.
Ta hãy xét bài toán giải hệ phương trình đại số tuyến tính trên máy tính. Đây là
một bài tập khá quen thuộc đối với sinh viên các chuyên ngành kỹ thuật. Với một đầu vào
như vậy, không ít sinh viên cho rằng chỉ còn một việc duy nhất, đó là viết chương trình.
Về mặt lý thuyết, toán học đã giải quyết khá đầy đủ: từ phát biểu bài toán, thuật toán và
xây dựng các phân tích về nghiệm của hệ phương trình trong các trường hợp khác nhau.
Nhưng khi viết chương trình trên máy tính để giải bài toán trên sẽ có một số vấn đề phải
làm rõ. Thậm chí có những vấn đề gặp phải ngay từ khi viết những dòng đầu tiên trong
chương trình như kích thước của hệ phương trình chẳng hạn. Số ẩn và số phương trình tối
đa là bao nhiêu? Nếu để ý tiếp ta sẽ thấy ngay một số thông tin mà người lập trình phải

3) Lặp lại bước 2) nếu còn các số nguyên trong dãy.
4) Giá trị cực đại tạm thời ở thời điểm này chính là số nguyên lớn nhất trong
dãy.
Trên đây là những chỉ dẫn cụ thể từng bước được thể hiện bằng ngôn ngữ thông
thường. Chúng ta sẽ tìm cách thể hiện lại thuật toán giải bài toán trên theo cách thức
khác:
-

Dữ liệu vào (input): A là mảng chứa n số nguyên.
Dữ liệu ra (output): max, số lớn nhất trong mảng A.
Procedure Tim_max (A: mảng có n số nguyên);
a) Đặt max:= A (1);
b) Xét từ i = 2 đến n
Nếu max < A (i) thì đặt max:=A(i);

Bảng mô tả thuật toán có các yếu tố:
a) Tính xác định: Các bước của thuật toán phải được xác định một cách chính xác,
các chỉ dẫn phải rõ ràng, có thể thực hiện được.
b) Tính hữu hạn: Thuật toán phải kết thúc sau một số hữu hạn bước.
c) Tính đúng đắn: Thuật toán phải cho kết quả đúng theo yêu cầu của bài toán đặt
ra.
d) Tính tổng quát: Thuật toán phải áp dụng được cho mọi bài toán cùng loại, với
mọi dữ liệu đầu vào như đã được mô tả.
Khi mô tả một thuật toán cần đảm bảo các yếu tố sau đây:

3


- Dữ liệu đầu vào: Một thuật toán phải mô tả rõ các giá trị đầu vào từ một tập hợp
các dữ liệu xác định. Ví dụ, dãy số nguyên a(1), a(2),…,a(n), với n

4


Ví dụ 3: Cho mảng số nguyên A đã được sắp xếp không gian và số nguyên x. Hãy xác
định xem số nguyên x có trong mảng A hay không. Nếu có, hãy chỉ ra vị trí của x trong
mảng A.
Dữ liệu đầu vào của bài toán này khác với bài toán trước ở chỗ mảng A được sắp
xếp không giảm. Nhờ thế mà chúng ta có thể lựa chọn thuật toán tìm kiến nhị phân để
giải bài toán này.
Thuật toán:
- Input: Mảng A gồm n các số nguyên đã được sắp xếp tăng dần và số nguyên x
cần tìm trong danh sách.
- Output: Chỉ số Index, chỉ số Index bằng chỉ số phần tử bằng x, hoặc bằng 0 nếu
không tìm dược x.
Prucedure Timkiem_NP(A: mảng số nguyên; x: số nguyên)
+ CS trái :=1; CS phải :=n;
+ Chưa tìm thấy :=True;
+ While (còn khoảng tìm) and (chưa tìm thấy) Do
• Index:= Chỉ số ở giữa CS trái và CS phải;
• If x =A(i) Then đặt chưa tìm thấy = false
Else khoảng tìm sẽ bị co hẹp;
If x< A(Index) Then CS phải = Index -1
Else CS trái = Index + 1;
+ If chưa tìm thấy Then đặt Index :=0;
Trước khi giải một bài toán trên máy tính người lập trình phải phân tích bài toán,
hiểu rõ các yêu cầu và ràng buộc của nó sau đó mới xây dựng thuật giải. Thuật giải cũng
có thể được lựa chọn trong các thuật toán quen biết, cũng có thể do người lập trình xây
dựng thông qua hiểu biết và cảm nhận của mình.
2. Biễu diễn thuật toán

i:=2

True
ĐK

S
False
Ví dụ, sơ đồ khối sau đây
mô tả thuật toán tìm giá trị lớn nhất trong mảng số A có
i
Bài toán tìm kiếm là: Tìm kiếm một phương án, đáp án theo yêu cầu đầu vào.
VD:

- Cho một danh sách xác định vị trí xuất hiện của một phần tử trong danh sách.
- Tìm kiếm giải pháp lựa chọn để đạt giá trị cực đại trong bài toán cái túi.

Bài toán xảy ra trong hai tình huống:
- Dữ liệu xuất hiện được coi là ngẫu nhiên.
- Dữ liệu thỏa mãn một số ràng buộc nhất định.
2. Phân loại
-Tìm kiếm tuần tự
- Tìm kiếm nhị phân
- Tìm kiếm dựa trên quy hoạch
.......
3. Đánh giá hiệu quả của thuật toán
Tính hiệu quả của thuật toán thông thường được đo bởi thời gian (thời gian được
sử dụng để tính bằng máy hoặc bằng phương pháp thủ công) – độ phức tạp thời gian, khi
các giá trị đầu vào có kích thước xác định. Tính hiệu quả của thuật toán cũng được xem
xét theo thước đo dung lượng bộ nhớ đã sử dụng để tính toán khi kích thước đầu vào đã
xác định – độ phức tạp không gian.
Độ phức tạp không gian gắn liền với việc xem xét các cấu trúc dữ liệu đặc biệt
được dùng để thể hiện thuật toán.
Độ phức tạp thời gian của một thuật toán thường được biểu diễn thông qua số
phép toán trong khi thực hiện thuật toán khi các giá trị dữ liệu đầu vào có kích thước xác
định.
4. Giải thuật tìm kiếm
Bài toán
8





X(n+1)=b; k:=1;
While X(k) b do k:=k+1;
If k=n+1 then TKTT:=0 else TKTT:=k;
End;
Thì trong trường hợp xấu nhất ta cần n+1 phép so sánh. Trong cả hai trường hợp ta
có độ phức tạp của thuật toán là O(n).
4.2. Tìm kiếm nhị phân
Ý tưởng
Trên các bản ghi mà khóa đã được sắp xếp tăng dần so sánh khóa tìm kiếm b với
khóa của bản ghi ở giữa của đoạn mảng đang xét. Chẳng hạn mảng đang xét là X[l..r] thì
phần tử (bản ghi) ở giữa là X(k) với k=(l+r)/2; nếu X(k)=b thì việc tìm kiếm kết thúc, nếu
X(k)b thì việc tìm kiếm sẽ được thực hiện trên mảng con X[k+1,r]. Quá trình tìm
kiếm trên mảng con sẽ được tiếp tục với thủ tục nêu trên.
Thuật toán
Input: Mảng X[1..n], giá trị b
Output: Chỉ số k [1..n] mà tại đó X(k)=b hoặc nếu X(k) b với k [1..n]
Function TKNP (b: Khóa tìm kiếm): Chỉ số;
Begin
TKNP:=0;
can_trai:=1; can_phai:=n;
While can_trai

can_phai do

Begin
K:=(can_trai + can+phai)/2;
If X(k) = b then


PHẦN III: BÀI TOÁN ÁP DỤNG
1. Phát biểu bài toán
Cho dãy X gồm n số nguyên n ≤ 1000000. Hãy tìm dãy con đơn điệu gồm các
phần tử liên tiếp của X sao cho có nhiều phần tử nhất. Ví dụ, nếu X = { 12, 2, 3, 4, 6, 7, 1,
9, 10 } thì dãy con cần tìm là {2, 3, 4, 6, 7} có 5 phần tử.
2. Nhận định ban đầu
-

Số dãy con của x:

Chúng ta có thể xem mỗi dãy con x của X tương đương với một chuỗi nhị phân b,
độ dài n trong đó, bi = 0 nghĩa là ai không thuộc a và ngược lại bi = 1 nghĩa là ai thuộc a.
11


Ví dụ nếu X = [1, 3, 2, 3] thì dãy con tương ứng với chuỗi nhị phân b = 1010 là [1, 3].
Như vậy, số dãy con của X cũng chính là số chuỗi nhị phân có độ dài n chính là 2 n. Mặc
dù có thể với 2 chuỗi nhị phân khác nhau sẽ tương ứng với cùng một dãy con (với
mảng X = [1, 3, 2, 3], hai chuỗi 1100 và 1001 cùng tương ứng với dãy con [1, 3]), nhưng
nếu lập trình bình thường để duyệt tất cả các dãy con của X thì phải duyệt 2 n phần tử.
Với n = 100 thì có đến 2100≈ 1030 dãy con.
-

Phương án khả thi:

Phương án duyệt tất cả các dãy con để tìm kết quả tối ưu có độ phức tạp là O (2 n),
rõ ràng là không khả thi khi n lớn. Do đó chúng ta sẽ sử dụng thuật toán quy hoạch động
để giải bài toán.
3. Ý tưởng

i = 2, ta xét 12< 2, dãy giảm, đưa 2 vào ta được dãy {12,2}
i = 3, ta thấy 23. />4. />5. Giải thuật và lập trình – Lê Minh Hoàng – Đại học sư phạm Hà Nội, 1999 - 2002

14