[email protected]
TIN HỌC ðẠI CƯƠNG
Chương 3: Lý thuyết thuật toán
Tin học đại cương - Chương 3
2
[email protected]
Nội dung
1. Khái niệm thuật toán.
2. Chương trình máy tính, ngôn ngữ lập trình.
3. Tính chất của thuật toán.
4. Các cách biểu diễn thuật toán.
5. Thiết kế và phân tích thuật toán.
6. Đệ quy và thuật toán đệ quy.
7. Một số bài toán tìm kiếm, sắp xếp đơn giản.
8. Bài tập.
Tin học đại cương - Chương 3
3
[email protected]
Tin học Đại cương - Chương 3 3/51
Thuật toán là gì?
Thuật toán, thuật giải, hay giải thuật, ñều dùng để
chỉ một thuật ngữ tiếng Anh có tên là
ALGORITHM.
Chúng ta sẽ tìm hiểu:
q Thuật toán theo cách hiểu thông thường
q Các thao tác trong thuật toán
q Định nghĩa thuật toán trong tin học
Tin học đại cương - Chương 3
4
[email protected]
Thuật toán - cách hiểu thông thường

Tin học đại cương - Chương 3
7
[email protected]
Trò chơi 5 quân bài (tt)
So sánh Quân bài lớn nhất:
Tin học đại cương - Chương 3
8
[email protected]
Trò chơi 5 quân bài (tt)
So sánh Quân bài lớn nhất:
Tin học đại cương - Chương 3
9
[email protected]
Trò chơi 5 quân bài (tt)
So sánh Quân bài lớn nhất:
Tin học đại cương - Chương 3
10
[email protected]
Trò chơi 5 quân bài (tt)
So sánh Quân bài lớn nhất:
Tin học đại cương - Chương 3
11
[email protected]
Các thao tác trong thuật toán
q Thao tác tuần tự (sequential operation): Một công
việc đã được xác định rõ ràng, thực hiện xong thì
chuyển sang công việc khác.
q Thao tác
kiểm tra điều kiện (conditional operation):
Kiểm tra điều kiện đưa ra có thoả mãn hay không

q Giải thuật là bất cứ thủ tục tính toán (computational
procedure
) nào nhận các dữ liệu vào (input) và trả
thông tin ra (
output).
q Giải thuật là dãy các thao tác xử lý dữ liệu để có
được thông tin mong muốn.
q Ví dụ: “Bài toán sắp xếp dãy số”
– Input: Dãy số.
– Output: Dãy số ñã sắp xếp.
INPUT ALGORITHM OUTPUT
Tin học đại cương - Chương 3
14
[email protected]
Chương trình máy tính
q Máy tính?
– Làm theo “lệnh” của con người.
– Điểm mạnh là tính toán với tốc độ cao
(hàng tỷ phép tính trên giây).
q Làm thế nào để “ra lệnh” cho máy
tính?
– Lập chương trình cho máy tính.
q Chương trình ?
– Nói cho máy tính biết phải làm gì, như
thế nào,…
Tin học đại cương - Chương 3
15
[email protected]
Ngôn ngữ lập trình
q Muốn “ra lệnh” cho máy tính:

ALGORITHMSDATA STRUCTURES PROGRAM
+ =
Tin học đại cương - Chương 3
17
[email protected]
Chương trình viết bằng ngôn ngữ C
Tin học đại cương - Chương 3
18
[email protected]
“Giải thuật nấu cơm”
q Giải thuật nấu cơm (đề phòng trường hợp có thêm khách)
– Bước 0: Ước lượng số gạo cần thiết.
– Bước 1: Vo gạo.
– Bước 2: Cho gạo và nước thích hợp vào nồi cơm điện(NCĐ).
– Bước 3: Cắm điện, chuyển chế ñộ “
cook”.
– Bước 4: Chờ ñến khi NCĐ chuyển sang chế ñộ “
warm”.
– Bước 5: Chờ thêm 10 phút nữa.
– Bước 6: Cơm chín. Nếu không có thêm khách thì sang bước 8.
– Bước 7: Quay lại bước 0.
– Bước 8: Kết thúc.
q Nhận xét: Bước 6 là thao tác kiểm tra điều kiện và bước 7 là thao
tác lặp.
Tin học đại cương - Chương 3
19
[email protected]
Các tính chất của thuật toán
q Tính hữu hạn dừng
– Một thuật toán bất kỳ phải đảm bảo dừng sau một số

