Giáo án chuyên đề Khoa học máy tính 11 cánh diều CĐ 2 Bài 2: Kĩ thuật đệ quy trong chia để trị
Giáo án giảng dạy theo sách Chuyên đề học tập Tin học 11 - Khoa học máy tính bộ sách cánh diều CĐ 2 Bài 2: Kĩ thuật đệ quy trong chia để trị. Bộ giáo án giúp giáo viên hướng dẫn học sinh mở rộng kiến thức, phát triển năng lực, nâng cao khả năng định hướng nghề nghiệp cho các em sau này. Thao tác tải về rất đơn giản, tài liệu file word có thể chỉnh sửa dễ dàng, mời quý thầy cô tham khảo bài demo.
Xem toàn bộ: Giáo án chuyên đề Tin học 11 Khoa học máy tính cánh diều đủ cả năm
Ngày soạn: .../.../...
Ngày dạy: .../.../...
BÀI 2. KĨ THUẬT ĐỆ QUY TRONG CHIA ĐỂ TRỊ (2 tiết)
- MỤC TIÊU
- Kiến thức
Sau bài học này, HS sẽ:
- Nêu được ý tưởng kĩ thuật đệ quy trong bài toán tìm kiếm nhị phân và tính an.
- Biết được một số bài toán sử dụng kĩ thuật đệ quy trong chia để trị.
- Cài đặt được thuật toán tìm kiếm nhị phân bằng kĩ thuật đệ quy.
- Hiểu và mô tả được thuật toán giải bài toán tính an.
- Năng lực
Năng lực chung:
- Năng lực giao tiếp và hợp tác: biết chủ động trong giao tiếp, tự tin phát biểu ý kiến của bản thân về kĩ thuật đệ quy trong chia để trị.
- Năng lực tự chủ và tự học: Xác định được nhiệm vụ học tập Chuyên đề môn Tin học 11 – Khoa học máy tính qua việc tìm hiểu ý tưởng kĩ thuật đệ quy trong bài toán tìm kiếm nhị phân và cài đặt thuật toán tìm kiếm nhị phân bằng kĩ thuật đệ quy.
- Năng lực giải quyết vấn đề và sáng tạo: Vận dụng các kiến thức giải quyết được các vấn đề liên quan.
Năng lực riêng:
- Năng lực giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông: Xác định được ý tưởng kĩ thuật đệ quy trong bài toán tìm kiếm nhị phân và cài đặt thuật toán tìm kiếm nhị phân bằng kĩ thuật đệ quy.
'2. Phẩm chất
- Chăm chỉ: có ý thức đánh giá điểm mạnh, điểm yếu của bản thân, thuận lợi, khó khăn trong học tập để xây dựng kế hoạch học tập; tích cực tìm tòi và sáng tạo trong học tập, có ý chí vượt qua khó khăn để đạt kết quả tốt trong học tập.
- Trách nhiệm: tích cực, tự giác và nghiêm túc rèn luyện, tu dưỡng đạo đức; sẵn sàng chịu trách nhiệm về lời nói và hành động của bản thân.
- THIẾT BỊ DẠY HỌC
- Đối với giáo viên
- Giáo án, sách CĐHT, SGV Tin học 11 – Khoa học máy tính bộ Cánh diều.
- Máy tính cá nhân có cài đặt phần mềm mô phỏng thuật toán, máy chiếu, màn hình chiếu.
- Đối với học sinh
- Vở ghi, sách CĐHT Tin học 11 – Khoa học máy tính bộ Cánh diều.
- Tư liệu có liên quan đến nội dung bài học và dụng cụ học tập.
III. TIẾN TRÌNH DẠY HỌC
- HOẠT ĐỘNG KHỞI ĐỘNG (MỞ ĐẦU)
- a) Mục tiêu: Dẫn dắt đưa ra vấn đề để học sinh suy nghĩ khơi gợi hứng thú học tập, làm quen với kĩ thuật đệ quy trong chia để trị.
- b) Nội dung: HS trả lời câu hỏi mở đầu có nội dung liên quan đến bài học.
- c) Sản phẩm: HS mô tả từng bước thu hẹp phạm vi tìm kiếm trong một ví dụ và phân tích sự lặp lại của các bước dẫn đến sự phù hợp của cài đặt đệ quy cho thuật toán tìm kiếm nhị phân.
- d) Tổ chức thực hiện:
Bước 1: Chuyển giao nhiệm vụ:
- GV yêu cầu HS trả lời câu hỏi phần Khởi động trang 31 sách CĐHT:
Trong Bài 1, em đã biết thuật toán tìm kiếm nhị phân bằng vòng lặp. Việc loại bỏ đi một nửa dãy sau mỗi bước và tìm kiếm phần tử trên một nửa dãy còn lại cũng phù hợp với việc cài đặt đệ quy do các bước làm chỉ khác nhau ở phạm vi tìm kiếm trên một ví dụ trong Hình 4 của Bài 1 để thấy sự lặp lại thuật toán trên bài toán con so với bài toán cha.
Bước 2: Thực hiện nhiệm vụ học tập:
- HS đọc SGK, thực hiện công não để có câu trả lời cho các câu hỏi.
Bước 3: Báo cáo, thảo luận:
- Các học sinh xung phong phát biểu trả lời.
Bước 4: Kết luận và nhận xét:
- GV nhận xét, đánh giá và dẫn vào bài: Để trả lời câu hỏi này, chúng ta cùng nhau đi tìm hiểu bài học ngày hôm nay: Bài 2. Kĩ thuật đệ quy trong chia để trị.
- HÌNH THÀNH KIẾN THỨC MỚI
Hoạt động 1: Tìm hiểu một số ví dụ về đệ quy
- a) Mục tiêu: Nêu được ý tưởng kĩ thuật đệ quy trong bài toán tìm kiếm nhị phân và làm quen với bài toán sử dụng kĩ thuật đệ quy trong chia để trị.
- b) Nội dung: HS thảo luận, đọc sách CĐHT trang 31,32 để tìm hiểu nội dung cài đặt thuật toán tìm kiếm nhị phân bằng đệ quy.
- c) Sản phẩm: Nêu được các bước thực hiện thuật toán tìm kiếm nhị phân và chạy thử chương trình đệ quy tìm kiếm nhị phân.
- d) Tổ chức thực hiện:
|
HOẠT ĐỘNG CỦA GV VÀ HS |
SẢN PHẨM DỰ KIẾN |
|
Bước 1: GV chuyển giao nhiệm vụ học tập - GV yêu cầu HS đọc nội dung trang 31 sách CĐHT và trả lời câu hỏi sau: + Thuật toán tìm kiếm nhị phân được mô tả chi tiết như thế nào? - GV yêu cầu HS thảo luận cặp đôi, nghiên cứu sách CĐHT và trả lời câu hỏi Hoạt động 1 trang 31: Tìm hiểu Bước 3 và Bước 4 trong thuật toán tìm kiếm nhị phân để rút ra kĩ thuật đệ quy cài đặt thuật toán này. Hai bước trên có thể cài đặt bởi lời gọi đệ quy đến hàm tìm kiếm nhị phân tổng quát với tham số đầu vào là khoảng cần tìm kiếm trong dãy số. Em hãy đọc hiểu chương trình Python mẫu trong Hình 1 và chạy thử nghiệm trên các bộ dữ liệu đầu vào khác nhau. - GV có thể mô tả lại thuật toán tìm kiếm nhị phân trên một ví dụ khác. - GV hướng dẫn HS phân tích chương trình mẫu để nổi bật được Bước 3 và Bước 4 và yêu cầu HS thử nghiệm chương trình trên các bộ dữ liệu đầu vào khác nhau. - GV kết luận về cài đặt thuận toán tìm kiếm nhị phân bằng đệ quy. Bước 2: Thực hiện nhiệm vụ - HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi. Bước 3: Báo cáo, thảo luận - Đại diện nhóm HS báo cáo. - Một số HS nhóm khác nhận xét, bổ sung cho bạn. Bước 4: Kết luận, nhận định - GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS. - GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở. |
1. Cài đặt thuật toán tìm kiếm nhị phân bằng đệ quy - Thuật toán tìm kiếm nhị phân được mô tả chi tiết từng bước thực hiện như sau: Bước 1: So sánh x với phần tử nằm ở vị trí giữa dãy số, gọi là phần tử giữa. Bước 2: Nếu x bằng với giá trị phần tử giữa, đưa ra vị trí phần tử tìm được. Bước 3: Nếu x lớn hơn giá trị phần tử giữa, giá trị x chỉ có thể nằm ở nửa bên phải phần tử giữa của dãy số. Quay lại Bước 1, tiếp tục áp dụng thuật toán đối với nửa dãy số bên phải này. Bước 4: Nếu x nhỏ hơn giá trị phần tử giữa, giá trị x chỉ có thể nằm ở nửa bên trái phần tử giữa của dãy số. Quay lại Bước 1, tiếp tục áp dụng thuật toán đối với nửa dãy số bên trái này.
- Chức năng hoạt động của Bước 3 và Bước 4 trong thuật toán tìm kiếm nhị phân hoàn toàn giống nhau chỉ khác là thực hiện ở phạm vi nào trong dãy số. Đồng thời chức năng hoạt động của hai bước này của hai bước này cũng hoàn toàn giống với chức năng hoạt động của thuật toán trên toàn dãy số.
*Kết luận - Thuật toán tìm kiếm nhị phân phù hợp để cài đặt bằng kĩ thuật đệ quy do việc học lại chức năng thuật toán của các bài toán con. |
Hoạt động 2: Tìm hiểu bài toán Tính an
- a) Mục tiêu: HS hiểu được cách thiết lập thuật toán tính lũy thừa nhanh bằng chia để trị.
- b) Nội dung: HS thảo luận, đọc sách CĐHT trang 33, 34 để tìm hiểu nội dung giải bài toán tính lũy thừa bằng chia để trị.
- c) Sản phẩm: HS giải được bài toán tính lũy thừa bằng cách nhanh nhất và rút ra cách giải bài toán này.
- d) Tổ chức thực hiện:
|
HOẠT ĐỘNG CỦA GV VÀ HS |
SẢN PHẨM DỰ KIẾN |
|
Bước 1: GV chuyển giao nhiệm vụ học tập - GV mô tả bài toán và yêu cầu các nhóm giải bài này bằng cách nhanh nhất. - GV gợi ý HS đọc nội dung sách CĐHT và tham khảo cách làm của bạn Thanh An. - GV yêu cầu HS đọc nội dung trang 33 sách CĐHT và trả lời câu hỏi sau: + Em hãy giúp Thanh An mô tả chi tiết các bước tính giá trị 310 với số phép tính nhân phải sử dụng là ít nhất. - GV gợi ý cho HS quan sát Hình 3 và rút ra ra cách làm nhanh nhất dựa trên việc xét riêng hai trường hợp số mũ chẵn và số mũ lẻ. - GV giới thiệu ý tưởng mới giải bài toán tính lũy thừa theo kĩ thuật chia để trị. - GV kết luận về giải bài toán tính lũy thừa bằng chia để trị. - GV yêu cầu HS làm việc theo cặp và trả lời câu hỏi Thực hành (SCĐ – tr33) Mô tả chi tiết tính an dùng chia để trị mà sử dụng số phép tính nhân là ít nhất. Viết hàm đệ quy tính an. Sau đó, viết chương trình nhập vào hai số nguyên dương a, n và hiển thị giá trị của an. Bước 2: Thực hiện nhiệm vụ - HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi, thực hành. Bước 3: Báo cáo, thảo luận - Đại diện nhóm HS báo cáo. - Một số HS nhóm khác nhận xét, bổ sung cho bạn. Bước 4: Kết luận, nhận định - GV nhận xét kết quả thảo luận nhóm. - GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở. |
2. Bài toán Tính an - Bài toán: Tính giá trị của 310 bằng cách nhanh nhất. - Có hai trường hợp: an = an/2 x an/2, nếu n chẵn. an = a x an-1 nếu n lẻ và n > 1.
*Kết luận: - Bài toán tính an được giải hiệu quả bằng kĩ thuật đệ quy trong phương pháp chia để trị nhờ việc xét trường hợp n chẵn và n lẻ. |
- HOẠT ĐỘNG LUYỆN TẬP
- a) Mục tiêu: HS củng cố lại kiến thức về kĩ thuật đệ quy trong chia để trị.
- b) Nội dung: HS hoạt động cá nhân trả lời câu hỏi liên quan đến kĩ thuật đệ quy trong chia để trị.
- c) Sản phẩm: Hướng dẫn trả lời câu hỏi liên quan đến thiết kế thuật toán đệ quy.
- d) Tổ chức thực hiện
--------------- Còn tiếp ---------------
Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II
MỘT VÀI THÔNG TIN
- Giáo án bản word, dễ dàng chỉnh sửa nếu muốn
- Font chữ: Time New Roman, trình bày rõ ràng, khoa học.
- Giáo án có đủ các chuyên đề, đủ cả năm
PHÍ GIÁO ÁN:
- Phí giáo án: 350k
=> Khi đặt, nhận đủ giáo án cả năm ngay và luôn
CÁCH ĐẶT:
- Bước 1: gửi phí vào tk: 10711017 - Chu Văn Trí - Ngân hàng ACB (QR)
- Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo và nhận giáo án
=> Khi đặt, sẽ nhận giáo án ngay và luôn. Tặng kèm phiếu trắc nghiệm + đề kiểm tra ma trận
Xem toàn bộ: Giáo án chuyên đề Tin học 11 Khoa học máy tính cánh diều đủ cả năm