Tải bản chuẩn giáo án chuyên đề Khoa học máy tính 11 Cánh diều CĐ 3 Bài 5: thực hành kĩ thuật quy lui giải bài toán xếp hậu
Tải bản chuẩn giáo án chuyên đề học tập Khoa học máy tính 11 bộ sách mới cánh diều CĐ 3 Bài 5: thực hành kĩ thuật quy lui giải bài toán xếp hậu. giáo án soạn ch1 t1ết, hướng dẫn học sinh hoạt động để tìm tò1, khám phá ra k1ến thức mới, vận dụng chúng vào v1ệc giải quyết các vấn đề của học tập và của thực tiễn cuộc sống. Mờ1 thầy cô kéo xuống tham khảo
Rõ nét về file powerpoint trình chiếu. => Xem thêm
Ngày soạn: .../.../...
Ngày dạy: .../.../...
BÀI 5. THỰC HÀNH KĨ THUẬT QUAY LUI GIẢI BÀI TOÁN XẾP HẬU (2 tiết)
- MỤC TIÊU
- Kiến thức
Sau bài học này, HS sẽ:
- Hiểu được các bước giải 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ề cách sử dụng kĩ thuật quay lui để giải bài toán xếp hậu.
- 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 viết chương trình đơn giả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: Viết và thực hiện được chương trình các bài toán bằng các sử dụ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: Ô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 giới thiệu bài toán Xếp hậu: “Cần đặt n quân hậu lên bàn cờ vua kích thước , sao cho không có hai quân hậu nào tấn công nhau (tức là không có hai quân nào cùng hàng, cùng cột hoặc cùng đường chéo).”
Em hãy thiết lập chương trình giải bài toán trê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: Bài toán Xếp hậu là một bài toán nổi tiếng và thú vị, để tìm lời giải 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 5. Thực hành kĩ thuật quay lui giải bài toán xếp hậu.
- HÌNH THÀNH KIẾN THỨC MỚI
Hoạt động: Bài toán Xếp hậu
- a) Mục tiêu: Nhận biết được các bước giải 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 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 giới thiệu bài toán Xếp hậu và cho HS xem các ví dụ trong những trường hợp khác nhau của bài toán.
- GV yêu cầu HS tìm hiểu cách giải, hướng dẫn HS theo gợi ý SCĐ. *Bước 1: GV đặt câu hỏi:
- Với n = 4 có hai cách đặt 4 quân hậu thỏa mãn, em hãy chỉ ra hai dãy số biểu diễn lời giải của hai cách đó theo dãy , hai dãy đó có đặc điểm gì? - GV giải thích cho HS về cách tấn công của quân hậu và đặt câu hỏi:
- Em hãy đưa ra điều kiện để kiểm tra hai quân hậu đặt ở hai ô và tấn công nhau?
- GV kết luận về điều kiện và hướng giải của bài toán.
- GV yêu cầu HS tìm hiểu chương trình giải quyết bài toán xếp hậu bằng kĩ thuật quay lui trong Hình 4, chạy thử nghiệm với và 10. - GV đặt câu hỏi: “giải thích ý nghĩa hàm check, printSolution, permutation”
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 Xếp hậu Bài toán: Cần đặt n quân hậu lên bàn cờ vua kích thước , sao cho không có hai quân hậu nào tấn công nhau (tức là không có hai quân nào cùng hàng, cùng cột hoặc cùng đường chéo).” Ví dụ 1: Trên bàn cờ Ví dụ 2: Trên bàn cờ Bưới 1: Thiết kế thuật toán theo kĩ thuật quay lui. - Trên bàn cờ, đánh số các dòng từ 0 đến theo chiều từ trên xuống dưới, các cột đánh số từ 0 đến theo chiều từ trái sang phải. Ô nằm giao của hàng và cột gọi là ô . - Nhận thấy, mỗi hàng có đúng một quân hậu, mỗi cột có đúng một quân hậu nên lời giải bài toán có thể được biểu diễn bằng một dãy là hoán vị của 0, 1, …, , trong đó, là chỉ số cột của quân hậu trên hàng thứ , nghĩa là quân hậu thứ sẽ được đặt ở ô . VD: với thì ).
*Trả lời câu hỏi HĐ1: Hai dãy (1, 3, 0, 2); (2, 0, 3, 1) biểu diễn cách đặt 4 quân hậu. Đây là hai hoán vị của 0, 1, 2, 3.
Quân hậu đặt ở ô sẽ tấn công các quân hậu đặt ở ô cùng hàng, cùng cột hoặc cùng đường chéo. *Trả lời câu hỏi HĐ2: hai quân hậu ở hai ô , tấn công nhau khi đặt cùng hàng hoặc cùng cột hoặc cùng đường chéo hoặc . - Dãy là hoán vị của dãy (0, 1, …, ) biểu diễn một cách đặt thỏa mãn nếu với mọi thì hai điều kiện sau thỏa mãn: và . - Dãy là hoán vị của 0, 1, …, , trong đó, là chỉ số cột của quân hậu trên hàng thứ , ta có thể giải quyết bài toán bằng cách sử dụng kĩ thuật quay lui để liệt kê tất cả các hoán vị của dãy (0, 1, …, ). Với mỗi hoán vị đó, tiến hành kiểm tra để chọn nghiệm. Bước 2: Xây dựng chương trình giải bài toán bằng kĩ thuật quay lui. *Trả lời câu hỏi HĐ3: Chạy thử nghiệm với và 10 sẽ tìm thấy số cách đặt thỏa mãn tương ứng là 2, 10, 92, 724. hàm check: Kiểm tra vị trí đứng của quân hậu. hàm printSolution: Gọi tên từng đáp án. hàm permutation: Liệt kê các hoán vị. |
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
Từ khóa tìm kiếm:
Tải bản chuẩn giáo án chuyên đề Khoa học máy tính 11 Cánh diều, giáo án chuyên đề học tập Khoa học máy tính 11 Cánh diều CĐ 3 Bài 5: thực hành kĩ thuật, soạn giáo án chuyên đề Khoa học máy tính 11 cánh diều CĐ 3 Bài 5: thực hành kĩ thuật