q Có những bài toán không có giải thuật tổng quát đ ể
giải quyết.
q Có những bài toán chưa có giải thuật hữu hiệu để
giải quyết.
q Có những bài toán chưa có giải thuật tìm lời giải.
Tin học đại cương - Chương 3
22
[email protected]
Các cách biểu diễn thuật toán
q Liệt kê từng bước
q Sơ đồ khối
q Sử dụng giả ngôn ngữ lập trình
Tin học đại cương - Chương 3
23
[email protected]
Phương pháp liệt kê từng bước
q Các thao tác của giải thuật được liệt kê từng bước.
q Tại mỗi bước, sử dụng ngôn ngữ tự nhiên ñể diễn tả công
việc phải làm.
q Bước đứng trước (có số thứ tự nhỏ hơn) được thực hiện
trước.
q Ưu nhược điểm
– Dễ hiểu, dễ làm
– Phụ thuộc vào “cách hành văn” của người diễn đạt
– Với những giải thuật phức tạp, cách diễn đạt này trở nên rườm
rà
– …
Tin học đại cương - Chương 3
24
[email protected]

Biểu diễn thuật toán bằng sơ đồ khối
q Sử dụng các hình khối để minh hoạ cho các lệnh hay thao
tác.
q S
ử dụng mũi tên để diễn đạt thứ tự thực hiện.
q Đây là cách di
ễn đạt khoa học, có tính nhất quán cao.
q Các hình khối cơ bản
– Khối bắt đầu.
– Khối kết thúc.
– Khối thao tác cụ thể.
– Khối kiểm tra điều kiện.
– Khối vào/ra dữ liệu.
– Khối gọi chương trình con.
q Các ký pháp.
Tin học đại cương - Chương 3
26
[email protected]
Các hình khối cơ bản
q Khối bắt đầu và kết thúc
q Thực hiện công việc A
q Vào/ra d
ữ liệu
q Gọi chương trình con A (ít
dùng)
q Kiểm tra điều kiện
– Tuỳ thuộc điều kiện (Đúng
hay Sai) mà rẽ nhánh thích
hợp
A

• C = 2*(a+b)
– B3. Tính diện tích
• S = a*b
– B4. In chu vi C
– B5. In diện tích S
– Kết thúc
q Sơ đồ khối
Begin
End
§äc c¹nh a,b
C := 2*(a+b)
In ra C,S
S := a*b
Tin học đại cương - Chương 3
29
[email protected]
Lưu đồ thuật giải tính tổng N số tự nhiên ñầu tiên
q Cách 1 q Cách 2
Tin học đại cương - Chương 3
30
[email protected]
Tính chu vi, diện tích tam giác
q Phương pháp liệt kê
– B1. Nhập cạnh a,b,c
– B2. Kiểm tra xem a,b,c có phải ba
cạnh tam giác không
• Nếu (a+b>c) và (b+c>a) và
(a+c>b) thì sang bước 3
• Nếu không thì thông báo
“không tạo thành tam giác” và

Giải thuật tính tổng N số tự nhiên ñầu tiên
Nhập N
i:=0
S:=0
REPEAT
S:=S+i
i:=i+1
UNTIL (i>N)
In S
Tin học đại cương - Chương 3
33
[email protected]
Thiết kế và phân tích thuật toán
q Quá trình viết chương trình giải bài toán:
– Phân tích yêu cầu bài toán
– Thiết kế giải thuật
– Viết chương trình
– Chạy thử, đánh giá
q Thiết kế giải thuật là từ yêu cầu của một bài toán, diễn đạt một giải
thuật giải quyết bài toán đó.
– Mô-đun hoá việc giải quyết bài toán.
– Tinh chỉnh từng bước.
q Phân tích giải thuật
– Xem xét các tiêu chuẩn của giải thuật có ñược thoả mãn không, nếu có
thì ñến mức độ nào.
Tin học đại cương - Chương 3
34
[email protected]
Thiết kế từ trên xuống
q Các bài toán lớn đòi hỏi giải

