Kế hoạch dạy học môn Tin học Lớp 10 - Bài 4: Bài toán và thuật toán - Phan Kim Cương (Tiết 3)

BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN
I. MỤC TIÊU BÀI HỌC
1. Kiến thức, kĩ năng, thái độ:
a. Kiến thức: 
Nêu được cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước.
b. Kĩ năng: 
Xây dựng được thuật toán của một số bài toán thông dụng.
c. Thái độ: 
Sự nghiêm túc và tính tích cực, chủ động trong học tập.
2. Năng lực có thể hình thành và phát triển cho học sinh
Năng lực tự học.
Năng lực giải quyết vấn đề.
Năng lực sử dụng công nghệ thông tin và truyền thông.
II. Chuẩn bị về tài liệu và phương tiện dạy học.
1. Giáo viên: 
Kế hoạch dạy học, sách giáo khoa, câu hỏi liên quan đến bài học.
2. Học sinh: 
Sách giáo khoa, vở ghi.
Ôn lại kiến thức đã học.
Đọc bài trước ở nhà.
III. Tổ chức hoạt động học của học sinh
1. Kiểm tra bài cũ. Thời gian: 3 phút.
Câu hỏi 1: ..
Câu hỏi 2: ..
2. Hoạt động dẫn dắt vào bài. Thời gian: 2 phút.
Tìm kiếm là việc thường làm của mỗi người, chẳng hạn tìm cuốn sách giáo khoa Tin học 10 trên giá sách để chuẩn bị cho giờ học ngày hôm sau, tìm chiếc áo sơ mi mới màu trắng trong tủ quần áo, Nói một cách tổng quát là cần tìm một đối tượng cụ thể nào đó trong tập các đối tượng cho trước.
3. Hoạt động hình thành kiến thức:
Hoạt động 1 (25 phút): Hướng dẫn tìm thuật toán giải bài toán
Mục tiêu: Biết cách xác định thuật toán,và diễn tả được thuật toán bằng cách liệt kê.
Hoạt động của giáo viên
Hoạt động của học sinh
GV: Dưới đây ta chỉ xét bài toán tìm kiếm dạng đơn giản sau:
Ví dụ, cho dãy A gồm các số: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51.
+ Với khoá k = 2, trong dãy trên có số hạng a5 có giá trị bằng k. Vậy chỉ số cần tìm là i = 5.
+ Với khoá k = 6 thì không có số hạng nào của dãy A có giá trị bằng k. 
GV: Tổ chức các nhóm thảo luận
GV: Hãy xác định bài toán?
GV: Gợi ý để học sinh xây dựng ý tưởng giải bài toán tìm kiếm.
GV: Hướng dẫn HS trình bày thuật toán tìm kiếm bằng cách liệt kê.
GV: Chú ý: i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N+1.
HS: Input: N, a1, a2, , aN, k
 Output: i hoặc thông báo không có i.
HS: Tìm kiếm tuần tự là lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá.
Kết luận
III. Một số ví dụ: (tt)
3. Ví dụ 3: Bài toán tìm kiếm
Cho dãy A gồm N số nguyên khác nhau: a1, a2, , aN và một số nguyên k. Cần biết có hay không chỉ số i ( 1 ≤ i ≤ N) mà ai = k. Nếu có hãy cho biết chỉ số đó. Thuật toán tìm kiếm tuần tự 
	(sequential search)
 Xác định bài toán
 - Input: Dãy A gồm N số nguyên khác nhau a1, a2, , aN và số nguyên k;
 - Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
Ý tưởng:
 - Tìm kiếm tuần tự là lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá. Thuật toán:
* Cách liệt kê:
 - B1: Nhập N, các số hạng a1, a2, , aN và khoá k;
 - B2: i 1;
 - B3: Nếu ai = k thì thông báo chỉ số i, kết thúc;
 - B4: i i + 1;
 - B5: Nếu i >N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc.
 - B6: Quay lại bước 3.
Hoạt động 2 (12 phút): Diễn tả thuật toán tìm kiếm bằng sơ đồ
Mục tiêu: Biết cách diễn tả thuật toán tìm kiếm bằng sơ đồ khối.
Hoạt động của giáo viên
Hoạt động của học sinh
GV: Từ cách liệt kê biểu diễn thuật toán bằng sơ đồ khối.
HS: 
S
i 1
Nhập N và a1, a2,..., aN; k
i i + 1
ai = k
i > N ?
Đưa ra i rồi 
kết thúc
Thông báo dãy A không có số hạng có giá trị bằng k rồi kết thúc
Đ
Đúng
S
Kết luận
* Sơ đồ khối
S
i 1
Nhập N và a1, a2,..., aN; k
i i + 1
ai = k
i > N ?
Đưa ra i rồi 
kết thúc
Thông báo dãy A không có số hạng có giá trị bằng k rồi kết thúc
Đ
Đúng
S
4. Hoạt động luyện tập (3 phút): 
Mục tiêu: Hệ thống, cũng cố các kiến thức đã học.
Hoạt động của giáo viên
Hoạt động của học sinh
Đặt câu hỏi giúp học sinh hệ thống, cũng cố những nội dung trọng tâm của bài học.
Giao nhiệm vụ về nhà cho học sinh.
Trả lời những câu hỏi của giáo viên.
Tiếp nhận nhiệm vụ học tập.
IV. Rút kinh nghiệm
DUYỆT KẾ HOẠCH