Bài 4: BÀI TOÁN VÀ THUẬT TOÁN I. Khái niệm bài toán:
Định nghĩa: Trong tin học, bài toán là một việc nào đó mà ta muốn máy tính thực hiện.
Bài toán được cấu tạo từ 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
Ví dụ 1: Bài toán tìm ước chung lớn nhất của hai số nguyên dương M và N.
– Input: hai số nguyên dương 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 (a ≠ 0) – Input: a,b,c (a ≠ 0)
– Output: nghiệm x II. Khái niệm thuật toán:
1. Khái niệm: 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 khi thực hiện dãy theo tác ấy, từ input của bài toán ta nhận được output cần tìm
2. Ví dụ1 : Bài toán tìm nghiệm của phương trình bậc nhất: ax + b = 0
Xác định bài toán – Input: a,b
– Output: nghiệm x
Thuật toán B1. Nhập a,b B2. Nếu a=0
Bước 2.1. Nếu b ≠0 thì thông báo phương trình vô nghiệm, rồi kết thúc;
Bước 2.2. Nếu b = 0 thì thông báo phương trình vô số nghiệm rồi kết thúc;
Bước 3:Nếu a ≠ 0, thông báo pt có nghiệm x -b/a Bước 4. Đưa ra nghiệm x, rồi kết thúc.