Giáo án Tin học 10 bài 4 tiết 12: Bài toán - Thuật toán (t4/5)

Tuần 7- Tiết 13 Ngày soạn: 07/10/2015 Ngày dạy: 09 /10/2015 Lớp dạy: 10B1 Tiết 12 BÀI TOÁN - THUẬT TOÁN (T4/5) I. XÁC ĐỊNH MỤC TIÊU: 1. Lựa chọn chủ đề, nội dung dạy học: Bài toán - Thuật toán. 2. Xác định yêu cầu kiến thức, kỹ năng, thái độ Kiến thức: – Hiểu 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. – Hiểu thuật toán sắp xếp. Kĩ năng: – Biết xây dựng thuật toán của một số bài toán thông dụng. Thái độ: – Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó. 3. Lập bảng mô tả yêu cầu cần đạt Nội dung Loại câu hỏi / bài tập Nhận biết Thông hiểu Vận dụng thấp Vận dụng cao 3. Một số ví dụ đơn giản Câu hỏi / bài tập định tính Bài tập định lượng Tìm Input, Output và nêu cách giải của bài toán sắp xếp. Viết được chính xác thuật toán giải bài toán sắp xếp. Giải thích chính xác hoạt động của thuật toán sắp xếp. Đọc hiểu thuật toán từ đó phát biểu bài toán sắp xếp. Bài tập thực hành 4. Đề xuất năng lực có thể hướng tới: Hiểu các bài toán: Sắp xếp. HS phải hiểu được các bài toán này (mô tả được thuật toán bằng ngôn ngữ liệt kê, mô phỏng thực hiện thuật toán với bộ dữ liệu đơn giản). II. CÁC HOẠT ĐỘNG DẠY HỌC Nội dung Hoạt động của Giáo viên Hoạt động của Học sinh Hoạt động 1: Mô tả thuật toán sắp xếp bằng tráo đổi III. Một số ví dụ (tt) 2. Ví dụ 2: 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. Đặt vấn đề: Trong cuộc sống ta thường gặp những việc liên quan đến sắp xếp. Cho một dãy số nguyên A: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4 Hãy sắp xếp dãy A trở thành dãy không giảm. · Tổ chức các nhóm thảo luận H. Hãy xác định Input và Ouput của bài toán? · GV hướng dẫn HS tìm thuật toán giải bài toán. · GV nhận xét và bổ sung · Hướng dẫn HS trình bày thuật toán (bằng pp liệt kê) · Nhận xét: 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. · HS trả lời: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12. · 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. · Các nhóm thảo luận đưa ra ý kiến · Ghi lại sơ đồ thuật toán và hình dung ra các bước thực hiện thuật toán. Hoạt động 2: Diễn tả thuật toán bằng sơ đồ khối b) Sơ đồ khối: Hoạt động 3: Mô phỏng việc thực hiện thật toán – Củng cố Mô phỏng việc thực hiện thuật toán với: N = 10 và dãy A: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4 Dãy A 6 1 5 3 7 8 10 7 12 4 Lượt 1 1 5 3 6 7 8 7 10 4 12 Lượt 2 1 3 5 6 7 7 8 4 10 Lượt 3 1 3 5 6 7 7 4 8 Lượt 4 1 3 5 6 7 4 7 Lượt 5 1 3 5 6 4 7 Lượt 6 1 3 5 4 6 Lượt 7 1 3 4 5 Lượt 8 1 3 4 Lượt 9 1 3 Lượt 10 1 III. BÀI TẬP VỀ NHÀ – Tập mô phỏng việc thực hiện thuật toán trên với dãy số khác. – Tìm thuật toán tìm sắp xếp một dãy số nguyên thành dãy không tăng. IV. RÚT KINH NGHIỆM, BỔ SUNG