Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 8: Thực hành cây tìm kiếm nhị phân

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

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

BÀI 8: THỰC HÀNH CÂY TÌM KIẾM NHỊ PHÂN

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

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

• Hiểu được phương pháp cài đặt cây tìm kiếm nhị phân để mỗi nút chứa thông tin của một đối tượng gồm nhiều thuộc tính.

2. Năng lực

Năng lực chung: 

• Năng lực giao tiếp và hợp tác: Biết lựa chọn hình thức làm việc nhóm với quy mô phù hợp với yêu cầu và thực hiện tốt nhiệm vụ.

• Năng lực tự chủ và tự học: Chủ động học tập, tìm hiểu nội dung bài học, biết lắng nghe và trả lời nội dung trong bài học.

• Giải quyết vấn đề và sáng tạo: Trả lời được các câu hỏi, giải quyết được các vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

Năng lực Tin học:

• Vận dụng cây tìm kiếm nhị phân vào các bài toán cụ thể để tìm kiếm dữ liệu, đặc biệt trường hợp dữ liệu của các đối tượng gồm nhiều thuộc tính.

• Mô phỏng được thuật toán tạo cây tìm kiếm nhị phân, tìm kiếm một nút trên cây theo giá trị của khoá và cập nhật các thuộc tính của nút đó.

3. Phẩm chất

• Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.

• Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.

• Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua sản phẩm.

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

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

• Tài liệu, máy tính, máy trình chiếu.

• SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

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

• Vở ghi, máy tính.

• SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

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

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

a. Mục tiêu: Tạo tâm thế cho HS vào bài học mới.

b. Nội dung: HS quan sát các hình ảnh, suy nghĩ, thảo luận và trả lời câu hỏi. 

c. Sản phẩm học tập: Câu trả lời 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 cho HS thảo luận theo nhóm đôi.

- GV yêu cầu HS quan sát và trả lời câu hỏi Khởi động SGK trang 37: 

Trong Bài 7, cây tìm tìm kiếm nhị phân được cài đặt bằng mảng một chiều và mỗi nút của cây có khoá là một thuộc tính. Trong thực tế, một đối tượng có thể có nhiều thuộc tính. Ví dụ, với bài toán quản lí các món trong thực đơn, mỗi món có hai thuộc tính là tên và giá tiền. Trong trường hợp này, cây tìm kiếm nhị phân biểu diễn danh sách các món được cài đặt bằng mảng như thế nào và làm thế nào để mỗi nút của cây chứa hai thuộc tính là tên và giá tiền?

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

- HS tiếp nhận, thực hiện nhiệm vụ.

- GV hướng dẫn, hỗ trợ HS (nếu cần thiết).

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

- HS trình bày câu trả lời, các HS khác chú ý lắng nghe và nhận xét.

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

GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Ở các tiết trước, chúng ta đã được tìm hiểu về cây nhị phân, cây tìm kiếm nhị phân, bài học này chúng ta thực hành thiết lập cây tìm kiếm nhị phân và sử dụng để tra cứu tìm kiếm dữ liệu trong các trường hợp cụ thể. – Bài 8: Thực hành cây tìm kiếm nhị phân.

B. HOẠT ĐỘNG THỰC HÀNH

Hoạt động: Viết chương trình quản lí thực đơn.

a. Mục tiêu: HS được luyện tập thiết lập và sử dụng cây tìm kiếm nhị phân, áp dụng cho dữ liệu cụ thể, đặc biệt trường hợp quản lí các đối tượng có các thuộc tính khác ngoài khoá.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: HS viết được chương trình quản lí thực đơn.

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

C. HOẠT ĐỘNG LUYỆN TẬP

a. Mục tiêu: Giúp HS luyện tập kiến thức đã học.

b. Nội dung: GV giao nhiệm vụ cho HS, HS hoàn thành phần luyện tập SGK.

c. Sản phẩm học tập: Kết quả bài tập 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 yêu cầu HS hoạt động cá nhân, hoàn thành phần Luyện tập SGK tr.40)

Câu 1. Vẽ cây tìm kiếm nhị phân ứng với tệp menu.inp trong nhiệm vụ thực hành, lưu ý mỗi nút gồm hai thuộc tính name và price.

Câu 2. Mô tả quá trình tra cứu giá tiền món Bún chả thực hiện trên cây tìm kiếm nhị phân đã vẽ ở Luyện tập 1.

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

- HS suy nghĩ, hoàn thành các bài tập GV yêu cầu.

- GV quan sát và hỗ trợ, hướng dẫn.

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

- Mỗi bài tập GV mời 1 đến 2 HS trình bày. Các HS khác chú ý chữa bài, theo dõi nhận xét bài làm của các bạn.

Gợi ý đáp án: 

Câu 1. 

Để vẽ lại cây tìm kiếm nhị phân ứng với tệp menu.inp, đầu tiên cần sắp xếp tên các món ăn theo thứ tự từ điển để dễ so sánh các khoá khi chèn các nút vào cây. Thứ tự như sau:

Lưu ý: Do cây được cài đặt bằng mảng nên cây nhị phân thu được có thể có nhiều nút giả None và thực tế không có con trỏ left và right từ mỗi nút tới các nút con của nó. Thực hiện thuật toán chèn sẽ thu được cây như sau:

Cây nhị phân thực sự sau khi bỏ các nút giả None có thể được hình dung sau:

Câu 2.

Quá trình tìm kiếm bắt đầu bằng lời gọi hàm search(T,k = 0, name = "Bún chả”). Vì

“Bún chả" < T[0][0] = "Cơm suất cá thu sốt” nên theo thuật toán cần đi tìm theo nhánh trái. Thuật toán gọi hàm left(0) trả về giá trị 1 ứng với nút “Cơm sườn cốt lết.

Ở lần gọi hàm search thứ hai: search(T, k = 1, name = "Bún chả”) do “Bún chả" < T[1][0] = “Cơm sườn cốt lết” nên lại đi theo nhánh bên trái, left(1) = 3 ứng với nút “Bún chả.

Ở lần gọi hàm search thứ ba, search(T, k = 3, name = “Bún chả”) thì giá trị cần tìm “Bún chả” đã bằng với khoá của nút hiện tại nên giá trị k = 3 là chỉ số của nút cần tìm trong mảng T. Nút này có dữ liệu giá tiền T[3][1] là 60 000.

----------------------------------

------------------ Còn tiếp ---------------------