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

Tuần 6- Tiết 11 Ngày soạn: 30/08/2015 Ngày dạy: Lớp dạy: 10B1 Tiết 10 BÀI TOÁN - THUẬT TOÁN (T2/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 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 đó. 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 2. Khái niệm thuật toán Câu hỏi / bài tập định tính Biết các hình để sử dụng diễn tả thuật toán bằng SĐK. Bài tập định lượng Biết xây dựng ý tưởng tìm giá trị lớn nhất của một dãy số nguyên cho trước. Tìm ra được thuật toán Max. Xây dựng theo 2 cách: liệt kê và SĐK cho bài toán Max. Mô phỏng được thuật toán tìm Max. 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: Tìm giá trị lớn nhất của một dãy số nguyên. 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: 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: Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên cho trước. · Xác định bài toán: + Input: – số nguyên dương N. – N số a1, a2, , aN. + Output: giá trị Max. · Thuật toán: (Liệt kê) B1: Nhập N và dãy a1, , aN B2: Max ¬ a1; i ¬2 B3: Nếu i > N thì đưa ra giá trị Max và kết thúc. B4: Nếu ai > max thì Max ¬ ai B5: i ¬ i+1, quay lại B3. Câu hỏi: Hãy xác định dữ liệu vào và ra của bài toán? · Tổ chức các nhóm thảo luận H. Hãy xác định Input và Output của bài toán? · Hướng dẫn HS tìm thuật toán (có thể lấy VD thực tế để minh hoạ: tìm quả cam lớn nhất trong N quả cam) · Ý tưởng: – Khởi tạo giá trị Max = a1. – Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai. · GV giải thích các bước · Các nhóm đưa ra kết quả Input: – số nguyên dương N. – N số a1, a2, , aN. Output: giá trị Max. · Các nhóm thảo luận và trình bày ý tưởng. học sinh lắng nghe và ghi nhớ 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 tác so sánh. thể hiện các phép tính toán. thể hiện thao tác nhập, xuất dữ liệu. qui định trình tự thực hiện các thao tác. Câu hỏi: Em hãy vẽ sơ đồ khối của bài toán trên? 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 thuật toán trên với N = 11 và dãy A: 5, 1, 4, 7, 6, 3, 15, 8, 4, 9, 12. · GV minh hoạ việc thực hiện thuật toán với một dãy số cụ thể. · HS theo dõi, tham gia nhận xét kết quả. Dãy số 5 1 4 7 6 3 15 8 4 9 12 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: – Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác. – Tính xác định: sau khi thực 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. Câu hỏi: Em có nhận xét gì về tính dừng, tính đúng đắn, tính xác định của thuật toán trên · Hướng dẫn HS nhận xét các tính chất của thuật toán. · Cho HS nêu lại các cách diễn tả thuật toán · HS nhận xét qua VD trên Trả lời:Với thuật toán trên ta có nhận xét -Tính dừng: Vì giá trị của I mỗi lần tăng lên 1 đơn vị nên sau n lần thì i>n. Khi đó phép toán so sánh ở bước 3 xác định việc đưa ra giá trị Max rồi kết thúc -Tính xác định: Các bước được thực hiện tuần tự và sau mỗi bước xác địng duy nhất bước tiếp theo -Tính đúng đắn: Thuật toán so sánh max với từng số hạng. Nếu tại một vị trí nào đó Ai lớn hơn Max thì hoán đổi giá trị. Sau n-1 lần so sanh, sẽ tìm ra giá trị lớn nhất. III. BÀI TẬP VỀ NHÀ Học các nội dung: Các tính chất của thuật toán Bài tập: Bài tập 1,2, 3/Trang 44 SGK Chuẩn bị bài mới: Làm thế nào để sắp xếp một dãy số theo chiều tăng hoặc giảm dần – 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" IV. RÚT KINH NGHIỆM, BỔ SUNG