Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi

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

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

BÀI 5: THỰC HÀNH KIỂU DỮ LIỆU NGĂN XẾP VÀ HÀNG ĐỢI

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

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

• Biết cách kết hợp các kiểu dữ liệu hàng đợi và ngăn xếp để biểu diễn các loại dữ liệu khác nhau.

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:

• Sử dụng được cấu trúc dữ liệu ngăn xếp và hàng đợi.

3. Phẩm chất

• Có khả năng phân tích yêu cầu của bài toán để sử dụng kiểu dữ liệu ngăn xếp hoặc hàng đợi một cách phù hợp.

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 hứng thú học tập cho HS.

b. Nội dung: HS thảo luận nhóm và trả lời các câu hỏi phần Khởi động SGK tr.20. 

c. Sản phẩm học tập: Từ yêu cầu, HS vận dụng sự hiểu biết để trả lời các câu hỏi phần Khởi động SGK tr.20.

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

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

- GV chia lớp thành 3 – 4 nhóm học tập và nêu câu hỏi Khởi động SGK tr.20 cho các nhóm thảo luận: 

Trong bài trước, chúng ta đã sử dụng kiểu dữ liệu hàng đợi và ngăn xếp. Trong nhiều trường hợp ứng dụng trong thực tế chúng ta phải kết hợp cả hai loại dữ liệu này. Em có thể nêu được một ví dụ cần sử dụng cả hai kiểu dữ liệu này không?

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

- HS thảo luận theo nhóm và 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

- GV lần lượt mời các nhóm báo cáo kết quả thảo luận.

Gợi ý trả lời:

Ví dụ thực tế cần sử dụng cả kiểu dữ liệu hàng đợi (queue) và ngăn xếp (stack) là việc thực hiện kiểm tra biểu thức số học (arithmetic expression) để xem liệu biểu thức có được viết đúng (well-formed) hay không, đặc biệt là kiểm tra tính đúng đắn của dấu ngoặc.

Ví dụ: Kiểm tra tính đúng đắn của dấu ngoặc trong biểu thức

+ Ngăn xếp (Stack): Dùng để theo dõi các dấu ngoặc mở.

+ Hàng đợi (Queue): Dùng để lưu trữ biểu thức đã phân tích và kiểm tra trong trường hợp cần lưu trữ và xử lý lại sau khi kiểm tra dấu ngoặc.

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: Trong những tiết học trước, các em đã biểu diễn được ngăn xếp và hàng đợi bằng mảng một chiều, đồng thời viết được các chương trình con sử dụng các hàm cơ bản của kiểu dữ liệu ngăn xếp và hàng đợi. Tuy nhiên, trong nhiều bài toán thực tế, chúng ta cần phải kết hợp hai kiểu dữ liệu này. Vậy để giúp các em thực hiện được điều đó, chúng ta sẽ cùng nhau tìm hiểu Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi.

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

Nhiệm vụ: Viết chương trình mô phỏng bếp ăn tập thể

a. Mục tiêu: HS biết và nắm được cách sử dụng kiểu dữ liệu list trong Python để mô tả hàng đợi thông qua sơ đồ hoặc mô tả bằng lời, chưa cần lập trình.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1. Biểu diễn hàng đợi bằng mảng một chiều, 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 biểu diễn được hàng đợi bằng mảng một chiều.

