Kênh giáo viên » Giáo án chuyên đề Tin học 11 Định hướng khoa học máy tính kết nối tri thức

Giáo án chuyên đề Khoa học máy tính 11 kết nối Bài 15: Bài toán xếp hậu

Giáo án giảng dạy theo sách CGiáo án chuyên đề Khoa học máy tính 11 kết nối Bài 15. Bài toán xếp hậu. 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.

Hướng dẫn tải giáo án

Xem toàn bộ: Giáo án chuyên đề Tin học 11 Khoa học máy tính kết nối tri thức đủ cả năm

Ngày soạn:…/…/…

Ngày dạy:…/…/…

BÀI 15. BÀI TOÁN XẾP HẬU

I. MỤC TIÊU

1. Về kiến thức

Sau bài học này, HS sẽ:

- Biết và thực hiện được chương trình giải bài toán xếp Hậu trên bàn cờ.

- Thực hiện được lập trình cho bài toán xếp hậu theo kĩ thuật quay lui.

2. Năng lực

Năng lực chung:

- Năng lực tự chủ: Biết lựa chọn các nguồn tài liệu học tập phù hợp.

- Năng lực giải quyết vấn đề và sáng tạo: Xác định và tìm hiểu được các thông tin liên quan đến vấn đề, đề xuất giải pháp giải quyết vấn đề trong bài học.

- Năng lực giao tiếp và hợp tác: Thực hiện tốt nhiệm vụ trong hoạt động nhóm.

Năng lực tin học:

- Hình thành, phát triển 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.

3. Phẩm chất:

- Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.

- Có ý thức vận dụng kiến thức, kĩ năng đã học ở nhà trường vào thực tiễn.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU

1. Đối với giáo viên

- SGK, SGV, Giáo án;

- Máy tính đã cài đặt Python và máy chiếu;

- Hình ảnh, sơ đồ minh họa các bước thực hiện liên quan đến nội dung bài dạy.

2. Đối với học sinh

- SGK, vở ghi.

- Điện thoại có cài sẵn phần mềm Python (nếu có).

III. TIẾN TRÌNH DẠY HỌC

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu:

- HS làm quen với bài toán xếp 8 quân Hậu trên bàn cờ. Bài toán có thể mở rộng thành: Tìm tất cả các phương án xếp n quân Hậu trên bàn cờ vuông bậc n sao cho không quân nào khống chế quân nào.

b. Nội dung: GV cho các nhóm HS trao đổi đưa ra câu trả lời.

c. Sản phẩm học tập: Câu trả lời, dự đoán của HS.

d. Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV đặt vấn đề:

Trên bàn cờ vua chúng ta đều biết Hậu là quân cờ mạnh nhất vì nó có thể di chuyển theo tất cả các hướng ngang, dọc và chéo. Một bài toán vui rất nổi tiếng là tìm cách sắp xếp 8 quân Hậu trên bàn cờ sao cho không quân Hậu nào khống chế con nào. Em hãy thử tìm một cách xếp quân Hậu khác với cách xếp như hình sau:

Bài toán tìm tất cả các cách xếp 8 quân Hậu trên bàn cờ vua sao cho các quân Hậu không khống chế lẫn nhau được gọi là bài toán xếp Hậu (n-Queen Problem). Bài toán này được nhà bác học Đức Carl Friedrich Gauss nghiên cứu từ những năm 1850. Bài toán đã được mở rộng trên bàn cờ kích thước bất kì và vẫn đang được tiếp tục phát triển cho đến ngày nay.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS lắng nghe, suy nghĩ và đưa ra câu trả lời.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời HS trả lời câu hỏi.

- Các HS khác nhận xét, nêu ý kiến khác (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, đánh giá, tuyên dương câu trả lời của HS.

- GV dẫn dắt vào nội dung bài mới: - Bài 15. Bài toán xếp Hậu.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Tìm hiểu mô hình bài toán xếp Hậu trên bàn cờ vua tổng quát

a. Mục tiêu: HS biết được mô hình dữ liệu chính thức của bài toán từ đó có thể thiết lập được thuật toán giải bằng quay lui.

b. Nội dung: GV yêu cầu HS tìm hiểu Hoạt động 1 SGK trang 63, đọc thông tin mục 1, thảo luận nhóm và xây dựng kiến thức mới.

c. Sản phẩm học tập: HS nêu mô hình bài toán xếp Hậy trên bàn cờ vua.

d. Tổ chức hoạt động:

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 1 SGK trang 63:

Đọc, quan sát, trao đổi và thảo luận về bài toán xếp Hậu tổng quát và cách tiếp cận quay lui để giải bài toán.

- GV cho HS quan sát bàn cờ thực tế để HS thiết lập dữ liệu cho bài toán.

GV cho nhận xét, đánh giá, chốt phương án.

- GV giúp HS xác định điểm quan trọng: điều kiện xếp được quân Hậu tiếp theo tại cột k sau khi đã xếp xong tại các cột bên trái. Mệnh đề mô tả điều kiện của quân cờ tại cột k chính là điều kiện tính của sơ đồ thuật toán quay lui tổng quát đã học trong bài 13.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr65) để củng cố kiến thức:

+ Câu 1: Giả sử n = 4, A[0] = 2, A[1] = 0. Hãy tìm A[2].

+ Câu 2: Nếu n = 5, A[0] = 0, A[1] = 3. Tìm các khả năng của A[2].

Bước 2: HS thực hiện nhiệm vụ học tập

- Các nhóm HS tìm hiểu lời giải của bài toán viên bi giả trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình, hình thành kiến thức bài học.

- Đại diện các nhóm xung phong trả lời Câu hỏi.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm làm tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

1. Mô tả bài toán xếp Hậu trên bàn cờ vua

Hoạt động 1

Trong quá trình quay lui, ta sử dụng một mảng để lưu vị trí của các quân hậu đã đặt. Mỗi lần thêm một quân hậu mới, ta kiểm tra xem nó có đặt được ở vị trí đó không bằng cách kiểm tra xem quân hậu mới đó có trùng hàng, cột hay đường chéo với bất kỳ quân hậu nào đã đặt trước đó không.

Nếu quân hậu mới đó không thể đặt được ở vị trí đó, ta quay lại đặt lại quân hậu trước đó tại một vị trí khác và tiếp tục thử các vị trí khác cho đến khi tìm được vị trí thích hợp.

Với phương pháp này, ta sẽ duyệt qua tất cả các trường hợp có thể có và đưa ra được kết quả đúng của bài toán.

Kết luận

Ý tưởng tiếp cận duyệt quay lui giải bài toán xếp Hậu tổng quát là tìm kiếm trên tất cả các dãy dạng A[0] , A[1], …, A[n-1], trong đó A[k] là chỉ số hàng của quân Hậu tại cột thứ k.

Câu hỏi

Câu 1.

Với n = 4 A[0] = 2 A[1] = 0 thì A[2] = 3 (chỉ có 1 giá trị duy nhất).

Câu 2.

Với n = 5 A[0] = 0 A[1] = 3 thì A[2] = 1 (chỉ có 1 giá trị duy nhất).

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