Trư
ờng ðại học Nô
ng nghi
ệp 1
-
Giáo trình
Tin h
ọc

ñ
ại
c
ươ
ng

102102

CHƯƠNG VI: GIẢI THUẬT

1. Khái niệm giải thuật (Algorithms)

- Khi cần giải quyết một bài toán trong thực tế với sự trợ giúp của máy tính ñiện tử ta

Bước thực hiện a b Kiểm tra ñiều kiện a=b
Bước 1 20 32 Sai
Bước 2 20 12
Bước 1 20 12 Sai
Bước 2 8 12
Bước 1 8 12 Sai
Bước 2 8 4
Bước 1 8 4 Sai
Bước 2 4 4
Bước 1 4 4 ðúng

Kết quả là: (20,32)=4
Trư
ờng ðại học Nô
ng nghi
ệp 1
-
Giáo trình
Tin h
ọc

ñ
ại
c
ươ
ng


Ví dụ: Có 31 que diêm, người và máy thay nhau bốc. Mỗi lần bốc từ 1 ñến 4 que. Ai
phải bốc sau cùng là thua. Hãy xây dựng thuật giải sao cho máy bốc trước bao giờ cũng thua.
Bước 1: Máy bốc ngẫu nhiên x que diêm (1≤x≤4)
Bước 2: Người bốc (5- x) que, tổng số que diêm giảm ñi 5 que. Nếu số que diêm còn lại
là 1 que thì chuyển sang bước 3, nếu không thì quay lại thực hiện bước 1
Bước 3: Tuyên bố người thắng cuộc

3.2. Cách 2: Sử dụng lưu ñồ
Sử dụng phương tiện hình học cũng là một cách tốt ñể minh hoạ giải thuật của 1 bài
toán. Trong lưu ñồ người ta sử dụng các hình sau, với kí hiệu + là ñúng, - là sai.

- + Khi iu kin

Khi lnh


gt1

K

a. Cấu trúc rẽ nhánh
- Rẽ nhánh dạng khuyết: if <ñk thoả mãn> then <thực hiện lệnh> (hình 1)
- Rẽ nhánh dạng ñủ: if <ñk thoả mãn> then <thực hiện lệnh 1>
else <thực hiện lệnh 2> (hình 2)
- Cấu lệnh lựa chọn:
case <biểu thức nhận>
Giá trị 1: Thực hiện lệnh 1
Giá trị 2: Thực hiện lệnh 2

Giá trị n: Thực hiện lệnh n
else Thực hiện lệnh (n+1)
end

- - -

+ + +


Lnh (n+1)

Lnh 1

Lnh

K

Lnh

Lnh

Lnh

Lnh 1

Lnh

K
K

Lnh 2

Hình 1

Hình 2



105

3.3 Cách 3: Sử dụng giả ngôn ngữ có cấu trúc tựa ngôn ngữ lập trình bậc cao
Là phương pháp diễn tả giải thuật dựa vào các cấu trúc ñiều khiển, cùng với các từ khoá
của một ngôn ngữ lập trình bậc cao nào ñó. Trong giáo trình này ta sẽ sử dụng ngôn ngữ tựa
Pascal ñể diễn tả giải thuật. Cách diễn ñạt này ñã tiếp cận gần hơn với ngôn ngữ lập trình.
Ví dụ: Với thuật giải tìm UCLN ở trên ta có thể diễn ñạt như sau
while a≠b
begin
if a>b then thay a bởi a-b
else thay b bởi b-a
end
write ước chung lớn nhất là a

4. Thiết kế giải thuật

4.1. Mô-ñun hoá và việc giải quyết bài toán

Những bài toán ta gặp trong thực tế thường là phức tạp, trong trường hợp ñó người ta
thường chia bài toán thành những bài toán nhỏ và dễ giải quyết hơn. Nghĩa là coi bài toán ban
ñầu là Mô- ñun chính, ta chia nó thành các Mô- ñun con, và mỗi Mô- ñun con này có thể lại
ñược chia thành các Mô- ñun nhỏ hơn Cách giải quyết bài toán như vậy người ta thường gọi
là chiến thuật "Chia ñể trị"(divide and conquer).
Trong khi lập trình việc chia chương trình chính thành các chương trình con thể hiện
tính có cấu trúc của ngôn ngữ lập trình về mặt chương trình



ñ
ại
c
ươ
ng

106106

- Có ñôi lúc viêc kiểm tra chương trình phải thực hiện thủ công, kiểm tra từng bước,
từng thủ tục của chương trình chính. Kỹ thuật này ñược gọi là “ñi bộ qua chương
trình”(Walking through the program)
- Quan tâm ñặc biệt tới thời gian thực hiện chương trình, thời gian thực hiện phụ thuộc
rất nhiều vào việc tổ chức dữ liệu ñưa vào (kích thước dữ liệu).

5. Giải thuật sắp xếp (Sorting)

