Bai 4

Kiểm tra bài cũ
Câu hỏi 1: Hãy nhắc lại khái niệm Bài toán
Câu hỏi 2: Hãy nhắc lại khái niệm Thuật toán
Thuật toán tìm giá trị lớn nhất (max)
3. Các ví dụ về thuật toán
Bài 4. Bài toán và thuật Toán (Tiếp theo)
3
Người ta đặt 5 quả bóng có kích thước khác nhau trong hộp đã được đậy nắp như hình bên. Chỉ dùng tay sờ để tìm ra quả bóng có kích thước lớn 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!
Cùng tìm thuật toán
?
Max
?
Max
?
Max
?
Max
3.1) Thuật toán tìm số lớn nhất trong
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 a1, a2, a3 ., an (ai với i: 1?n).
N= a1, a2, a3, ., an
OUTPUT: Số lớn nhất (Max) của dãy số.
ý tưởng:
- Đặt giá trị Max =
ai
a1
a2
a3
a4
a5
- Lần lượt cho i chạy từ 2 đến n, so sánh từng giá trị ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai.
Câu hỏi 1:
Em hãy xác định giá trị của a1 đến a5
Câu hỏi 2:
Với i chạy từ 1 đến n. Em cho biết n =?
Trả lời a1 = 5...a5 = 6
Trả lời n= 5
Cụ thể cho dãy N= 5,1,4,7,6
* Mô tả (biểu diễn) thuật toán bằng 2 cách
1) Liệt kê 2) Sơ đồ khối
Cách 1: Liệt kê các bước
B1: Nhập dãy a1,., an;
B2: Max ? a1; i ? 2;
B3: Nếu i > n thì đưa ra giá trị Max rồi kết thúc;
B4: Bước 4.1: Nếu ai > Max thì Max ? ai;
Bước 4.2: i ? i+1 rồi quay lại B3.
Đ
S
Đ
S
B1: Nhập dãy a1,.,an;
B2: Max ? a1; i ? 2;
B3: Nếu i > n thì đưa ra giá trị
Max rồi kết thúc;
B4 :
4.1: Nếu ai > Max thì Max ? ai;
4.2: i ? i + 1 rồi quay lại B3.
Cách 2: Sơ đồ khối
Đ
S
Đ
S
Nhập N và dãy a1,.,an
Max ? a1 ; i ? 2
i > n ?
ai > Max ?
Max ai
i  i+1
Đưa ra Max rồi kết thúc
Max
i
a
7
7
5
5
5
5
4
3
2
6
7
4
1
5
N=5 ; A [ 5 1 4 7 6 ]
Max ? 5 ; i ? 2
2 > 5 ?
1> 5 ?
i  2+1
3 > 5 ?
4> 5 ?
i 3+1
4 > 5 ?
7 > 5 ?
Max 7
4
i 4+1
5 > 5 ?
6 > 7 ?
i 5+1
6 > 5 ?
Số lớn nhất của dãy là 7
Mô phỏng
thuật toán
Với i = 2
Với i = 3
Với i = 4
Với i = 5
Đ
S
Đ
S
Nhập N và dãy a1,.,an
Max ? a1 ; i ? 2
i > n ?
ai> Max ?
Max ai
i  i+1
Đưa ra Max rồi kết thúc
Max
i
a
7
7
5
5
5
5
4
3
2
6
7
4
1
5
N=5 ; A [ 5 1 4 7 6 ]
Max ? 5 ; i ? 2
2 > 5 ?
1> 5 ?
i  2+1
3 > 5 ?
4> 5 ?
i 3+1
4 > 5 ?
7 > 5 ?
Max 7
4
i 4+1
5 > 5 ?
6 > 7 ?
i 5+1
6 > 5 ?
Số lớn nhất của dãy là 7
Cho dãy N= 3, 1, 2, 6, 5
Lớp thảo luận nhóm 5 phút. Sau đó mỗi nhóm lên thực hiện Mô Phỏng một công đoạn v?i i=2, i=3,., i=5 trên bảng.
C?ng c?:
Đ
S
Đ
S
Nhập N và dãy a1,.,an
Max ? a1 ; i ? 2
i > n ?
ai> Max ?
Max ai
i  i+1
Đưa ra Max rồi kết thúc
Max
i
a
6
6
3
3
3
5
4
3
2
5
6
2
1
3
N=5 ; A [ 3 1 2 6 5 ]
Max ? 3 ; i ? 2
2 > 5 ?
1 > 3 ?
i  2+1
3 > 5 ?
2 > 3 ?
i 3+1
4 > 5 ?
6 > 3 ?
Max 6
4
i 4+1
5 > 5 ?
5 > 6 ?
i 5+1
6 > 5 ?
Số lớn nhất của dãy là 6
K?t lu?n: Mỗi bài toán cần máy tính thực hiện, chúng ta phải xác định được:

Input;
Thuật toán c?a bài toán;
Output cần tìm.
Dặn dò:
Về nhà nghiên cứu chu?n b? tiếp các ví dụ về thuật toán sắp xếp, tìm kiếm. trong sách giáo khoa.