SGK Tin Học 10 - §4. BÀI TOÁN VÀ THUẬT TOÁN

§4. BÀI TOÁN VÀ THUẬT TOÁN
Khái niệm bài toán
Trong phạm vi tin học, ta có thể quan niệm bài toán là một việc nào đó ta muốn máy tính thực hiện.
Những việc như đưa một dòng chữ ra màn hình, giải phương trình bậc hai, quản lí cán bộ của một cơ quan,... là những ví dụ về bài toán.
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 trình bày rõ Input và Output của bài toán đó và mối quan hệ giữa Input và Output.
Ví dụ 1. Bài toán tìm ước chung lớn nhất của hai số nguyên dương.
Input: Hai số nguyên dương M và N’,
Output: Ước chung lớn nhất của M và N.
Ví dụ 2. Bài toán tìm nghiệm của phương trình bậc hai ax2 + bx + c = 0 (ứ 0).
Input: Các số thực a, b,c(a* 0);
Output: Tất cả các số thực X thoả mãn ax + bx + c = 0.
Ớ đây, Output có thể là một hoặc hai số thực hoặc câu trả lời không có số thực nào như vậy.
Ví dụ 3. Bài toán kiểm tra tính nguyên tố.
Input: Số nguyên dương N;
Output: "N là số nguyên tố" hoặc 'W không là số nguyên tố".
Ví dụ 4. Bài toán xếp loại học tập của một lớp.
Input: Bảng điểm của học sinh trong lớp;
Output: Bảng xếp loại học lực.
Qua các ví dụ trên, ta thấy các bài toán được cấu tạo bởi hai thành phần cơ bản:
Input: Các thông tin đã có;
Output: Các thông tin cần tìm từ Input.
Khái niệm thuật toán
Al-Khwarizmi, nhà toán học thế kỉ IX - người có ảnh hưởng lớn đến sự hình thành thuật ngữ "Algorithm"
Việc cho một bài toán là mô tả rõ Input cho trước và Output cần tìm. Vấn đề là: Làm thế nào để tìm ra Output?
Trước hết cần lưu ý rằng trong toán học có một xu hướng nghiên cứu định tính các bài toán, có nghĩa là người ta có thể chỉ cần chứng minh sự tồn tại của lời giải và không cần chỉ ra một cách tường minh cách tìm lời giải đó.
Việc chỉ ra tường minh một cách tìm Output của bài toán được gọi là một thuật toán (algorithm) giải bài toán đó. Có nhiều định nghĩa khác nhau về thuật toán, dưới đây là một định nghĩa thường dùng.
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 ấy, từ Input của bài toán, ta nhận được Output cần tìm.
Ví dụ. Tìm giá trị lớn nhất của một dãy sô' nguyên • Xác định bài toán
-Input: Số nguyên dương N và dãy N số nguyên aN. - Output: Giá trị lớn nhất Max của dãy số.
• Ý tưởng: - Khởi tạo giá trị Max = ữp
- Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ứ,- với giá trị Max, nếu ứ, > Max thì Max nhận giá trị mới là Oị.
3- TIN HỌC 10(C) -A
Hình 21
K
34
• Thuật toán. Thuật toán giải bài toán này có thể được mô tả theo cách liệt kê như sau:
Bước 1. Nhập N và dãy aN;
Bước 2. Max <— ứj, i <— 2;
Bước 3. Nếu i > N thì đưa ra giá trị Max rồi kết thúc; Bước 4.
Bước 4.1. Nếu aị > Max thì Max <— Bước 4.2. i <— z + 1 rồi quay lại bước 3;
Ghi chú: - Trong thuật toán trên, / là biến chỉ số và có giá trị nguyên thay đổi từ 2 đến N + 1.
- Mũi tên <- trong thuật toán trên được hiểu là gán giá trị của biểu thức bên phải cho biến ở bên trái mũi tên. Ví dụ /■<-/'+ 1 được hiểu là đặt cho biến i giá trị mới bằng giá trị trước đó tăng thêm 1 đơn vị.
Ngoài cách liệt kê dãy các thao tác như trên, thuật toán còn có thể được diễn tả bằng sơ đồ khối. Trong sơ đồ khối, người ta dùng một số khối, đường có mũi tên với:
Hình thoi o thể hiện thao tác so sánh;
Hình chữ nhật I I thể hiện các phép tính toán;
Hình ô van CD thể hiện thao tác nhập, xuất dữ liệu;
Các mũi tên —► quy định trình tự thực hiện các thao tác.
Với bài toán ở ví dụ trên, thuật toán có thể được diễn tả bằng sơ đồ khối như hình 21.
Dưới đây là ví dụ mô phỏng việc thực hiện thuật toán trên với N = 11 và dãy số: 5, 1, 4, 7, 6, 3, 15, 8, 4, 9, 12.
3- TIN HỌC 10(C) -B
5
1
4
7
6
3
15
8
4
9
12
2
3
4
5
6
7
8
9
10
11
12
5
5
5
7
7
7
15
15
15
15
15
Dãy số
Max
Các thao tác trong thùật toán phải được mô tả đủ chi tiết để đối tượng thực hiện thuật toán có thể thực hiện được. Ví dụ, trong thuật toán giải phương trình bậc hai với ba hệ số a, b, c cần tính đại lượng A. Tuỳ thuộc đối tượng thực hiện mà việc tính A có thể được mô tả chi tiết khác nhau, chẳng hạn: '
Với đối tượng biết công thức tính A thì chỉ cần mô tả một bước là: Tính A;
Với đối tượng không biết công thức tính A thì cần phải mô tả chi tiết hơn, chẳng hạn:
Bước 1. Tính ỉ>2;
Bước 2. Tính 4ac\
Bước 3. Giá trị A là kết quả của bước 1 trừ đi kết quả của bước 2.
Dù đối tượng thực hiện không hề biết khái niệm A là gì nhưng thực hiện theo các bước nêu trên thì vẫn nhận được giá trị A cần tính.
Qua định nghĩa, ta thấy thuật toán có các tính chất sau:
Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác;
Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo;
Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.
Ví dụ. Với thuật toán tìm Max đã xét:
Tính dừng: Vì giá trị của i mỗi lần tăng lên 1 nên sau N lần thì i > N, khi đó kết quả phép so sánh ở bước 3 xác định việc đưa ra giá trị Max rồi kết thúc.
Tính xác định: Thứ tự thực hiện các bước của thuật toán được mặc định là tuần tự nên sau bước 1 là bước 2, sau bước 2 là bước 3. Kết quả các phép so sánh trong bước 3 và bước 4 đều xác định duy nhất bước tiếp theo cần thực hiện.
Tính đúng đắn: Vì thuật toán so sánh Max với từng số hạng của dãy số và thực hiện Max Max nên sau khi so sánh hết N số hạng của dãy thì Max là giá trị lớn nhất.
Một số ví dụ vế thuật toán
Ví dụ 1. Kiểm tra tính nguyên tố của một số nguyên dương
Xác định bài toán
-Input: N là một số nguyên dương;
Output: "N là số nguyên tố" hoặc "V không là số nguyên tố".
Ý tưởng: Ta nhớ lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu nó có đúng hai ước số khác nhau là 1 và chính nó. Từ định nghĩa đó, ta suy ra:
Nếu N = 1 thì N không là số nguyên tố;
Nếu 1 < N < 4 thì N là số nguyên tố;
Nếu N > 4 và không có ước số trong phạm vi từ 2 đêh phần nguyên căn bậc hai của N thì N là số nguyên tố.
Từ đó ta có thuật toán như sau:
Thuật toán
a) Cách liệt kê
Bước 1. Nhập số nguyên dương V;
Bước 2. Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;
Bước 3. Nếu N < 4 thì thông báo N là nguyên tố rồi kết thúc;
Bước 4. i <r- 2',
Bước 5. Nếu i > [ ựỹỹ J1'1 thì thông báo N là nguyên tố rồi kết thúc;
Bước 6. Nếu V chia hết cho z' thì thông báo N không nguyên tố rồi kết thúc;
Bước 7. i <— ỉ + 1 rồi quay lại bước 5.
Ghi chú: Biến / nhận giá trị nguyên thay đổi trong phạm vi từ 2 đến + 1 và dùng để kiểm tra N có chia hết cho i hay không.
(,) [x] kí hiệu phần nguyên của X, là số nguyên lớn nhất không vượt quá X.
b) Sơ đồ khối
Dưới đây là ví dụ mô phỏng việc thực hiện thuật toán trên.
VỚỈN-29 ([a/29] = 5)	Với N = 45 ([V45] = 6)
/
2
3
4
5
6
N/i
29/2
29/3
29/4
29/5
Chia hết không?
Không
Không
Không
Không
/
2
3
N/i
45/2
45/3
Chia hết không?
Không
Chia hết
a) 29 là sô' nguyên tô'	b) 45 không là sô' nguyên tô'
Ví dụ 2. Bài toán sắp xếp
Trong cuộc sống, ta thường gặp những việc liên quan đến sắp xếp như xếp các học sinh theo thứ tự từ thấp đến cao, xếp điểm trung bình của học sinh trong lớp theo thứ tự từ cao đến thấp. Nói một cách tổng quát, cho một dãy đối tượng, cần sắp xếp lại vị trí các đối tượng theo một tiêu chí nào đó. Chẳng hạn, cho 10 chiếc cọc có chiều cao khác nhau (h. 22a), cần xếp lại các cọc từ thấp đến cao (h. 22b).
Dưới đây ta chỉ xét bài toán sắp xếp dạng đom giản:
Cho dãy A gồm N số nguyên ữj, a2,..., aN. Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm (tức là số hạng trước không lớn hơn số hạng sau).
Ví dụ, với A là dãy gồm các số nguyên: 6, 1,5, 3, 7, 8, 10, 7, 12, 4, sau khi sắp xếp ta có dãy: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12.
Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
Xác định bài toán
Input: Dãy A gồm N số nguyên ứp a2,..., aN.
Output: Dãy A được sắp xếp lại thành dãy không giảm.
Ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hom số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
Thuật toán a) Cách liệt kê
Bướcl. Nhập N, các số hạng đ], a2,..., aN;
Bước 2. M <— N;
Bước 3. Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
Bước 4. AI M — 1, I 4— 0;
Bước 5. i <— I' + 1;
Bước 6. Nếu i > M thì quay lại bước 3;
Bước 7. Nếu ữj> ai+ị thì tráo đổi Í7j và ữí+1 cho nhau;
Bước 8. Quay lại bước 5.
Ta thấy rằng, sau mỗi lần đổi chỗ, giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng vị trí là ở cuối'dãy. Tương tự, sau lượt thứ hai, giá trị lớn thứ hai được xếp đúng ở vị trí sát cuối,... Có thể hình dung, sau mỗi lượt có ít nhất một số hạng đã xếp đúng vị trí và không còn tham gia vào quá trình đổi chỗ nữa, giống như các bọt nước từ đáy hồ (đầu dãy) nổi dần và khi đã lên mặt nước (cuối dãy) rồi thì tan biến. Có thể vì thế mà sắp xếp bằng tráo đổi còn có tên gọi là sắp xếp nổi bọt (Bubble Sort).
Ghi chú: - Qua nhận xét trên, ta thấy quá trình so sánh và đổi chỗ sau mỗi lượt chỉ thực hiện với dãy đã bỏ bớt số hạng cuối dãy. Để thực hiện điều đó trong thuật toán sử dụng biến nguyên M có giá trị khởi tạo là N, sau mỗi lượt M giảm một đơn vị cho đến khi M < 2.
- Trong thuật toán trên, / là biến chỉ số có giá trị nguyên thay đổi lẩn lượt từ 0 đến M + 1.
b) Sơ đồ khối
F
1<- i + 1
Đúng
SaiT
" Đúng
d	ữị > đ/+l •
Sai
Dưới đây là ví dụ mô phỏng việc thực hiện thuật toán trên.
6	1	5	3	7	8	10	7	12	4
1	6	5	3	7	8	10	7	12	4
...... _ _
Lẩn duyệt 1	1	5	6	3	7	8	10—T	12	4
1	5	3	6	7	8	10	7	12	4
„ „ „„
153678	7	10	12	4
153678	7	10	4	12
_ 	
1 5 3 6 7 8_7	10	4	12
Lần duyệt 2	1	3 5 6 7 8	7	10	4	12
135677	8	10	4	12
Lần duyệt 3
135677 8 4 10 12
135677 8 4 10 11 135677 48 10 12
Lần duyệt 4
Lần duyệt 5
Lần duyệt 6
Lần duyệt 7
Lần duyệt 8
Lần duyệt 9
Lần duyệt 10
135677 48 10 12 135674 78 10 12
135674 78 10 12 13564 778 10 12
1 3 5 6 4	1g
1 3 5 4HHK. 8 10 12 4"%
W0M 8 10 12
1 3 4' 5 6 7 7 8 10 12
13456 778 10 12
Ví dụ 3. Bài toán tìm kiếm
Tìm kiếm là việc thường xảy ra trong cuộc sống, chẳng hạn cần tìm cuốn sách giáo khoa Tin học 10 trên giá sách, cần tìm một học sinh trong danh sách một lớp học,... Nói một cách tổng quát là cần tìm một đối tượng cụ thể nào đó trong tập các đối tượng cho trước.
Dưới đây ta chỉ xét bài toán tìm kiếm dạng đơn giản sau:
Cho dãy A gồm N số nguyên khác nhau: a Ị, a2,..., aNvà một số nguyên k. Cần biết có hay không chỉ số i (1 < i < N) mà Oị = k. Nếu có hãy cho biết chỉ số đó.
Số nguyên k được gọi là khoá tìm kiếm (gọi tắt là khoá).
Ví dụ, cho dãy A gồm các số: 5,7, 1, 4, 2, 9, 8, 11, 25, 51.
Với khoá k - 2, trong dãy trên có số hạng ứ5 có giá trị bằng k. Vậy chỉ số cần tìm là Z = 5;
Với khoá k - 6 thì không có số hạng nào của dãy A có giá trị bằng k.
Thuật toán tìm kiếm tuần tự (Sequential Search)
Xác định bài toán
Input: Dãy A gồm N số nguyên khác nhau aỵ, a2,..., aN và số nguyên k;
Output: Chỉ số Z mà = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
Ỷ tưởng: Tìm kiếm tuần tự được thực hiện một cách tự nhiên. Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá.
Thuật toán
Cách liệt kê
Bước 1. Nhập N, các số hạng ứj, ứ2,..., aNvà. khoá k;
Bước 2. i <— 1;
Bước 3. Nếu aị = k thì thông báo chỉ số i, rồi kết thúc;
Bước 4. i i + 1;
Bước 5. Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc;
Bước 6. Quay lại bước 3.
Sơ đồ khối
Ghi chú: Trong thuật toán trên, i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N + 1.
Dưới đây là ví dụ mô phỏng việc thực hiện thuật toán trên.
A
5
7
1
4
2
9
8
11
25
51
i
1
2
3
4
5
-
-
-
-
k = 2 và N = 10
Với i = 5 thì a5 = 2.
A
5
7
1
4
2
9
8
11
25
51
i
1
2
3
4
5
6
7
8
9
10
11
k = 6 và N = 10
Với mọi /' từ 1 đến 10 không có a,- có giá trị bằng 6.
Thuật toán tìm kiếm nhị phân (Binary Search)
Xác định bài toán
Input: Dãy A là dãy tăng gồm N số nguyên khác nhau ax, a2,..., aN và một số nguyên k;
Output: Chỉ số i mà dị = k hoặc thông báo không có số hạng nào' của dãy A có giá trị bằng k.
Ỷ tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh khoá với số hạng được chọn. Để làm điều đó, ta chọn số hạng aGiua ở "giữa dãy" để so sánh với k, trong đó
_ _ p+f
Oiua = —— .
2
Khi đó, chỉ xảy ra một trong ba trường hợp sau:
Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.
Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy ax, a2,..., aGiua_x (phạm vi tìm kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trước đó).
Nếu aGiua < k thì thực hiện tìm kiếm trên dãy ữGiua+ỵ, aGiua+2,..., aN.
Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng.
Thuật toán
a) Cách liệt kê
Bước 1. Nhập V, các số hạng ax, a2,..., aN và khoá k;
Bước 2. Dau <— 1, Cuoỉ <— N\
Bước 3. Giua <—
Daũ + Cuoi
Bước 4. Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc;
Bước 5. Nếu aGiua > k thì đặt Cuoi = Giua - 1, rồi chuyển đến bước 7; Bước 6. Dau <—Giua + 1;
Bước 7. Nếu Dau > Cuoi thì thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc;
Bước 8. Quay lại bước 3.
Ghi chú: Tuỳ thuộc aGịua > k hoặc aGịua < k mà chỉ sô' đầu hoặc chỉ số cuối của dãy ■ ở bước tìm kiếm tiếp theo sẽ thay đổi. Để thực hiện điều đó, trong thuật toán chỉ sử dụng các biến nguyên tương ứng Dau và Cuoi có giá trị khởi tạo Dau = 1 và Cuoi = N.
b) Sơ đồ khối
ĩ
Dau <- 1; Cuoi <— N
Giua <— [(Dau + Cuoi)l2]
Dưới đây là ví dụ mô phỏng việc thực hiện thuật toán trên.
/
1
2
3
4
5
6
7
8
9
10
A
2
4
5
6
9
21
22
30
31
33
Dau
1
6
6
Cuoi
10
10
7
Giua
5
8
6
aGiua
9
30
21
Lần
duyệt
1
2
3
k = 21, N =10
Ở lần duyệt thứ ba thì aGiug = k. Vậy chỉ sô' cần tìm là / = Giua = 6.
/■
1
2
3
4
5
6
7
8
9
10
A
2
4
5
6
9
21
22
30
31
33
Dau
1
6
6
7
8
Cuoi
10
10
7
7
7
Giua
5
8
6
7
aGiua
9
30
21
22
Lần
duyệt
1
2
3
4
5
k = 25, N =10
Tại lẩn duyệt thứ năm Dau > Cuoi nên kết luận trong dãy A không có số hạng nào có giá trị là 25 cả.
Các thuật ngữ chính	
Bài toán; Thuật toán; Sơ đồ khối; Input; Output; sắp xếp bằng tráo đổi; Tìm kiếm tuần tự; Tìm kiếm nhị phân.
CÂU HỎI VÀ BÀI TẬP
Hãy phát biểu một bài toán và chỉ rõ Input và Output của bài toán dó.
Dãy các thao tác sau:
Bước 1. Xoá bàng;
Bước 2. Vẽ đường tròn;
Bước 3. Quay lợi bước 1.
có phải là thuật toán không? Tại sao?
Hãy chỉ ra tính dùng của thuật toán tìm kiếm tuần tụ.
Hãy mô tả thuật toán giải các bài toán sau bằng cách liệt kê hoặc bằng sơ đổ khối.
Cho N và dãy số Ơ!	dN. hãy tìm giá trị nhỏ nhất (Min) của dãy đó.
Tìm nghiệm của phương trình bộc hai tổng quát: ơx2 + bx + c = ũ.
Cho N và dãy số ơ],.,., dN, hãy sắp xếp dãy số đó thành dãy số không tăng (số hạng trước lớn hơn hay bằng số hạng sau).
Cho /V và dãy số d-ị,..., dN. hãy cho biết có bao nhiêu số hạng trong dãy có giá trị bằng 0.