BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN
GV: HUỲNH VĂN MẠNH
MỤC ĐÍCH YÊU CẦU MỤC ĐÍCH YÊU CẦU
- Hiểu cách biểu diễn thuật toán bằng sơ đồ khối hoặc bằng liệt kê các bước.
- Biểu diễn được thuật toán liệt kê hoặc bằng sơ đồ khối.
- Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán.
1. Khái niệm bài toán 1. Khái niệm bài toán
Trong phạm vi tin học bài toán là một việc nào đó ta muốn máy tính thực hiện.
Vậy thì khi giải bài toán trên máy tính ta cần quan
tâm đến các yếu tố nào?
2. Input và Output 2. Input và Output
Đưa vào máy tính thông tin gì?
Cần lấy ra thông tin gì?
VÍ DỤ VÍ DỤ
GIẢI BÀI TOÁN
PHƯƠNG TRÌNH BẬC HAI
Ax
2+ Bx + C = 0
INPUT: Các số thực a, b, c (a 0).
OUTPUT: Số thực x thoả
BÀI TOÁN QUẢN LÝ HỌC SINH
XẾP LOẠI HỌC TẬP CỦA HỌC SINH
INPUT: Bảng điểm học sinh OUTPUT: Xếp loại HS
Việc xác định Input và Output giúp ta thuận lợi hơn
cho việc giải một bài toán đơn giản. Đối với những bài toán phức tạp ngoài việc tìm Input và Output chúng ta cần phải sử dụng đến một phương pháp gọi là “Thuật toán”.
Việc xác định Input và Output giúp ta thuận lợi hơn
cho việc giải một bài toán đơn giản. Đối với những bài toán phức tạp ngoài việc tìm Input và Output chúng ta cần phải sử dụng đến một phương pháp gọi là “Thuật toán”.
Vậy thuật toán là gì?
2. Khái niệm thuật toán 2. Khái niệm thuật toán
a/ Khái niệm thuật toán: 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.
2. Khái niệm thuật toán 2. Khái niệm thuật toán
b/ Mô tả các thao tác trong thuật toán:
Có hai cách:
Liệt kê và sơ đồ khối.
Củng cố Củng cố
- Nắm vững khái niệm bài toán và thuật toán trong tin học.
- Diễn tả được thuật toán.
Hết tiết 1 Hết tiết 1
3. Bài toán tìm giá trị lớn nhất của dãy số nguyên 3. Bài toán tìm giá trị lớn nhất của dãy số nguyên
Cho dãy số nguyên a1, a2,…, aN. Hãy tìm giá trị lớn nhất của dãy số trên.
Để giải bài toán ta sẽ thực hiện qua ba bước:
Để giải bài toán ta sẽ thực hiện qua ba bước:
Xác định bài toán Lên ý tưởng
Thiết kế thuật toán
Xác định bài toán
Lên ý tưởng
Thiết kế thuật toán Thiết kế thuật toán Input:Nhập N và dãy a1 . . . aN
Output:Đưa ra GTLN (Max)
+ Khởi tạo giá trị MAX = a1. + Lần lượt với i = 2 đến N,
so sánh giá trị ai với MAX, nếu ai > MAX thì MAX = ai
Nhập N và dãy a1, a2, ..., aN.
B1 B1
Max a1, i 2;
B2 B2
Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
B3 B3
Nếu ai > Max Thì Max ai; B4 B4
i i + 1 rồi quay lại Bước 3;
B5 B5
Nhập N = 5
Max = 3, i2 2 > 5 ?
Nếu a2 > Max Thì Max là a2
9 3
9
Tăng i lên 1 đơn vị:
i=2+1=3, quay lại B3 Nếu a3 > Max
Thì Max là a2 = 9
7 9
Tăng i lên 1 đơn vị:
i=3+1=4 quay lại B3 Nếu a4 > Max
Thì Max là a2 = 9
4 9
Tăng i lên 1 đơn vị:
i=4+1=5 quay lại B3 Nếu a5 > Max
Thì Max là
10 9
Tăng i lên 1 đơn vị:
i=5+1=6 quay lại B3 3 > 5 ? 5 > 5 ? 4 > 5 ?
a5 = 10
6 > 5 ? Thoả ĐK Đưa ra Max = 10 rồi kết thúc
i 1 2 3 4 5
a 3 9 7 4 10
Thiết kế thuật toán Thiết kế thuật toán
Nhập N và dãy a1, a2, ..., aN.
B1 B1
Max a1, i 2;
B2 B2
Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
B3 B3
Nếu ai > Max Thì Max ai; B4 B4
i i + 1 rồi quay lại Bước 3;
B5 B5
Nhập N và dãy a1, a2, ..., aN.
Max a1, i 2;
i > N? Đưa ra Max
rồi kết thúc
ai>Max?
i =i + 1
Đ
S
Đ Max ai
S
4. Bài toán giải phương trình bậc một 4. Bài toán giải phương trình bậc một
Tìm nghiệm của phương trình ax + b = 0
Để giải bài toán ta sẽ thực hiện qua ba bước:
Để giải bài toán ta sẽ thực hiện qua ba bước:
Xác định bài toán Lên ý tưởng
Thiết kế thuật toán
Xác định bài toán ax + b = 0 (1)
Ý tưởng
Thiết kế thuật toán Thiết kế thuật toán Input:Nhập các hệ số a, b
Output: Số thực x thoả (1)
Xét các trường hợp:
và a
Nhập a và b B1 B1
Nếu a = 0 và b<>0 Thì ptvn (1) kết thúc.
B2 B2
x = -b/a;
B3 B3
Đưa ra kết quả rồi kết thúc.
B4 B4
ko giải được (1)
a
5. Bài toán hình chữ nhật 5. Bài toán hình chữ nhật
Tính chu vi và diện tích hình chữ nhật
Để giải bài toán ta sẽ thực hiện qua ba bước:
Để giải bài toán ta sẽ thực hiện qua ba bước:
Xác định bài toán Lên ý tưởng
Thiết kế thuật toán
Xác định bài toán Phcn và Shcn
Ý tưởng
Thiết kế thuật toán Thiết kế thuật toán Input: chiều dài (a) và chiều
rộng (b)
Output: Phcn và Shcn
Nhập a và b B1 B1
Nếu (a <= 0) or (b <=
0) Thì ko tính được Phcn và Shcn kết thúc.
B2 B2
P = (a+b)*2; S=a*b B3 B3
Đưa ra kết quả rồi kết thúc.
B4 B4
TH (a = 0) hoặc (b = 0)
P = (a+b)*2; S=a*b
6. Bài toán hình tròn 6. Bài toán hình tròn
Tính chu vi và diện tích hình tròn
Để giải bài toán ta sẽ thực hiện qua ba bước:
Để giải bài toán ta sẽ thực hiện qua ba bước:
Xác định bài toán Lên ý tưởng
Thiết kế thuật toán
Xác định bài toán Pht và Sht
Ý tưởng
Thiết kế thuật toán Thiết kế thuật toán
Input: Bán kính r Output: Pht và Sht
Nhập bán kính r B1 B1
Nếu (r <= 0) Thì ko tính được Pht và Sht kết thúc.
B2 B2
P = 2*r*pi; S=pi*r*r B3 B3
Đưa ra kết quả rồi kết thúc.
B4 B4
TH r = 0 ?
P = 2*r*pi; S=pi*r*r
7. Bài toán giải phương trình bậc hai 7. Bài toán giải phương trình bậc hai
Tìm nghiệm của phương trình ax2 + bx + c = 0 Để giải bài toán ta sẽ thực hiện qua ba bước:
Để giải bài toán ta sẽ thực hiện qua ba bước:
Xác định bài toán Lên ý tưởng
Thiết kế thuật toán
Xác định bài toán Pht và Sht
Ý tưởng
Thiết kế thuật toán Thiết kế thuật toán
Input: Bán kính r Output: Pht và Sht
Nhập bán kính r B1 B1
Nếu (r <= 0) Thì ko tính được Pht và Sht kết thúc.
B2 B2
P = 2*r*pi; S=pi*r*r B3 B3
Đưa ra kết quả rồi kết thúc.
B4 B4
TH r = 0 ?
P = 2*r*pi; S=pi*r*r