Sắp xếp là một trong số yêu cầu thường xuyên xuất hiện trong quá trình xử lý số liệu.
Bản chất của thuật giải sắp xếp là bố trí lại vị trí của số liệu theo thứ tự tăng dần hoặc giảm
dần. Có nhiều giải thuật sắp xếp trong tin học, trong giáo trình này chúng ta sẽ ñề cập ñến một
số thuật giải ñơn giản ñó là sắp xếp lựa chọn (selection sort), sắp xếp chèn (insertion sort) và

end
end
Ví dụ
Dãy số ban ñầu : 3 6 -2 7 5
i=1 -2 6 3 7 5
i=2 -2 3 6 7 5
i=3 -2 3 5 7 6
i=4 -2 3 5 6 7

5.2 Sắp xếp chèn (insertion sort)

Thuật giải chèn ñược diễn tả như sau: Xét lần lượt từng phần tử và chèn vào vị trí thích
hợp của phần tử ñó trong số các phần tử ñã xét trước ñó. Cụ thể giả sử ñã có (i-1) phần tử
ñược sắp xếp ñúng vị trí, ñể chèn phần tử thư i vào ñúng vị trí ta so sánh lần lượt với các phần
tử thứ (i-1), (i-2), khi tìm ñược vị trí ñúng thì chèn phần tử thứ i ñó vào. Trư
ờng ðại học Nô
ng nghi
ệp 1
-
Giáo trình
Tin h
ọc

ñ

, j:=j-1 end
a
j
:=k
end
end

Ví dụ
Dãy số ban ñầu : 3 6 -2 7 5
i=2 3 6 -2 7 5
i=3 -2 3 6 7 5
i=4 -2 3 6 7 5
i=5 -2 3 5 6 7

5.3 Sắp xếp nổi bọt (bubble sort)

Thuật giải này còn có tên gọi khác là sắp xếp bằng cách ñổi chỗ trực tiếp (exchange
sort), thuật giải nổi bọt ñược diễn tả như sau: Duyệt dãy số theo thứ tự từ phải sang trái nếu
hai phần tử kề cận ngược thứ tự thì ñổi chỗ cho nhau. Như vậy sau lượt duyệt ñầu tiên phần tử
ñầu tiên sẽ là phần tử nhỏ nhất, sau lượt thứ hai phần tử nhỏ thứ hai ñược chuyển lên vị trí thứ
hai cứ như vậy dãy số sẽ ñược sắp xếp tăng dần.

procedure Bubble_Sort
begin
for i:=1 to n-1 do
for j:=n downto i+1 do
if a
j
<a
j-1


ñ
ại
c
ươ
ng

108108

6.1 Tìm kiếm tuần tự (sequential searching)
ðây là thuật giải tìm kiếm ñơn giản nhất, ta sẽ duyệt tuần tự dãy số, thuật giải sẽ kết
thúc khi tìm thấy phần tử bằng giá trị X hoặc khi duyệt hết dãy số nhưng không có phần tử
nào có giá trị là X
procedure Sequential_Searching
begin
i:=1
while a
i
≠ X do i:=i+1
if i=n+1 then không có phần tử cần tìm
else vị trí phần tử cần tìm là i

then vị trí cần tìm là mid
else không có phần tử cần tìm
end
Ví dụ: Tìm phần tử 28 trong dãy số sau
[4 15 28 33
67 99 103]
Lặp lần 1 [4 15
28]
Lặp lần 2 [28]

7. Giải thuật ñệ quy

7.1. Khái niệm ñệ qui

Một ñối tượng ñược gọi là ñệ qui nếu nó bao gồm một phần của chính nó hay ñược ñịnh
nghĩa bởi chính nó.
Trong khi thiết kế giải thuật ta thường thiết kế dưới dạng các mô- ñun. Khi giải thuật
ñược cài ñặt thành chương trình thí các mô- ñun sẽ tương ứng với các chương trình con (hàm-
function và thủ tục- procedure),
Chương trình con ñược gọi là ñệ qui nếu trong thân của nó có lời gọi trực tiếp hoặc gián
tiếp ñến chính bản thân nó.
ðệ qui có ý nghĩa ñặc biệt quan trọng trong các ñịnh nghĩa toán học
Trư
ờng ðại học Nô
ng nghi
ệp 1
-
Giáo trình
Tin h
ọc

Trong ví dụ ñịnh nghĩa n! thì trường hợp suy biến ñịnh nghĩa 0!, phần qui nạp ñịnh
nghĩa n! qua các giá trị của n và giá trị của (n-1)!
Dễ nhận xét, nếu (n-1)! ñã tính ñược thì n! sẽ dễ dàng tính ñược. Với cách suy diễn
tương tự, (n-1)! sẽ tính ñược nếu như (n-2)! ñã tính ñược cuối cùng 1! sẽ tính ñược nếu 0!
ñã tính ñược. Ta thấy rằng 0! ñã cho trong ñịnh nghĩa. Do vậy ñi ngược từ cuối, vì 0! ñã tính
ñược nên 1! cũng tính ñược, ,sau khi (n-1)! ñã có ta sẽ nhận ñược n!
Minh hoạ: Tính 3!
3!=3*2!=3*2=6

