Các bài khác
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 1 Khái niệm đệ quy và ví dụ (P1)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 1 Khái niệm đệ quy và ví dụ (P2)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 2 Thuật toán đệ quy (P1)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 2 Thuật toán đệ quy (P2)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 3 Thực hành thiết kế thuật toán đệ quy (P1)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 3 Thực hành thiết kế thuật toán đệ quy (P2)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 4 Thực hành tổng hợp thiết kế thuật toán đệ quy (P1)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 4 Thực hành tổng hợp thiết kế thuật toán đệ quy (P2)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 1 Ý tưởng chia để trị
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 2 Kĩ thuật đệ quy trong chia để trị
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 3 Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 4 Kĩ thuật chia để trị trong thuật toán sắp xếp trộn (P1)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 4 Kĩ thuật chia để trị trong thuật toán sắp xếp trộn (P2)
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 5 Thực hành tổng hợp ứng dụng chia để trị
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 1 Kĩ thuật duyệt
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 2 Kĩ thuật quy lui
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 3 Thực hành kĩ thuật quay lui
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 4 Thực hành tổng hợp kĩ thuật duyệt
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 5 thực hành kĩ thuật quy lui giải bài toán xếp hậu
- Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 6 Dự án xây dựng chương trình sử dụng kĩ thuật duyệt
Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 2 Kĩ thuật quy lui
Mẫu giáo án chuyên đề khoa học máy tính 11 cánh diều. Chi tiết chuyên đề bài 2 Kĩ thuật quy lui. Giáo án được biên soạn chi tiết. Có thể tải về tham khảo. Cách tải nhanh chóng, dễ dàng. Ngoài ra, hệ thống có đủ giáo án các bài khác của chuyên đề khoa học máy tính 11 cánh diều
Nội dung giáo án
Ngày soạn: .../.../...
Ngày dạy: .../.../...
BÀI 2. KĨ THUẬT QUAY LUI (2 tiết)
- MỤC TIÊU
- Kiến thức
Sau bài học này, HS sẽ:
- Tìm hiểu được chương trình liệt kê dãy bít độ dài bằng kĩ thuật đệ quy.
- Nêu được ý tưởng của kĩ thuật quay lui.
- Tìm hiểu được lời giải một số bài toán sử dụng kĩ thuật quay lui.
- 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ề ý tưởng của kĩ thuật quay lui.
- 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 của kĩ thuật quay lui.
- 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 quay lui và giải bài toán bằng kĩ thuật quay lui.
- Năng lực ứng dụng công nghệ thông tin và truyền thông trong học và tự học: Biết được ý tưởng kĩ thuật quay lui vẫn thường xuất hiện trong các sự vật, sự việc ta gặp hàng ngày.
'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 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: Gợi ý câu trả lời của HS.
- 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 49 sách CĐHT:
Trong bài học trước, các em đã tìm hiểu bài toán Chọn mua đồ dùng học tập với các tình huống mua một đồ dùng hoặc hai đồ dùng. Nếu bài toán không cố định số lượng đồ dùng cần mua mà có thể mua một số đồ dùng với tổng giá không vượt quá T (đồng) với tổng mức độ yêu thích của các đồ dùng đó là lớn nhất, em hãy trình bày ý tưởng giải quyết bài toán.
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: Để có câu trả lời tổng quát cho bài toán này, chúng ta cùng đi tìm hiểu bài học ngày hôm nay: Bài 2. Kĩ thuật quay lui.
- HÌNH THÀNH KIẾN THỨC MỚI
Hoạt động 1: Bài toán Mua đồ tổng quát
- a) Mục tiêu: Nhận biết được nhu cầu liệt kê dãy bit độ dài .
- b) Nội dung: HS thảo luận, đọc sách CĐHT trang 55 tìm hiểu hoạt động 1 để thấy được nhu cầu của liệt kê dãy bit độ dài .
- c) Sản phẩm: HS hình thành được kiến thức bài học về nhu cầu liệt kê dãy bit độ dài , câu trả lời của HS cho các câu hỏi.
- 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 thảo luận cặp đôi, nghiên cứu Bài toán tổng quát mua đồ dùng học tập và hoàn thành yêu cầu phần hoạt động.
- GV mời 1 HS đứng tại chỗ trả lời. - GV nhận xét, kết luận “Để giải quyết bài toán Mua đồ tổng quát bằng kĩ thuật duyệt ta có thể xét toàn bộ dãy bit độ dài , mỗi dãy bit tương ứng với một phương án mua”.
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. Bài toán Mua đồ tổng quát Hoạt động 1 Lời giải bài toán này có thể biểu diễn bằng 1 dãy bit độ dài (là số lượng đồ vật), trong đó bit thứ () bằng 1 hoặc 0 tương ứng là vật thứ được chọn hoặc không chọn. Ví dụ: dãy bit (1, 0, 0, 1, 0) tương ứng với cách chọn đồ dùng số 0 và 3 với tổng giá là 10 + 9 = 19 (nghìn đồng) và mức độ yêu thích là 7 + 6 = 13; dãy bit (1, 1, 0, 0, 1) tương ứng với cách chọn đồ dùng số 0, 1 và 4 có tổng giá là 10 + 5 + 5 = 20 (nghìn đồng) và mức độ yêu thích là 7 + 2 + 3 = 12.
|
Hoạt động 2: Liệt kê dãy bit độ dài bằng kĩ thuật đệ quy
- a) Mục tiêu: Tìm hiểu được chương trình liệt kê dãy bít độ dài bằng kĩ thuật đệ quy.
- b) Nội dung: HS thảo luận, đọc sách CĐHT tìm hiểu hoạt động 2 để tìm hiểu được chương trình liệt kê dãy bit độ dài bằng kĩ thuật đệ quy.
- c) Sản phẩm: HS hình thành được kiến thức bài học về liệt kê dãy bit độ dài bằng kĩ thuật đệ quy, câu trả lời của HS cho các câu hỏi.
- 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 thảo luận cặp đôi, tìm hiểu chương trình liệt kê dãy bit độ dài bằng kĩ thuật đệ quy và hoàn thành yêu cầu hoạt động 2.
- GV yêu cầu HS tìm hiểu SCĐ đưa ra cách xây dựng dãy nhị phân theo thuật toán đệ quy.
- GV giải thích cho HS quá trình xây dựng các dãy nhị phân với độ dài - GV tổng hợp, giải thích cụ thể trên các lệnh của chương trình và nhận định “Để trả lời số lượng dãy bit nhị phân độ dài , ta có thể tính theo công thức ”. - GV yêu cầu HS dùng kết quả trên để kiểm tra chương trình. 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ở. |
2. Liệt kê dãy bit độ dài bằng kĩ thuật đệ quy Hoạt động 2 Dãy bit độ dài có dạng , trong đó bằng 0 hoặc có thể mô tả theo cách đệ quy như sau: - Nếu thì phần tử đầu tiên của dãy bằng 0 hoặc 1 và phần tử sau là dãy bit độ dài . - Ngược lại, nếu thì dãy bit độ dài là dãy rỗng. Việc xây dựng các dãy nhị phân theo thuật toán đệ quy như sau: 1. Bắt đầu từ rỗng, lệnh và gọi thủ tục đệ quy backtrack(0) để xây dựng bắt đầu từ phần tử 0. 2. Thành phần sẽ lần lượt nhận giá trị 0 và 1 bằng lệnh for v in range(2): Với mỗi giá trị của vào cuối . Sau đó tiếp túc gọi đệ quy để xây dựng các thành phần còn lại (từ thành phần đến thành phần ). 3, Để xét được khả năng tiếp theo, hành động quay lui được thực hiện bằng cách loại bỏ ghi nhận thành phần cuối cùng của bằng lệnh x.pop(). Việc quay lui cũng được diễn ra khi đang xây dựng thành phần mà đã lần lượt nhận cả hai giá trị 0 và 1, khi đó thành phần sẽ bị loại khỏi và lùi về để xét khả năng tiếp theo cho thành phần . Dãy trong hình chữ nhật là dãy bit trong quá trình xây dựng, số trong hình ô van là thứ tự gọi đệ quy trong quá trình xây dựng.
|
Hoạt động 3: Kĩ thuật quay lui
- a) Mục tiêu: Nêu được ý tưởng của kĩ thuật quay lui và nhận biết được lời giải một số bài toán sử dụng kĩ thuật quay lui.
- b) Nội dung: HS thảo luận, đọc sách CĐHT tìm hiểu về kĩ thuật quay lui.
- c) Sản phẩm: HS hình thành được kiến thức bài học về kĩ thuật quay lui, câu trả lời của HS cho các câu hỏi.
- 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 thảo luận cặp đôi, nghiên cứu cách xây dựng lời giải của bài toán có dạng: với (trong đó là tập các giá trị có thể của . - GV khái quát, giải thích kĩ thuật quay lui.
- GV yêu cầu HS tìm hiểu mô hình kĩ thuật quay lui.
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ở. |
3. Kĩ thuật quay lui Xây dựng lời giải dần từng bước: 1. Bắt đầu từ lời giải rỗng []. 2. Giả sử, hiện tại đang xây dựng được thành phần , để xây dựng thành phần , cần xét từng khả năng trong . - Nếu xây dựng xong lời giải thì lời giải sẽ được kiểm tra đánh giá và chọn nghiệm. Nếu chưa xây dựng xong lời giải thì xây dựng tiếp thành phần . - Nếu đã xét xong các khả năng cho thành phần thì quay lui xét khả năng tiếp theo của thành phần . Quá trình sẽ dừng lại khi tất cả các khả năng lựa chọn của các thành phần của lời giải đều đã được xét. - Khi cài đặt kĩ thuật quay lui, người ta sử dụng kĩ thuật để quy để xây dựng tất các các khả năng của lời giải, với mỗi khả năng kiểm tra đánh giá để chọn nghiệm. |
Thông tin tải tải liệu
Nhận xét
Đánh giá trung bình
Chi tiết
Kho tài liệu Tin học 11 cánh diều
Giáo án lớp 11 cánh diều chương trình mới bản chuẩn
1. Giáo án ban tự nhiên
- Giáo án toán 11 cánh diều chuẩn nhất
- Giáo án vật lí 11 cánh diều chuẩn nhất
- Giáo án sinh học 11 cánh diều chuẩn nhất
- Giáo án hoá học 11 cánh diều chuẩn nhất
- Giáo án tiếng anh 11 cánh diều chuẩn nhất
2. Giáo án ban xã hội
- Giáo án ngữ văn 11 cánh diều chuẩn nhất
- Giáo án lịch sử 11 cánh diều chuẩn nhất
- Giáo án Địa lí 11 cánh diều chuẩn nhất
- Giáo án kinh tế pháp luật 11 cánh diều chuẩn nhất
3. Giáo án các môn khác
Giáo án tin học cánh diều bản chuẩn, đầy đủ
Tin học cánh diều THPT
- Giáo án Tin học 10 Cánh diều chuẩn nhất
- Giáo án Tin học 11 Cánh diều chuẩn nhất
- Giáo án Tin học 12 Cánh diều chuẩn nhất
Tin học cánh diều THCS
- Giáo án Tin học 6 Cánh diều chuẩn nhất
- Giáo án Tin học 7 Cánh diều chuẩn nhất
- Giáo án Tin học 8 Cánh diều chuẩn nhất
- Giáo án Tin học 9 Cánh diều chuẩn nhất