d. Tổ chức thực hiệ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 yêu cầu HS hoạt động cá nhân, đọc và phân tích Nhiệm vụ SGK tr.20 sau đó thực hành theo hướng dẫn: Bài toán:  + Nhà ăn tập thể của một doanh nghiệp, phục vụ cho người lao động xếp hàng vào chọn suất ăn. Nhà ăn này chỉ có đúng hai loại là cơm gà và cơm bò. Mỗi người khi vào phải xếp hàng và đăng kí món ăn (gà hoặc bò). Thông tin đăng kí suất ăn sẽ được lưu trong tệp input1.inp như hình bên. Trong đó, mỗi hàng tương ứng với lượt đăng kí của một người, số đầu tiên là số định danh (ID của người đăng kí), theo sau là loại suất ăn mà người đó chọn. + Căn cứ vào tệp đã đăng kí, người quản lí sẽ cho người lao động xếp thành hai hàng, một hàng gồm toàn bộ những người đã chọn cơm gà, hàng còn lại gồm những người chọn cơm bò. + Do nhà bếp không biết trước thông tin đăng kí của người lao động nên sẽ chuẩn bị trước các suất ăn một cách ngẫu nhiên. Các suất ăn được chuẩn bị sẵn và được đưa vào một ngăn xếp, tổng số lượng các suất ăn bằng với tổng số người lao động. Thông tin các suất ăn đã chuẩn bị sẵn được lưu trong tệp input2.inp có dạng như sau: + Quy tắc nhà bếp hoạt động như sau: Mỗi lần người quản lí sẽ lấy một suất ăn trong ngăn xếp và đưa cho người đầu tiên trong hàng đợi tương ứng. Ví dụ, nếu suất ăn được lấy ra là cơm gà thì sẽ đưa cho người đầu tiên trong hàng chọn cơm gà. + Nếu số lượng các loại suất ăn không đúng với số lượng các suất ăn mà mọi người đăng kí, sẽ xảy ra hiện tượng một hàng đợi (ví dụ hàng đợi cơm gà) đã được phục vụ xong nhưng loại đó vẫn còn. Khi đó, người quản lí bắt buộc người đã đăng kí cơm bò phải chuyển sang cơm gà. Yêu cầu: Hãy viết chương trình mô phỏng quá trình trên. Nhận đầu vào là hai tệp input1.inp thể hiện việc đăng kí suất ăn của mọi người và tệp input2.inp thể hiện các suất ăn đã được chuẩn bị trước và đưa vào ngăn xếp. Hãy cho biết có người nào buộc phải đổi suất ăn của mình hay không. Nếu có thì hãy in ra số ID của những người đó. Hướng dẫn: Duyệt lần lượt từng suất ăn trong ngăn xếp. + Nếu suất ăn là gà, chúng ta kiểm tra nếu vẫn còn người trong hàng đợi suất ăn gà, chúng ta phát suất ăn cho người đầu tiên trong hàng đó (dequeue) và tiếp tục.  + Nếu đã hết người trong hàng đợi suất ăn gà, chúng ta bắt buộc người đầu tiên trong hàng suất ăn bò đổi sang suất ăn gà, đưa ID của người này vào danh sách những người buộc phải đổi món ăn và tiếp tục.  + Quy trình tương tự được thực hiện nếu suất ăn lấy ra từ ngăn xếp là suất ăn bò.  Bước 2: HS thực hiện nhiệm vụ học tập - GV hướng dẫn HS viết chương trình. - GV quan sát và trợ giúp HS khi cần. Bước 3: Báo cáo kết quả hoạt động và thảo luận - HS chạy chương trình và báo cáo kết quả cho GV. - GV kiểm tra kết quả thực hành 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ả thực hành của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

Nhiệm vụ: Viết chương trình mô phỏng bếp ăn tập thể Phân tích: Để xử lí bài toán này, việc đầu tiên là phải tiến hành đọc dữ liệu từ hai file input và đưa chúng vào những kiểu dữ liệu phù hợp: - Với dữ liệu người lao động trong hàng đợi, yêu cầu người xếp hàng trước sẽ được phục vụ món ăn trước nên chúng ta sẽ sử dụng kiểu dữ liệu hàng đợi để mô phỏng hai hàng đợi của suất ăn gà và suất ăn bò.  - Với dữ liệu các suất ăn được đưa vào ngăn xếp, các suất ăn sẽ được lấy lần lượt từ trên xuống dưới nên chúng ta sử dụng dạng dữ liệu ngăn xếp để lưu trữ loại dữ liệu này. * Chương trình thực hiện bài toán:

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

a. Mục tiêu: GV hướng dẫn HS thực hiện các yêu cầu trong phần Luyện tập để đảm bảo HS thực sự hiểu được chương trình của nhiệm vụ thực hành chứ không dừng lại ở mức sao chép và chạy chương trình.

b. Nội dung: HS thực hiện hoạt động Luyện tập SGK tr.22.

c. Sản phẩm học tập: HS hoàn thành hoạt động Luyện tập SGK tr.22.

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

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