2!=2*1!=2*1=2

1!=1*0!=1*1=1 Giải thuật ñược viết dưới dạng thủ tục hàm (tựa Pascal) như sau:
function giaithua(n)
begin
if n=0 then giaithua:=1 (* trường hợp suy biến*)
else giaithua:=n*giaithua(n-1) (* phần ñệ qui*)
end
Chú ý: Không phải lúc nào tính ñệ qui trong cách giải bài toán cũng thể hiện rõ nét và
dễ phát hiện như ví dụ trên. Do ñó muốn biết giải thuật của một bài toán có thể thiết kế dưới
dạng giải thuật ñệ qui ñược hay không? Có thể thấy câu trả lời qua việc trả lời các câu hỏi sau
: + Có thể ñịnh nghĩa ñược bài toán dưới dạng một bài toán cùng loại nhưng “nhỏ” hơn
không?
+ Kích thước của bài toán sẽ giảm ñi ở mỗi bước gọi ñệ qui như thế nào?
+ Trường hợp nào của bài toán ñược coi là trường hợp suy biến?

7. 2. Ví dụ về giải thuật ñệ qui : Bài toán tháp Hà Nội
Bài toán Tháp Hà Nội là một ví dụ cổ ñiển cho thấy thuật toán ñệ qui là ñặc biệt thích - Khi chuyển một ñĩa, nó phải ñược ñặt vào một trong 3 cọc ở trên
Hãy chỉ ra thứ tự các bước chuyển.
A B C
Một truyền thuyết cho rằng các thầy tu ở ðiện Bramah ñược cho một bài toán ñố với
một nền vàng có 3 kim vàng trên 1 cọc có 64 ñĩa vàng. Khi họ chuyển các ñĩa vàng theo các
luật của bài toán trên, nếu mỗi giây chuyển ñược một ñĩa và họ bắt ñầu công việc từ năm 0,
ñến khi hoàn thành công việc thì sẽ là ngày tận thế.
Những người mới bắt ñầu có thể giải bài toán một cách dễ dàng với số các ñĩa là bé,
nhưng họ sẽ rất khó khăn khi số ñĩa tăng lên 7,8 và lớn hơn. Tuy nhiên với một nhà lập trình
thì có thể giải bài toán một cách không mấy khó khăn.
Cách giải: Nếu có một ñĩa, chuyển nó từ cọc A sang cọc C. Bài toán giải ñược với n=1
Giả sử rằng bài toán có nghiệm với n-1 ñĩa , nghiệm với n ñĩa có thể nhận ñược một
cách dễ dàng nhờ dùng phép ñệ quy:
+ Chuyển n-1 ñĩa trên cùng ở cọc A sang cọc B, dùng cọc C làm trung chuyển
+ Chuyển ñĩa còn lại ở cọc A sang cọc C
+ Chuyển n-1 từ cọc B sang cọc C, dùng cọc A làm trung chuyển
Ta có thể viết giải thuật của bài toán Tháp Hà Nội như sau:

procedure Move(n,A,B,C)
(* Chuyển n ñĩa từ cọc A sang cọc C, dùng cọc B làm trung chuyển*)


ñ
ại
c
ươ
ng

111111

Bài tập chương VI: Thuật giải

Viết giải thuật cho các bài toán sau:

1. Tính n giai thừa: n! =1.2 n với n>1
2. Tính các tổng: S=1/2 + 1/4 + + 1/(2k)
Q=1.1!+2.2!+ +n.n!
3. Tìm và in ra tất cả các số chính phương nhỏ hơn một số cho trước, cho biết có bao nhiêu số
chính phương như vậy.
4. Viết chương trình giải bài toán cổ: " Vừa gà vừa chó, bó lại cho tròn, ba mươi sáu con, một
trăm chân chẵn. Hỏi có bao nhiêu gà, bao nhiêu chó?"
5. Viết chương trình tìm ước số chung lớn nhất của 2 số nguyên dương cho trước.

10. Viết chương trình tìm và in ra màn hình các số nguyên tố nhỏ hơn một số cho trước.
11. Cho dãy số sau: a
1
,a
2
, ,a
n
.

Viết chương trình tìm phần tử lớn nhất, phần tử nhỏ nhất
của dãy số ñó.
12. Cho dãy số sau: a
1
,a
2
, ,a
n
.

Viết chương trình sắp xếp dãy theo thứ tự tăng dần .
13. Cho dãy số sau: a
1
,a
2
, ,a
n
.

Viết chương trình ñếm số phần tử dương và xoá ñi phần tử
thứ m trong dãy (m<=n) .