Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 4 Thực hành tổng hợp: Ứng dụng cây tìm kiếm nhị phân

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 nêu các yêu cầu thực hành và nội dung cụ thể cần thực hiện.

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

- HS chú ý lắng nghe.

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

- HS hiểu rõ các yêu cầu thực hành và nội dung cụ thể cần thực hiện.

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

- GV tổng kết lại các yêu cầu và nội dung thực hành.

YÊU CẦU

Lớp chia thành các nhóm, sản phẩm của mỗi nhóm qua bài thực hành tổng hợp này bao gồm:

Thực hành 1: Mô tả các bước thực hiện thuật toán cho các yêu cầu trong bài toán.

Thực hành 2: Mô phỏng chi tiết các bước ứng dụng cây tìm kiếm nhị phân giải quyết bài toán đối với một ví dụ cụ thể.

Thực hành 3: Viết chương trình duyệt cây nhị phân theo thứ tự giữa.

Thực hành 4: Kết quả thử nghiệm trên các bộ dữ liệu đầu vào mẫu và tự tạo.

NỘI DUNG CỤ THỂ CẦN THỰC HIỆN

Gia đình Hương Trà làm kinh doanh, thường xuyên nhập về kho các mặt hàng có mã khác nhau. Mỗi lần có một mặt hàng nhập về kho, gia đình Hương Trà thường ghi chép lại bằng tay để quản lí. Sau khi được học về cây tìm kiếm nhị phân, Hương Trà muốn viết chương trình quản lí hàng hoá cho gia đình mình. Hương Trà dự định sử dụng cây tìm kiếm nhị phân để quản lí hàng hoá, mỗi nút trên cây sẽ lưu trữ thông tin của một mặt hàng. Hương Trà hiểu là một mặt hàng có nhiều thông tin cần quản lí như: giá trị, số lượng, ngày xuất/nhập, nguồn gốc,... Do mới học cây tìm kiếm nhị phân với mỗi nút chứa thông tin một khoá, Hương Trà dự kiến xây dựng cây tìm kiếm nhị phân để quản lí một thông tin là mã mặt hàng, rồi sẽ tìm hiểm thêm để mở rộng sang bài toán quản lí nhiều thông tin mặt hàng. Cụ thể, Hương Trà sẽ xây dựng cây tìm kiếm nhị phân, mỗi nút có khoá là mã của một mặt hàng sao cho có thể thuận lợi để thực hiện các yêu cầu sau đây:

1. Mỗi lần một mặt hàng được nhập về, Hương Trà sẽ chèn vào cây tìm kiếm nhị phân một nút có khoá là mã của mặt hàng đó.

2. Trả lời có tồn tại mặt hàng trong kho có mã bằng x cho trước hay không.

3. Đưa ra danh sách mã các món hàng trong kho theo thứ tự tăng dần.

4. Đưa ra danh sách các mặt hàng có mã trong khoảng từ min đến max.

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 phân tích các nhiệm vụ trong bài thực hành và hướng dẫn HS phân công thành viên trong nhóm ôn lại các thuật toán tương ứng với 4 yêu cầu ở trên để mô tả các thuật toán.

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

- HS mô tả các bước thực hiện thuật toán cho bốn yêu cầu trong bài toán đã trên.

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

- HS báo cáo kết quả thực hiện hoạt động Thực hành 1.

- GV kiểm tra kết quả thực hiện hoạt động Thực hành 1 của HS.

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

- Từ kết quả của hoạt động Thực hành 1, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

Thực hành 1. Mô tả các bước thực hiện thuật toán cho bốn yêu cầu trong bài toán nêu trên

- Đầu vào của bài toán là một tập các phần tử có giá trị là mã các mặt hàng được nhập vào lần lượt. 

- Các yêu cầu của bài toán cần được mô tả chi tiết các bước thực hiện thuật toán như sau:

1. Đầu tiên, khởi tạo một cây tìm kiếm nhị phân rỗng. Với mỗi mã mặt hàng được nhập vào, tạo một nút mới có khoá là mã mặt hàng vừa nhập và chèn nút vào đúng vị trí trên cây tìm kiếm nhị phân.

2. Với một giá trị x nhập vào, thực hiện thao tác tìm kiếm giá trị khoá x trên cây tìm kiếm nhị phân.

3. Thực hiện phép duyệt cây tìm kiếm nhị phân theo thứ tự giữa sẽ thu được danh sách các mã mặt hàng được đưa ra theo thứ tự giá trị khoá tăng dần.

4. Thực hiện phép duyệt cây tìm kiếm nhị phân theo thứ tự giữa. Trong khi duyệt, nếu gặp nút có giá trị khoá nhỏ hơn min hoặc có giá trị khoá lớn hơn max thì dừng việc duyệt đến các nút con của nó và tiếp tục quay lại quá trình duyệt cho các nhánh khác.

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 yêu cầu các nhóm HS thảo luận và thực hiện hoạt động Thực hành 2 theo hướng dẫn.

Hướng dẫn: Mỗi nhóm chọn một ví dụ cụ thể và mô phỏng chi tiết từng bước trên ví dụ đó, bao gồm:

• Khởi tạo cây tìm kiếm nhị phân.

• Chèn từng mã mặt hàng vào cây.

• Tìm kiếm một mã mặt hàng trên cây.

• Duyệt cây theo thứ tự giữa tìm nút có giá trị khoá x.

• Duyệt cây theo thứ tự giữa đưa ra danh sách các nút có giá trị khoá trong khoảng từ min đến max.

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

- HS thực hiện hoạt động Thực hành 2 theo hướng dẫn.

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

- HS báo cáo kết quả thực hiện hoạt động Thực hành 2.

- GV kiểm tra kết quả thực hiện hoạt động Thực hành 2.

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

- Từ kết quả của hoạt động Thực hành 2, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

Thực hành 2. Mô phỏng chi tiết các bước ứng dụng cây tìm kiếm nhị phân giải quyết bài toán đối với một ví dụ cụ thể

Mỗi nhóm chọn một ví dụ cụ thể và mô phỏng chi tiết từng bước trên ví dụ đó theo hướng dẫn.