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 16: Thực hành thiết kế thuật toán theo kĩ thuật duyệt quay lui

Giáo án giảng dạy theo sách Giáo án chuyên đề Khoa học máy tính 11 kết nối Bài 16. Thực hành thiết kế thuật toán theo kĩ thuật duyệt quay lui. 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 16. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT QUAY LUI

MỤC TIÊU
Về kiến thức

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

Ôn lại kĩ thuật duyệt quay lui để thiết kế thuật toán cho các bài toán tìm kiếm.
Thực hành kĩ thuật duyệt quay lui với một số bài toán phức tạp hơn.
Cài đặt kĩ thuật duyệt quay lui cho các bài toán tìm kiếm phức tạp.

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.

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.

THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
Đố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 cho các bước thực hiện trên một mẫu dữ liệu đơn giản.
Có thể dùng bàn cờ thật hoặc hình ảnh, phần mềm mô phỏng chơi cờ.

Đố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

HOẠT ĐỘNG KHỞI ĐỘNG
Mục tiêu:

- HS suy nghĩ về việc áp dụng kĩ thuật duyệt quay lui cho bài toán tìm đường mê cung và vấn đề sinh ra các nhánh tìm kiếm tại một vị trí của cây tìm kiếm trong bài toán này. Các bước đi tiếp theo là tất cả các hướng từ vị trí đó (hướng lên xuống trái phải trong bài toán mê cung).

Nội dung: GV cho các nhóm HS trao đổi câu hỏi Mở đầu.
Sản phẩm học tập: HS dựa vào kiến thức và hiểu biết cá nhân để đưa ra câu trả lời.
Tổ chức thực hiện:

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

- GV đặt câu hỏi yêu cầu HS thảo luận:

Chắc em đã nghe nói nhiều bài toán tìm đường đi trong mê cung. Nếu áp dụng kĩ thuật duyệt quay lui cho bài toán này thì làm thế nào để tìm ra các bước đi tiếp theo từ một vị trí?

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: Hôm nay, chúng ta sẽ vận dụng những kiến thức đã học để thực hành thiết kế thuật toán theo kĩ thuật duyệt quay lui- Bài 16. Thực hành thiết kế thuật toán theo kĩ thuật duyệt quay lui.

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

Hoạt động: Thực hành nhiệm vụ Giải bài toán mê cung

Mục tiêu: HS biết sử dụng kĩ thuật duyệt quay lui để thiết kế thuật toán cho các bài toán tìm kiếm.
Nội dung: GV yêu cầu HS tìm hiểu nhiệm vụ, tìm hiểu yêu cầu và các bước thực hiện.
Sản phẩm học tập: Các chương trình mà HS viết ra.
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 giới thiệu bài toán:

Giải bài toán mê cung.

Mê cung là một hình chữ nhật gồm m hàng, n cột ô được định nghĩa bằng một tệp dạng văn bản có tên maze.inp, trong đó các ô 0 là ô được đi, ô 1 tương ứng với tường và không được đi. Tại một vị trí có thể chọn một trong bốn hướng đi tiếp (lên, xuống, trái, phải). Giả sử vị trí xuất phát là ô bên trái phía trên, hãy tìm một đường đi đến ô bên phải phía dưới để thoát khỏi mê cung. Nếu tìm ra nghiệm thì in ra đường đi dưới dạng bảng trong đó vết của đường đi gồm các ô được thể hiện bằng số 1, các ô còn lại là số 0. Kết quả được thể hiện trên màn hình và ghi ra tệp maze.out. Ví dụ một thể hiện của dữ liệu đầu vào và ra như bảng bên.

- GV cho HS luyện tập cá nhân hoặc nhóm 2 -3 em. Yêu cầu:

+ Hiểu cấu trúc dữ liệu lưu trữ cấu trúc mê cung và vết đường đi được tìm thấy.

+ Hiểu ý tưởng thuật toán, triển khai ý tưởng bằng mã nguồn Python.

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

- HS chia nhóm, thảo luận thực hiện theo các bước SGK.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

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

- GV mời đại diện một số nhóm trình bày kết quả Nhiệm vụ.

- HS xung phong thực hiện các nhiệm vụ và giải thích.

- GV mời HS nhóm khác nhận xét, bổ sung.

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

- GV nhận xét, tổng kết, chuyển sang nội dung luyện tập.

Nhiệm vụ: Giải bài toán mê cung

- Ý tưởng thuật toán:

+ Quá trình tìm đường được bắt đầu tại vị trí bên phải phía trên.

+ Tại mỗi vị trí, thuật toán thử đi tiếp một bước theo một trong các hướng lên xuống trái phải. Nếu đi được thì cập nhật đường đi, nếu không thì thử hướng khác.

Nếu không có hướng nào hợp lệ thì quay lui.

+ Thiết lập mảng maze để lưu dữ liệu đầu vào của mê cung.

Thiết lập mảng sol để lưu vết đường đi trong mê cung. Ban đầu mảng sol sẽ gồm toàn số 0.

- Hàm quay lui để tìm đường đi chính là solveMaze(maze, m, n, x, y, sol), mê cung có m hàng, n cột, x, y là tọa độ của ô hiện thời để tìm đường đi tiếp. Hàm sẽ trả lại True nếu từ vị trí hiện thời thời (x, y) tìm được đường đi thoát khỏi mê cung, ngược lại sẽ trả về False. Sau đây là mã giả mô tả nhanh hàm solveMaze().

Chương trình:

(SGK -tr.69)

Giải thích:

+ Hàm readmaze() dùng để đọc dữ liệu từ tệp maze.inp, kết quả thông tin mê cung đưa vào mảng 2 chiều maze.

+ Hàm writemaze(outmaze) ghi mảng kết quả outmaze ra tệp maze.out.

+ Nếu ô hiện tại chưa là đích, tại dòng 25 kiểm tra xem ô này có được phép đi không, nếu có thì gán 1 tại ô hiện thời (dòng 28) và thử đi tiếp một bước theo một trong các hướng (lên, xuống, trái, phải). Nếu không đi được hoặc ô hiện tại không hợp lệ, trả lại giá trị False và quay lui về bước đi trước đó. Trước khi quay lui thì gán 0 tại ô hiện thời tại dòng 37.

+ Từ dòng 46, khởi tạo biển sol để lưu nghiệm và gọi hàm solveMaze để giải.

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