Tin học đại cương - Chương 3
36
[email protected]
Phương pháp tinh chỉnh từng bước
q Phương pháp tinh chỉnh từng bước (stepwise
refinement)
– Ban đầu, sử dụng ngôn ngữ tự nhiên ñể diễn tả
những công việc chính của giải thuật.
– Các bước sau, các công việc được chi tiết hoá dần
dần, ngôn ngữ tự nhiên ñược thay thế dần dần
bằng giả ngôn ngữ.
– Cuối cùng, giả ngôn ngữ ñược chuyển sang ngôn
ngữ lập trình
q Đặc điểm
– Thể hiện rõ ý tưởng thiết kế từ trên xuống
– Gắn liền việc thiết kế giải thuật với việc lập trình
Tin học đại cương - Chương 3
37
[email protected]
Sắp xếp dãy theo thứ tự tăng dần
q Phác thảo “thô” với những “ý tưởng cơ bản”
– “Từ dãy các số chưa ñược sắp xếp, tìm số nhỏ nhất và ñưa lên ñầu”
– Lặp lại quy trình trên tới khi dãy chưa được sắp xếp trở thành rỗng.
q Ban đầu, dãy chưa sắp xếp là dãy ñã cho, dãy đã sắp xếp là
rỗng.
q Lưu trữ dãy bằng “mảng” (danh sách các số), ñưa số nhỏ nhất
(a
j
) lên đầu danh sách là ñổi chỗ nó với số ñầu tiên.
q Đổi chỗ

q Một đối tượng là ñệ quy nếu nó bao gồm chính nó hoặc
được định nghĩa bởi chính nó.
q Ví dụ:
– Trong chương trình thời sự trên vô tuyến, ñôi khi ta thấy lại hình
ảnh của màn hình phía sau phát thanh viên.
– Định nghĩa số tự nhiên:
• 1 là số tự nhiên
• N là số tự nhiên nếu N-1 là số tự nhiên
– Định nghĩa giai thừa:
• 0! = 1
• N! = N(N-1)!
Tin học đại cương - Chương 3
40
[email protected]
Giải thuật đệ quy
q Lời giải của bài toán T có ñược dựa trên lời giải một bài toán
T’ nào đó thì l
ời giải đó là một lời giải đệ quy và giải thuật đó
g
ọi là giải thuật đệ quy.
q Bài toán T’ ph
ải nhỏ hơn bài toán T.
q Ví dụ “Bài toán tính N!”
– T
n
= tính N!
• Tính T
n-1
= tính (N-1)!
– Tính T

ỗi lần chỉ ñược chuyển một đĩa từ
cọc này sang cọc khác.
– Không đ
ược xếp đĩa to lên trên đĩa bé.
2
1
N
A
C
B
Tin học đại cương - Chương 3
42
[email protected]
Bài toán “Tháp Hà Nội” – Lời giải đệ quy
q Đánh số các đĩa theo thứ tự từ dưới lên
q Nếu N = 1
– Chuyển đĩa duy nhất (đĩa 1) từ cột A sang cột C
q Nếu N = 2
– Chuyển đĩa 2 từ cột A sang cột B
– Chuyển đĩa 1 từ cột A sang cột C
– Chuyển đĩa 2 từ cột B sang cột C
q N bất kỳ
– Chuyển N-1 đĩa trên cùng từ cọc A sang cọc B
– Chuyển đĩa 1 từ cọc A sang cọc C
– Chuyển N-1 đĩa từ cọc B sang cọc C
Tin học đại cương - Chương 3
43
[email protected]
Một số bài toán tìm kiếm, sắp xếp
q Tìm giá trị lớn nhất, nhỏ nhất của dãy số?

Tin học đại cương - Chương 3
45
[email protected]
Lưu đồ thuật giải (tìm giá trị lớn nhất)
Max := A[1]
i := 2
BEGIN
Nhập N, A
i := i+1
END
In ra Max
i > N Max<A[i]
Max := A[i]
Đ
S
Đ
S


 A là dãy số có N phần tử
Lần lượt so sánh và tìm
phần tử giả ñịnh mới 


Giả ñịnh giá trị lớn nhất
là phần tử ñầu tiên 


Kết thúc dãy, phần tử giả
định là giá trị lớn nhất 

Found := True
Đ
S
Đ
S
Found
Đ
In “Không thấy”
S
A - Dãy số có N phần tử
X - Phần tử cần tìm
Vòng lặp
tìm kiếm



Tin học đại cương - Chương 3
48
[email protected]
Sắp xếp dãy số
q Ý tưởng
– Tìm phần tử nhỏ nhất (lớn nhất) trong
dãy.
– Đ
ổi chỗ phần tử ñó với phần tử ñầu tiên
trong dãy (v
ị trí a), dãy đầu tiên sẽ ñược
chia làm 2 ph
ần.
• Phần đầu: tính từ vị trí a về ñầu dãy, ñã



 a là dãy số có n phần tử


 Đổi chỗ a[i] và a[j]
Vòng lặp sắp xếp 


Đ
S


 Bắt đầu từ phần tử ñầu tiên của dãy
i := i+1



Chuyển
sang sắp
xếp dãy tiếp
theo
Đến khi không
còn dãy nào
chưa sắp xếp



Tin học đại cương - Chương 3
50