11 BAI TOAN VA THUAT TOAN Tiet 2

<span class='text_page_counter'>(1)</span>Ngày soạn Ngày dạy. :............................ Tiết :.............................. : ........................... Lớp :.............................. §4. BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2). I. MỤC TIÊU 1. Kiến thức - Biết Input và Output của bài toán tìm giá trị lớn nhất của một dãy số nguyên; biết thuật toán của bài toán đó 2. Kỹ năng - Hiểu và trình bày được thuật toán tìm giá trị lớn nhất của một dãy số nguyên theo 2 cách: liệt kê hoặc sơ đồ khối; nhận biết được các bài toán khác thuộc lớp các bài toán (ví dụ: tìm min,…) II. PHƯƠNG PHÁP, PHƯƠNG TIỆN DẠY HỌC 1. Chuẩn bị của giáo viên - Đồ dùng: Giáo án, SGK, SGV, tài liệu tham khảo máy chiếu (nếu có) - Phương pháp: Thuyết trình, vấn đáp. 2. Chuẩn bị của học sinh Đồ dùng học tập: SGK, vở ghi, bút,.... III. NỘI DUNG BÀI GIẢNG 1. Ổn định tổ chức lớp - Ổn định lớp. - Chỉnh đốn trang phục. - Sĩ số:.........Vắng:...... 2. Kiểm tra bài cũ Câu 1: Hãy phát biểu một bài toán và chỉ rõ Input và Output của bài toán? Câu 2: Em hãy trình bày khái niệm thuật toán? 3. Đặt vấn đề 4. Nội dung bài mới. Hoạt động của GV 2. 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. Yêu cầu học sinh xác định Input và Output của bài toán.. Hoạt động của HS - Input: Số nguyên dương N và dãy N số nguyên a1, a2, ..., aN.. Hoạt động 1: Hướng dẫn học sinh tìm ý tưởng của bài - Output: Giá trị lớn nhất toán. Max của dãy số Trò chơi: Tìm max: trên. Cho 5 tấm bìa a1, a2,a3,a4,a5. Trên mỗi tấm bìa có ghi một số nguyên và được đặt úp sao cho người chơi không biết trước giá trị ghi trên nó. Tg.

<span class='text_page_counter'>(2)</span> Hoạt động của GV. Hoạt động của HS. *) Quy tắc chơi: Tại mỗi thời điểm người chơi được lật lần lượt từng tấm bìa để đọc giá trị; Và sử dụng một ô nhớ Max luôn cập nhật giá trị lớn nhất của các tấm bìa đã lật đến thời điểm trước khi lật tấm bìa tiếp theo. Sao cho khi lật hết các tấm bìa thì tìm ra được giá trị lớn nhất ghi trong ô Max. - Em khởi tạo giá trị ban đầu max =?. - HS: lên bảng thực hiện trò chơi Luật a1 = 17, ghi giá trị vào ô max (max= 17); lật a2= 11, so sánh với a1 thấy nhỏ hơn, lật tiếp a3=19, so sánh với max thấy lớn hơn, cập nhật giá - Tại sao không chọn giá trị khác mà lại chọn a1 để trị đó cho max (max=19); khởi tạo cho max? tiếp tục lật a4=23, so sánh với max thấy lớn hơn, cập nhật giá trị đó cho max (max=23); lật tiếp a5=18, thấy nhỏ hơn max. Kết - Lần lượt với tấm bìa thứ i (i = 2->5), em làm gì? thúc, ô nhớ max ghi giá trị lớn nhất là 23. - Thông qua các thao tác tìm max của trò chơi trên, em Trả lời: giá trị lớn nhất là cho biết ý tưởng bài toán “Tìm giá trị lớn nhất của một 23. dãy số nguyên” - HS: max = a1; - Nếu max là số khác a1 thì phải thêm 1 thao tác so sánh a1 với max; mặt khác, nếu giá trị ban đầu lớn hơn tất cả các ai -> nó không phải là giá trị lớn nhất cần tìm - HS: So sánh giá trị trên bìa với giá trị của ô max, nếu lớn hơn -> thay vào max; nếu nhỏ hơn -> tiếp tục lật tấm bìa tiếp theo để so sánh với max. - HS trả lời *) Ý tưởng: - Khởi tạo max = a1 - Với i từ 2 đến N, so sánh ai với max: nếu ai>max. Tg.

