Bài giảng Bài 4: Bài toán và thuật toán

được Output. Dãy thao tác đó gọi là thuật toán. · Cho các nhóm thảo luận tìm hiểu khái niệm thuật toán là gì? · GV nhận xét bổ sung và đưa ra khái niệm. · HS trả lời: · Các nhóm thảo luận và đưa ra câu trả lời. – Là một dãy thao tác – Sau khi thực hiện dãy thao tác với bộ Input thì cho ra Output. II. Khái niệm thuật toán: Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm. Hoạt động 3: Củng cố các kiến thức đã học · Cho HS nhắc lại: – Thế nào là bài toán trong tin học? – Việc xác định bài toán trong tin học? · Yêu cầu các nhóm cho VD về bài toán và xác định bài toán. · HS nhắc lại · Các nhóm trình bày 4. BÀI TẬP VỀ NHÀ: – Bài 1 SGK. – Đọc tiếp bài "bài toán và thuật toán" IV. RÚT KINH NGHIỆM, BỔ SUNG: Tuần Tiết . Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tt) 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. 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. Bài mới 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” Hoạt động của Giáo viên Hoạt động của Học sinh Nội dung · 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 kí hiệu · 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. 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. 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. 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. · 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 · HS nhắc lại 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" IV. RÚT KINH NGHIỆM, BỔ SUNG: Tuần.. Tiết Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tt) 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: SGK, vở ghi. Đọc bài trước. III. 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: Trình bày qui ước các khối trong sơ đồ khối và xác định input và output của bài toán ax2+bx+c=0 (a#o) Đáp: 3. Bài mới Hoạt động 1: Mô tả thuật toán sắp xếp bằng tráo đổi Hoạt động của Giáo viên Hoạt động của Học sinh Nội dung Đặ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. 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. 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 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. Tuần. Tiết .. Bài 4 BÀI TOÁN VÀ THUẬT TOÁN (tt) 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 đơn giản. 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ẽ sơ đồ khối – Tổ chức hoạt động nhóm. Học sinh: SGK, vở ghi. Đọc bài trước. III. 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 ý tưởng thuật toán sắp xếp bằng tráo đổi? Đáp: Ý 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 3. Bài mới Hoạt động 1: Hướng dẫn tim thuật toán giải bài toán Nội dung Hoạt động của Giáo viên Hoạt động của Học sinh 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ố đó. a) 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. Đặt vấn đề: Tìm kiếm là một việc thường xảy ra trong cuộc sống. Cho dãy A gồm: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51. Tìm i với ai = 2 ? · Tổ chức các nhóm thảo luận H. Hãy xác định bài toán? · GV hướng dẫn HS tìm thuật toán giải bài toán. · 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ê. · i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N+1. · i = 5 · Các nhóm thảo luận, đưa ra ý kiến Đ. + Input: N, a1, a2, , aN, k + Output: i hoặc thông báo không có i · Cho các nhóm trình bày ý tưởng. · Các nhóm thảo luận và đưa ra thuật toán. Hoạt động 2: Diễn tả thuật toán tìm kiếm bằng sơ đồ khối * Sơ đồ khối: Hoạt động 3: Mô phỏng việc thực hiện thuật toán Mô phỏng việc thực hiện thuật toán với: + N = 10, k = 2 k = 2 vµ N = 10 A 5 7 1 4 2 9 8 11 25 51 i 1 2 3 4 5 - - - - - Víi i = 5 th× a5 = 2. Hoạt động 7: Củng cố các kiến thức đã học 4. BÀI TẬP VỀ NHÀ: – Mô phỏng việc thực hiện thuật toán với dãy số khác. – Bài 3, 7 SGK.