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 2)

BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tt) 
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.
Trình bày một số thuật toán thông dụng.
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.
Chúng ta đã tìm hiểu hai cách diễn tả thuật toán bầng cách liệt kê và sơ đồ khối. Vậy để giải các bài toán sắp xếp thì ta phải mô tả các cách diễn đạt trên như thế nào?
3. Hoạt động hình thành kiến thức:
Hoạt động 1: (25 phút): Mô tả thuật toán sắp xếp bằng tráo đổi
Mục tiêu: Mô tả được cách biểu diễn thuật toán sắp xếp bằng sơ đồ khối và bằng liệt kê các bước.
Hoạt động của giáo viên
Hoạt động của học sinh
GV: Cho một dãy số nguyên A: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4 .
GV: Hãy sắp xếp dãy A trở thành dãy không giảm?
GV: Tổ chức các nhóm thảo luận 
GV: Hãy xác định Input và Ouput của bài toán?
GV: Gợi ý cho học sinh hướng giải bài toán để học sinh xây dựng ý tưởng của bài toán.
GV: Kết hợp với học sinh cùng xây dựng thuật toán (bằng pp liệt kê)
GV: Sau mỗi lần đổi chỗ, giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng vị trí là ở cuối dãy. Và sau mỗi lượt chỉ thực hiện với dãy đã bỏ bớt số hạng cuối dãy (M M–1). Trong thuật toán trên, i là biến chỉ số có giá trị nguyên từ 0 M+1.
GV: Hãy diễn tả thuật toán trên bằng sơ đồ khối
HS: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12.
HS: Các nhóm trả lời.
 + Input: Dãy N số nguyên
 + Output: Dãy N số nguyên đã được sắp xếp không giảm.
HS: Ý tưởng với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau thì ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
HS: 
Kết luận
III. Một số ví dụ 
 Ví dụ 1: Bài toán sắp xếp
Cho dãy A gồm N số nguyên a1, a2, , aN. Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm.
Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
 Xác định bài toán:
 - Input: Dãy A gồm N số nguyên a1, a2, , an.
 - Output: Dãy A được sắp xếp lại thành dãy không giảm.
 Ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau thì ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
 Thuật toán:
a) Cách liệt kê:
 - B1: Nhập N, các số hạng a1, a2, , aN ;
 - B2: M N ;
 - B3: Nếu M< 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
 - B4: M M–1; i 0;
 - B5: i i+1;
 - B6: Nếu i > M thì quay lại bước 3;
 - B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
 - B8: Quay lại bước 5.
b) Sơ đồ khối
Hoạt động 2 (12 phút): Mô phỏng việc thực hiện thuật toán sắp xếp bằng tráo đổi
Mục tiêu: Mô phỏng được việc thực hiện thuật toán sắp xếp.
Hoạt động của giáo viên
Hoạt động của học sinh
GV: Lấy ví dụ mô phỏng giải thích thêm cho thuật toán sắp xếp bằng tráo đổi với: N = 10 và dãy A: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4.
HS: Theo dõi và phát biểu ý kiến (nếu có).
Kết luận
Mô phỏng thuật toán
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