<span class='text_page_counter'>(3)</span> Hoạt động của GV. Hoạt động của HS thì max nhận giá trị mới là ai. (biến i để xét các số hạng sẽ so sánh với số ở max). Hoạt động 2: Hướng dẫn tìm hiểu 1 số khái niệm sử dụng trong diễn tả thuật toán - Khái niệm biến: Là 1 đại lượng mà giá trị của nó có - Khái niệm biến thể thay đổi khi thực hiện chương trình; biến là một vùng nhớ dùng để lưu trữ dữ liệu, mỗi biến có 1 tên. - Giới thiệu phép gán - Phép gán: Dùng để gán VD: x <-- 3; y <-- 3+x; (chuyển) giá trị của 1 biểu thức cho 1 biến, có dạng: biến biểu thức;. ? x<--2; x<--5; thì biến x có giá trị là bao nhiêu? A<--8; B<--A; thì A và B mang giá trị là bao nhiêu?. *) Đặc điểm của phép gán: +) khi gán giá trị mới thì giá trị cũ bị xoá (luôn lưu trữ giá trị gán mới nhất) +) Nếu gán a<--b thì giá trị của biến b ở vế phải không bị thay đổi (b cho a bản sao của b) - HS trả lời. Qua khái niệm trên, nếu muốn biến max nhận giá trị của a1 phải viết thế nào? Và biến i nhận giá trị khởi tạo - HS trả lời là 2? - Sau mỗi thao tác muốn tăng i lên 1 đơn vị ta có thể sử - HS: phải gán a1 cho dụng lệnh gán i<--i+1; biến max: Max <--a1; i<--2; Hoạt động 3 : Hướng dẫn học sinh các cách biểu diễn thuật toán và các tính chất của thuật toán. Ta có thể mô tả thuật toán bằng 2 cách: Cách 1: Cách liệt kê B1: Nhập N và dãy số a1, a2,..., aN.. Tg.

<span class='text_page_counter'>(4)</span> Hoạt động của GV. Cách 2: Sử dụng sơ đồ khối. Hoạt động của HS. Tg. B2: max <-- a1; i<--2; B3: Nếu i > N thì đưa ra max rồi kết thúc B4: Nếu ai > max thì max <-- ai; B5: i <--i +1; rồi quay lại B3 * Quy định: + Hình ellip. : Các. thao tác nhập, xuất dữ liệu. + Hình thoi - Với bài toán trên ta có thể biểu diễn dưới dạng sơ đồ Thao tác so sánh. khối như sau: + Hình chữ nhật * Tính chất của thuật toán: phép toán. - Đọc và trả lời câu hỏi 2 ( SGK – 44).. :. : Các. + Mũi tên  Quy định trình tự thực hiện các thao tác. - HS theo dõi trên bảng phụ. * Tính chất của thuật toán: - Tính dừng: Thuật toán phải kết thúc sau một dãy 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 một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để thực hiện tiếp theo. - Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần.

<span class='text_page_counter'>(5)</span> Hoạt động của GV. Hoạt động của HS. Tg. tìm. Hoạt động 4: Mô phỏng việc thực hiện thuật toán với dãy số có N= 10 phần tử. a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 ds 17 11 19 23 18 47 32 54 45 16 54 i 2 3 4 5 6 7 8 9 10 M A 17 17 19 23 23 47 47 54 54 54 x - Cho thêm bài tập để HS tự mô phỏng: Nhóm 1, 2: Cho N = 7 a1 21. a2 33. a3 27. a4 45. a5 38. a6 47. - HS làm theo nhóm và lên trình bày. a7 19. Nhóm 3, 4: N = 6 a1 15. a2 7. a3 -8. a4 20. a5 -31. a6 19. 5. Củng cố - Các cách biểu diễn thuât toán - Các tính chất của thuật toán.. 6. Bài tập về nhà - Làm bài tập trong SBT - Đọc sách trước bài sau: Bài toán và thuật toán: ví dụ - Kiểm tra tính nguyên tố của 1 số nguyên dương..

<span class='text_page_counter'>(6)</span>