Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH

20

CHƯƠNG II
BÀI TOÁN VÀ THUẬT TOÁN

2.1. KHÁI NIỆM BÀI TOÁN
2.1.1. Bài toán
Trong phạm vi Tin học, ta có thể quan niệm bài toán là việc nào đó ta
muốn máy tính thực hiện.
Viết một dòng chữ ra màn hình, giải phương trình bậc hai, quản lí điểm
trong trường học v.v…
Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố: đưa
vào máy thông tin gì (Input) và cần lấy ra thông tin gì (Output). Do đó để phát
biểu một bài toán ta cần phải chỉ rõ Input và Output của bài toán đó.
Ví dụ 1: Giải phương trình bậc nhất ax+b=0
Input: Các giá trị thực a,b
Output: Nghiệm là giá trị x hoặc thông báo không có nghiệm
Ví dụ 2: Quản lí điểm trong trường học
Input: Thông tin cá nhân của từng học sinh
Output: Thông tin cần khai thác về một học sinh, một lớp học
sinh, một khối hay toàn trường.
2.1.2. Các bước giải bài toán bằng máy tính điện tử
Học sử dụng máy tính thực chất là học cách giao cho máy tính việc mà
ta muốn nó làm. Khả năng khai thác máy tính phụ thuộc rất nhiều vào sự hiểu
biết của người sử dụng.Việc giải bài toán trên máy tính được tiến hành qua
các bước sau:
Bước 1: Xác định bài toán
Như đã trình bày, mỗi bài toán được đặc tả bởi hai thành phần: Input và
Output. Việc xác định bài toán chính là xác định rõ hai thành phần này. Các

theo đúng quy định ngữ pháp của ngôn ngữ đó. Chương trình dịch có thể giúp
ta phát hiện và thông báo đầy đủ các sai sót về mặt ngữ pháp.
Bước 4: Hiệu chỉnh
Sau khi được viết xong, chương trình vẫn còn có thể có nhiều lỗi khác
chưa phát hiện được nên chương trình có thể không cho kết quả đúng. Vì vậy,
cần phải thử chương trình bằng cách thực hiện nó với một số bộ Input tiêu
biểu phụ thuộc vào đặc thù của bài toán. Các bộ Input này gọi là các Test. Nếu
Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH

22

có sai sót, ta phải sửa chương trình rồi thử lại. Quá trình này được gọi là hiệu
chỉnh.
Bước 5: Viết tài liệu
Tài liệu phải mô tả chi tiết bài toán, thuật toán, chương trình, kết quả
thử nghiệm và hướng dẫn sử dụng. Tài liệu này rất có ích cho người sử dụng
chương trình và cho việc đề xuất những khả năng hoàn thiện thêm.
Các bước trên có thể lặp đi lặp lại nhiều lần cho đến khi mà ta cho là
chương trình đã làm việc đúng đắn.
2.2. KHÁI NIỆM THUẬT TOÁN
2.2.1. Định nghĩa
Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được
sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác
đó, từ Input của bài toán, ta nhận được Output cần tìm.
Có nhiều cách trình bày thuật toán: dùng ngôn ngữ tự nhiên; sơ đồ
khối; ngôn ngữ lập trình(tựa Pascal).
2.2.2. Một số ví dụ
Ví dụ 1: Mô tả thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn
các số bất kì (nguyên hoặc thực).
a) Dùng ngôn ngữ tự nhiên để mô tả các bước cần phải thực hiện:

{Item quy ước là một kiểu dữ liệu bất kì nào đó}
Ví dụ 2: Mô tả thuật toán tìm tổng các phần tử dương trong một dãy
hữu hạn các số bất kì.
a) Dùng ngôn ngữ tự nhiên để mô tả các bước cần phải thực hiện:
1. Đặt giá trị tổng ban đầu bằng 0.
2. Đi từ đầu dãy tới cuối dãy, kiểm tra số hiện thời nếu dương thì cộng
giá trị đó vào tổng S.
3. Dừng khi không còn số nào nữa trong dãy. Giá trị S chính là tổng cần
tìm.
b) Dùng ngôn ngữ tựa Pascal:
Procedure max (a
1
, a
2
, ..., a
n
: Item);
Begin
S:= 0;
for i:= 1 to n
if a
i
>0 then S:= S+ a
i
;
{S là tổng các phần tử dương}
End;
2.2.3. Các đặc trưng của thuật toán
Tính hữu hạn: Sau một số hữu hạn lần thực hiện các thao tác thuật
toán phải kết thúc;

