Tổ Toán - tin
Giáo viên :
nguyễn hùng cường
Sơ gd & đt sơn la
trường thpt
tông lệnh
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
Một số ví dụ về Thuật toán
1. Diễn tả Thuật toán bằng cách liệt kê các thao tác.
Để diễn tả Thuật toán của bài toán ta thường sử dụng 2 cách diễn tả sau:
2. Diễn tả Thuật toán bằng sơ đồ khối.
Muốn diễn tả Thuật toán của bài toán ta diễn tả bằng cách nào?
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
1. Diễn tả Thuật toán bằng cách liệt kê các thao tác
Tìm giá trị lớn nhất của một dãy số nguyên?
Hãy xác định Bài toán của ví dụ trên?
Ví dụ
Yêu cầu
Để xác định Bài toán của ví dụ ta cần xác định những yếu tố gì?
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
Xác định Bài toán
Input:
Output:
Hãy xác định Thuật toán của ví dụ trên?
Yêu cầu
Là số nguyên dương N và dãy N số nguyên a1, a2, ., aN;
Là giá trị Lớn nhất (Max) của dãy số;
Để xác định Thuật toán cho Bài toán trên ta cần xác định những yếu tố gì?
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
Xác định Thuật toán
Bước 1: Nhập N và dãy a1, a2, ., aN;
Bước 2: Max ? a1, i ? 2;
Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
Bước 4: Nếu ai > Max thì Max ? ai
i ? i + 1 rồi quay lại bước 3;
Xác định Thuật toán
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
Chú ý:
Trong thuật toán trên, i là trị số và có giá trị nguyên thay đổi từ 2 đến N+1;
Mũi tên ? trong thuật toán được hiểu là phép 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;
i ? i+1 được hiểu là đặt cho biến giá trị mới bằng giá trị trước đó tăng thêm 1 đơn vị.
Ví dụ:
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
2. Diễn tả Thuật toán bằng sơ đồ khối
Hình thoi thể hiện thao tác so sánh;
Hình chữ nhật thể hiện các phép toán;
Hình ô van thể hiện các 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 phép toán;
Trong sơ đồ khối ta có quy ước như sau:
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
Tìm giá trị lớn nhất của một dãy số nguyên?
Hãy xác định Thuật toán cho ví dụ trên bằng sơ đồ khối ?
Ví dụ
Yêu cầu
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
Nhập N
và dãy a1, ., aN
Max ? a1, i ? 2
i > N?
ai > Max?
Max ? a1
Đưa ra Max
rồi kết thúc
Đúng
Sai
Đúng
Sai
i ? i +1
Sơ đồ khối của Thuật toán
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
Mô phỏng việc sử dụng thuật toán trên
Với N = 11
và dãy số A: 5, 1, 4, 7, 6, 3, 15, 8, 4, 9, 12
Ví dụ
2
3
4
5
6
7
8
9
10
11
12
5
5
7
7
7
15
15
15
15
15
5
1
§4 Bµi to¸n vµ ThuËt to¸n (tiÕt 2)
Hiểu và diễn tả được thuật toán bằng 2 cách;
Học bài và Chuẩn bị ở nhà;
Yêu cầu
Bài tập về nhà
Cho N và dãy số a1, ., aN hãy tìm giá trị nhỏ nhất (Min) của dãy số?