Giáo án Tin học Lớp 10 - Tiết 11+12

Nội dung text: Giáo án Tin học Lớp 10 - Tiết 11+12

1. Tiết dạy : 11 Chương I: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC Ngày soạn: 07/2009 Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tt) Ngày dạy : 07/2009 I. MỤC TIÊU: 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 một số thuật toán thông dụng. 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 đó. II. CHUẨN BỊ: Giáo viên: – Giáo án + bảng vẽ các sơ đồ khối. – Tổ chức hoạt động nhóm. Học sinh: Sách giáo khoa, vở ghi. Đọc bài trước. III Phương Pháp dạy học Thuyết trình, hỏi đáp, đặt vấn đề, so sánh IV. HOẠT ĐỘNG DẠY HỌC: 1. Ổn định tổ chức: Kiểm tra sĩ số lớp. 2. Kiểm tra bài cũ: Hỏi: Để xác định một bài toán ta cần quan tâm đến các yếu tố nào? Cho ví dụ. Đáp: Input, Output. 3. Giảng bài mới: TL Nội dung Hoạt động của Giáo viên Hoạt động của Học sinh Hoạt động 1: Hướng dẫn tìm thuật toán giải bài toán: "Tìm GTLN của một dãy số nguyên" II. Khái niệm thuật toán: Tổ chức các nhóm thảo luận Các nhóm đưa ra kết quả Ví dụ: Tìm giá trị lớn nhất của H. Hãy xác định Input và Output của Đ. một dãy số nguyên cho trước. bài toán? Input: – số nguyên dương N. 15 Xác định bài toán: Hướng dẫn HS tìm thuật toán (có – N số a1, a2, , aN. + Input: thể lấy VD thực tế để minh hoạ: tìm Output: giá trị Max. – số nguyên dương N. quả cam lớn nhất trong N quả cam) Các nhóm thảo luận và trình bày ý – N số a1, a2, , aN. tưởng. + Output: giá trị Max. Ý tưởng: Thuật toán: (Liệt kê) – Khởi tạo giá trị Max = a1. B1: Nhập N – Lần lượt với i từ 2 đến N, so sánh và dãy a1, , aN giá trị số hạng a i với giá trị Max, nếu B2: Max  a1; i 2 ai > Max thì Max nhận giá trị mới là B3: Nếu i > N thì đưa ra giá trị ai. Max và kết thúc. GV giải thích các kí hiệu B4: Nếu ai > max thì Max  ai B5: i  i+1, quay lại B3. Hoạt động 2: Hướng dẫn diễn tả thuật toán bằng sơ đồ khối Sơ đồ khối: thể hiện thao 10 tác so sánh. thể hiện các phép tính toán.
2. Nhập N, a1, a2, , aN thể hiện thao tác Max  a1, i   nhập, xuất dữ liệu. qui định trình tự thực Đ Đưa ra Max i>N hiện các thao tác. rồi kết thúc S S ai > Max Đ Max  ai i  i + 1 Hoạt động 3: Mô phỏng việc thực hiện thuật toán Mô phỏng các bước thực hiện GV minh hoạ việc thực hiện thuật HS theo dõi, tham gia nhận xét kết thuật toán trên với toán với một dãy số cụ thể. quả. 10 N = 11 và dãy A: 5, 1, 4, 7, 6, 3, Dãy 5 1 4 7 6 3 15 8 4 9 12 15, 8, 4, 9, 12. số i 2 3 4 5 6 7 8 9 10 11 12 Max 5 5 5 7 7 7 15 15 15 15 15 Hoạt động 4: Củng cố các kiến thức đã học Tính chất thuật toán: Hướng dẫn HS nhận xét các tính HS nhận xét qua VD trên 7 – Tính dừng: thuật toán phải kết chất của thuật toán. thúc sau 1 số hữu hạn lần thực hiện các thao tác. Cho HS nêu lại các cách diễn tả HS nhắc lại – Tính xác định: sau khi thực thuật toán hiện 1 thao tác thì hoặc là kết thúc hoặc thực hiện 1 thao tác kế tiếp. – Tính đúng đắn: sau khi kết thúc phải nhận được Output. 4. BÀI TẬP VỀ NHÀ: – Mô phỏng việc thực hiện thuật toán tìm GTLN với N và dãy số khác. – Bài 2, 4, 5 SGK. – Đọc tiếp bài "Bài toán và thuật toán" V. RÚT KINH NGHIỆM, BỔ SUNG: - Về kiến thức: HS cần biết cả hai cách biểu diễn thuật toán là sơ đồ khối và ngôn ngữ liệt kê; - Về kĩ năng: HS chỉ cần sử dụng được một trong hai cách (sơ đồ khối hoặc ngôn ngữ liệt kê) để mô tả thuật toán. - Nên đưa một số ví dụ gần gũi với học sinh để mô phỏng cho các thuật toán
3. Tiết dạy: 12 Chương I: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC Ngày soạn: Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tt) Ngày dạy: I. MỤC TIÊU: 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 một số thuật toán thông dụng. 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 đó. II. CHUẨN BỊ: Giáo viên: – Giáo án + bảng vẽ các sơ đồ khối. – Tổ chức hoạt động nhóm. Học sinh: Sách giáo khoa, vở ghi. Đọc bài trước. III Phương Pháp dạy học Thuyết trình, hỏi đáp, đặt vấn đề, so sánh IV. HOẠT ĐỘNG DẠY HỌC: 1. Ổn định tổ chức: Kiểm tra sĩ số lớp. 2. Kiểm tra bài cũ: Hỏi: Nêu các cách diễn tả thuật toán? Đáp: Liệt kê, Sơ đồ khối. 3. Giảng bài mới: TL 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) Đặt vấn đề: Trong cuộc sống ta 2. Ví dụ 2: Bài toán sắp thường gặp những việc liên quan xếp đến sắp xếp. HS trả lời: 1, 3, 4, 5, 6, 7, 7, 8, 20 Cho dãy A gồm N số Cho một dãy số nguyên A: 10, 12. nguyên a1, a2, , aN. Cần 6, 1, 5, 3, 7, 8, 10, 7, 12, sắp xếp các số hạng để dãy 4 A trở thành dãy không Hãy sắp xếp dãy A trở thành giảm. dãy không giảm. Thuật toán sắp xếp bằng tráo đổi (Exchange Sort) Các nhóm trả lời. Xác định bài toán: Tổ chức các nhóm thảo luận Đ. + Input: Dãy N số nguyên - Input: Dãy A gồm N số H. Hãy xác định Input và Ouput + Output: Dãy N số nguyên nguyên a1, a2, , an. của bài toán? đã được sắp xếp không giảm. - Output: Dãy A được sắp xếp lại thành dãy không giảm. Các nhóm thảo luận đưa ra ý Ý tưởng: Với mỗi cặp số kiến hạng đứng liền kề trong dãy, GV hướng dẫn HS tìm thuật nếu số trước lớn hơn số sau toán giải bài toán. thì ta đổi chỗ chúng cho GV nhận xét và bổ sung 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ê: Ghi lại sơ đồ thuật toán và
4. - B1: Nhập N, các số hạng hình dung ra các bước thực hiện a1, a2, , aN ; Hướng dẫn HS trình bày thuật thuật toán. - B2: M  N ; toán (bằng pp liệt kê) - B3: Nếu M M thì quay lại nhất xếp đúng vị trí là ở cuối bước 3; dãy. Và sau mỗi lượt chỉ thực - B7: Nếu ai > ai+1 thì tráo hiện với dãy đã bỏ bớt số hạng đổi ai và ai+1 cho nhau; cuối dãy (M  M–1). Trong - B8: Quay lại bước 5. thuật toán trên, i là biến chỉ số có giá trị nguyên từ 0 M+1. Hoạt động 2: Diễn tả thuật toán bằng sơ đồ khối b) Sơ đồ khối: Nhập N, a1, a2, , aN M  N 10 Đ Đưa ra A M M S Tráo đổi Đ ai > ai+1 ai và ai+1 S 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: Dãy A 6 1 5 3 7 8 10 7 12 4 10 N = 10 và dãy A: 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 6, 1, 5, 3, 7, 8, 10, 7, 12, 4 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 4. 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. V. RÚT KINH NGHIỆM, BỔ SUNG: - Về các ví dụ này, không nhất thiết phải giới thiệu đồng thời cả hai cách biểu diễn thuật toán là sơ đồ khối và ngôn ngữ liệt kê;