2
, ..., a
n
và giá trị x
Output: Nghiệm là i nếu x=a
i
và là 0 nếu x không có mặt trong dãy.
2.3.2. Thuật toán tìm kiếm tuyến tính: Tìm kiếm tuyến tính hay tìm
kiếm tuần tự. Tư tưởng thuật toán là bắt đầu bằng việc so sánh x với a
1
; khi
x=a
1
, nghiệm là vị trí a
1
, tức là 1; khi x≠a
1
, so sánh x với a
2
. Nếu x=a
2
, nghiệm
là vị trí của a
2
, tức là 2. Khi x≠a
2
, so sánh x với a
3
. Tiếp tục quá trình này bằng
cách tuần tự so sánh x với mỗi số hạng của dãy cho tới khi tìm được số hạng

6,1,3,5,8}
Bước 2: k=3, so sánh x với k, x>k ta tìm kiếm x ở nửa sau {3,5,8}
Bước 3: k=5, so sánh x với k, x=k ta tìm được x kết thúc.
Dùng ngôn ngữ tựa Pascal: {Thuật toán áp dụng với dãy tăng dần}
Procedure tìm kiếm nhị phân (x: Item, a
1
,a
2
,...,an: Item);
Begin
d := 1 {d là điểm đầu của đoạn tìm kiếm}
c := n {c là điểm cuối của đoạn tìm kiếm}
while (d <c) do
begin
m:= [(d+c)/2]
if x>a
m
then d:=m+1
else c := m-1
end
if x = ai then kq := i
else kq := 0
{kq là vị trí của số hạng bằng x hoặc 0 nếu không tìm thấy x}
End;
2.4. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
2.4.1 Khái niệm về độ phức tạp của một thuật toán
Thước đo hiệu quả của một thuật toán là thời gian mà máy tính sử dụng
để giải bài toán theo thuật toán đang xét, khi các giá trị đầu vào có một kích
thước xác định. Một thước đo thứ hai là dung lượng bộ nhớ đòi hỏi để thực
hiện thuật toán khi các giá trị đầu vào có kích thước xác định. Các vấn đề như

coi kích thước của dữ liệu nhập là số lượng phần tử của dãy số, tức là n. Nếu
coi mỗi lần so sánh hai số của thuật toán đòi hỏi một đơn vị thời gian (giây
chẳng hạn) thì thời gian thực hiện thuật toán trong trường hợp xấu nhất là n-1
giây. Với dãy 64 số, thời gian thực hiện thuật toán nhiều lắm là 63 giây. Ta
nói độ phức tạp là n-1
Ví dụ: Thuật toán về bài toán “Tháp Hà Nội”
Bài toán “Tháp Hà Nội” như sau: Có ba cọc A, B, C bằng kim cương và
64 cái đĩa bằng vàng các đĩa có đường kính đôi một khác nhau. Nguyên tắc
chuyển đĩa là: mỗi lần chỉ chuyển một đĩa và không được chồng đĩa to lên trên
đĩa nhỏ hơn nó. Ban đầu, cả 64 đĩa được đặt chồng lên nhau ở cột A; hai cột
B, C trống. Vấn đề là phải chuyển cả 64 đĩa đó từ cột A sang cột B lấy cột C
làm trung gian.
Xét trò chơi với n đĩa ban đầu ở cọc A (cọc B và C trống). Gọi S
n
là số
lần chuyển đĩa để chơi xong trò chơi với n đĩa.
Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH

27

Nếu n=1 thì rõ ràng là S
1
=1.
Nếu n>1 thì trước hết ta chuyển n-1 đĩa bên trên sang cọc B (giữ yên
đĩa thứ n ở dưới cùng của cọc A). Số lần chuyển n-1 đĩa là S
n-1
. Sau đó ta
chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng, ta chuyển n-1 đĩa từ cọc B
sang cọc C (số lần chuyển là S
n-1

thuật toán xấp xỉ 585 tỉ năm!. Ta nói độ phức tạp là 2
n
−1
Hai thí dụ trên cho thấy rằng: một thuật toán phải kết thúc sau một số
hữu hạn bước, nhưng nếu số hữu hạn này quá lớn thì thuật toán không thể
thực hiện được trong thực tế.
2.4.2. So sánh độ phức tạp của các thuật toán
Một bài toán thường có nhiều cách giải, có nhiều thuật toán để giải, các
thuật toán đó có độ phức tạp khác nhau.
Xét bài toán:
Tính giá trị của đa thức P(x)=a
n
x
n
+a
n-1
x
n-1
+ ... +a
1
x+a
0
tại x
0
.
Thuật toán 1:
Procedure tính giá trị của đa thức (a
0
, a
1

Ta có thể tính P(x) theo thuật toán sau: