Soạn giáo án chuyên đề Khoa học máy tính 11 cánh diều Chuyên đề 3 Bài 3: Thực hành kĩ thuật quay lui
Soạn chi tiết đầy đủ giáo án chuyên đề Khoa học máy tính 11 Chuyên đề 3 Bài 3: Thực hành kĩ thuật quay lui sách cánh diều. Giáo án soạn chuẩn theo Công văn 5512 để các thầy cô tham khảo lên kế hoạch bài dạy tốt. Tài liệu có file tải về và chỉnh sửa được. Hi vọng, mẫu giáo án này mang đến sự hữu ích và tham khảo cần thiết. Mời thầy cô tham khảo.
Nội dung giáo án
Ngày soạn: .../.../...
Ngày dạy: .../.../...
BÀI 3. THỰC HÀNH 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ê các hoán vị của n phần tử bằng kĩ thuật đệ quy.
- Tìm hiểu được một số bài toán sử dụng kĩ thuật quay lui.
- Nhận ra được mối liên quan giữa thiết kế thuật toán theo kĩ thuật quay lui và kĩ thuật đệ quy.
- 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 duyệt và 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 chương trình liệt kê các hoán vị của bằng kĩ thuật đề quy, một số bài toán sử dụng 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 mối liên quan giữa thiết kế thuật toán theo kĩ thuật quay lui và kĩ thuật đệ quy.
- 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: Ôn lại bài cũ, dẫn dắt đưa ra vấn đề để học sinh suy nghĩ khơi gợi hứng thú học tập.
- 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 ôn lại bài cũ: ý tưởng của kĩ thuật quay lui là gì?
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:
Gợi ý đáp án: Kỹ thuật quay lui xây dựng tất cả các khả năng của lời giải bằng cách mở rộng từng thành phần và quay lui, bắt đầu từ lời giải rỗng. Với cách làm này, kĩ thuật quay lui có thể xét tất cả các khả năng của lời giải và kiểm tra, đánh giá để chọn nghiệm của bài toán theo ý tưởng của kĩ thuật duyệt.
- GV nhận xét, đánh giá và dẫn vào bài: Giải các bài toán bằng kĩ thuật quay lui được thực hiện như thế nào? Mối quan hệ giữa thiết kế theo kĩ thuật quay lui và kĩ thuật đệ quy là gì? Chúng ta cùng đi tìm hiểu bài học ngày hôm nay: Bài 3. Thực hành kĩ thuật quay lui.
- HÌNH THÀNH KIẾN THỨC MỚI
Hoạt động 1: Bài toán 1. Trả tiền
- a) Mục tiêu: Viết và thực hiện được chương trình giải quyết bài toán.
- b) Nội dung: HS thảo luận, đọc sách CĐHT thực hiện yêu cầu của bài toán.
- c) Sản phẩm: Chạy được chương trình sử dụng kĩ thuật quay lui.
- d) Tổ chức thực hiện:
|
HĐ CỦA GV VÀ HS |
SẢN PHẨM DỰ KIẾN |
|
Bước 1: Chuyển giao nhiệm vụ - GV yêu cầu HS tìm hiểu bài toán 1, xác định dữ liệu vào và kết quả ra của bài toán.
- GV đặt câu hỏi: “Lời giải của bài toán được biểu diễn như thế nào?” - GV yêu cầu HS sử dụng kĩ thuật quay lui, viết chương trình giải quyết bài toán. - HS chạy thử chương trình trên. Bước 2: Thực hiện nhiệm vụ - Ở các nhiệm vụ, HS đọc sách CĐHT, chạy chương trình và trả lời câu hỏi. Bước 3: Báo cáo, thảo luận - HS báo cáo kết quả chạy chương trình và trả lời câu hỏi nhiệm vụ. Bước 4: Kết luận, nhận định - GV nhận xét kết quả chạy chương trình và trả lời câu hỏi của HS. - GV tổng quát lại kiến thức trọng tâm và lưu ý HS những lỗi sai. |
Bài toán 1. Trả tiền Kết quả chạy chương trình với các dữ liệu đầu vào: - Lời giải được biểu diễn bằng dãy bit độ dài , trong đó bit thứ bằng 1 tương ứng tờ tiền thứ được dùng. - Viết chương trình như sau: def updateSolution(): sum = 0 p = [] for i in range(n): if x[i] == 1: sum = sum + t[i] p = p + [i] if(sum==s): print(p) def backtrack(i): for v in range(2): x.append(v) if I == n-1: updateSolution() else: backtrack(i+1) x.pop() n, s = map(int,input().split()) t = list(map(int,input().split())) x = [] backtrack(0) |
Hoạt động 2: Bài toán 2. Liệt kê hoán vị của phần tử bằng kĩ thuật đệ quy
- a) Mục tiêu: Viết và thực hiện được chương trình giải quyết bài toán.
- b) Nội dung: HS thảo luận, đọc sách CĐHT thực hiện yêu cầu của bài toán.
- c) Sản phẩm: Nhận biết được bài toán liệt kê hoán vị của phần tử bằng kĩ thuật đệ quy.
- d) Tổ chức thực hiện:
|
HĐ CỦA GV VÀ HS |
SẢN PHẨM DỰ KIẾN |
|
Bước 1: Chuyển giao nhiệm vụ - GV yêu cầu HS tìm hiểu bài toán liệt kê hoán vị của phần tử, tìm cách định nghĩa dãy hoán vị bằng đệ quy.
- GV nhận xét, chốt lại: “Dãy hoán vị của phần tử là chọn cố định một phần tử trong phần tử đặt ở vị trí đầu tiên ghép với dãy hoán vị của phần tử còn lại.” - GV yêu cầu HS chạy chương trình thử nghiệm, thảo luận, trả lời các câu hỏi trong SCĐ – tr.61. + Câu a. HS chạy chương trình với các đầu vào để đưa ra kết quả. + Câu b. HS so sánh sự tương đồng giữa hai chương trình. + Câu c. HS dựa vào kiến thức đã được học trả lời câu hỏi.
+ Câu d. HS quan sát sơ đồ, tìm ra cách hoán vị các số điền số còn thiếu vào dấu “?”.
- GV tổng hợp, giải thích cụ thể trên các lệnh của chương trình. Bước 2: Thực hiện nhiệm vụ - Ở các nhiệm vụ, HS đọc sách CĐHT, chạy chương trình và trả lời câu hỏi. Bước 3: Báo cáo, thảo luận - HS báo cáo kết quả chạy chương trình và trả lời câu hỏi nhiệm vụ. Bước 4: Kết luận, nhận định - GV nhận xét kết quả chạy chương trình và trả lời câu hỏi của HS. - GV tổng quát lại kiến thức trọng tâm và lưu ý HS những lỗi sai. |
Bài toán 1. Trả tiền - Một hoán vị của 0, 1, … , là một dãy ( mà và các đôi một khác nhau. VD: với có 6 hoán vị của 0, 1, 2. - Hướng dẫn trả lời câu hỏi trang 61: a) Với có 6 hoán vị, Với có 24 hoán vị, Với có 120 hoán vị. b) Chương trình liệt kê các dãy bit độ dài với chương trình liệt kê các hoán vị của phần tử đều được áp dụng kĩ thuật đệ quy. c) Lệnh x.append(v): Ghi nhận thêm thành phần . Lệnh x.pop(): Loại bỏ ghi nhận thành phần cuối cùng. d) |
- 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 quay lui.
- 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 quay lui.
- c) Sản phẩm: Hướng dẫn trả lời câu hỏi liên quan đến kĩ thuật quay lui.
- d) Tổ chức thực hiện
Bước 1: Chuyển giao nhiệm vụ
- GV cho HS trả lời nhanh các câu hỏi trắc nghiệm về các nội dung liên quan đến kĩ
=> Xem toàn bộ Giáo án chuyên đề Khoa học máy tính 11 cánh diều
Soạn giáo án chuyên đề Khoa học máy tính 11 cánh diều Chuyên đề 3 Bài 3: Thực hành kĩ, GA word chuyên đề Khoa học máy tính 11 cd Chuyên đề 3 Bài 3: Thực hành kĩ, giáo án chuyên đề Khoa học máy tính 11 cánh diều Chuyên đề 3 Bài 3: Thực hành kĩ
Nâng cấp lên tài khoản VIP để tải tài liệu và dùng thêm được nhiều tiện ích khác
Xem thêm giáo án khác
GIÁO ÁN TỰ NHIÊN 11 CÁNH DIỀU
GIÁO ÁN XÃ HỘI 11 CÁNH DIỀU
GIÁO ÁN LỚP 11 CÁNH DIỀU CÁC MÔN CÒN LẠI
