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 Max thì Max 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