Bài toán xếp loại học tập của một lớp Input của bài toán là
§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 |