CHÀO MỪNG QUÝ THẦY
CÔ ĐẾN DỰ GIỜ LỚP 10A11
Câu hỏi:
- Tìm input và output của bài toán: Tìm ước chung lớn nhất của 2 số nguyên dương M, N?
- Nêu khái niệm thuật toán?
Đáp án:
Input: 2 số nguyên dương M, N
Output: Ước chung lớn nhất của 2 số M, N
Thuật toán để giải một bài toán là:
Dãy hữu hạn các thao tác
- Sắp xếp theo 1 trình tự xác định
Input ta nhận được Output cần tìm
4.BÀI TOÁN THUẬT TOÁN
(Tiết PPCT: 11-12)
Khái niệm bài toán
Khái niệm thuật toán
Một số ví dụ về thuật toán
BÀI TOÁN TÌM MAX
Người ta đặt 5 quả dưa hấu có trọng lượng khác nhau trên bàn. Làm thế nào để tìm được quả dưa nặng nhất ?
Quả này lớn nhất
Quả này mới lớn nhất
ồ! Quả này lớn hơn
Tìm ra quả lớn nhất rồi!
mô phỏng thuật toán
Ví dụ 1: Cho số nguyên dương N và dãy số nguyên a1,a2…aN. Hãy tìm giá trị lớn nhất (max) của dãy số đó
Xác đinh bài toán:
Input
Output
:
:
Số nguyên dương N và dãy số nguyên a1,a2,…aN
Số lớn nhất (max) của dãy số
3. Một số ví dụ về thuật toán
Ý tưởng:
Khởi tạo giá trị max = a1
Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị max, nếu ai> max thì max nhận giá trị mới là ai
Cho số nguyên dương N và dãy số nguyên a1,a2…aN. Hãy tìm giá trị lớn nhất (max) của dãy số đó
N=5
Dãy số
max
Nhập N và dãy a1, a2 …, aN
Max  a1 ; i  2
i>N
Đưa ra Max
rồi kết thúc
Max  ai
Đ
S
i  i + 1;
ai>Max
Đ
S
Sơ đồ khối
N=5
max
ii + 1: phép gán i+1 cho i
(tăng i lên 1 đơn vị)

i >N: dừng lại
i 2
Ý tưởng:
Dãy số
Chạy thử với N = 3
Nhập N và dãy a1, a2 …, aN
Max a1 ; i  2
i>N
Đưa ra Max
rồi kết thúc
Max  ai
Đ
S
i  i + 1;
ai >Max
Đ
S
max9; i2
ia2< max;
i3
i=N
a3> max
i4
i>N
max 18
max a3
Cho số nguyên dương N và dãy số nguyên a1,a2…aN. Hãy tìm giá trị nhỏ nhất (min) của dãy số đó
Bài tập củng cố
Xác định bài toán
Ý tưởng
Thuật toán liệt kê