Giáo án điện tử chuyên đề Khoa học máy tính 12 chân trời Bài 1.3: Ứng dụng của hàng đợi

BÀI 1.3: ỨNG DỤNG CỦA HÀNG ĐỢI

Chào mừng quý thầy cô cùng các em học sinh đến với tiết học ngày hôm nay!

A. KHỞI ĐỘNG

Hoạt động theo nhóm:Em hãy liệt kê một số hoạt động hàng ngày cần dùng đến hàng đợi.

Gợi ý trả lời:

Một số hoạt động hàng ngày cần dùng đến hàng đợi:

+Xếp hàng mua vé: Khi xếp hàng để mua vé xem phim, vé máy bay, hoặc vé tàu, người đến trước sẽ được phục vụ trước. 

+ Chờ đợi tại bệnh viện: Tại bệnh viện hoặc phòng khám, bệnh nhân thường được ghi tên vào danh sách chờ. Bệnh nhân đến trước sẽ được khám trước.

+ Gọi điện tổng đài: Khi gọi đến tổng đài hỗ trợ khách hàng, các cuộc gọi sẽ được xếp vào hàng đợi và được xử lý theo thứ tự chúng được nhận.

+ Xếp hàng thanh toán tại siêu thị: Khi mua sắm tại siêu thị, người xếp hàng trước sẽ được thanh toán trước.

+ Xếp hàng lên xe buýt: Tại các bến xe buýt, hành khách xếp hàng để chờ lên xe. Hành khách đến trước sẽ được lên xe trước.

+ Xếp hàng tại nhà hàng: Tại một số nhà hàng, khách hàng cần xếp hàng để chờ có bàn trống. Khách hàng đến trước sẽ được phục vụ trước.

…

B. HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Một số ứng dụng của hàng đợi

+ Cơ chế hoạt động của hàng đợi là gì?

+ Hàng đợi có thể được ứng dụng vào những lĩnh vực nào? Trong mỗi lĩnh vực đó, hàng đợi được sử dụng để làm gì?

+ Em hãy nêu một số ứng dụng phổ biến của hàng đợi trong lĩnh vực Công nghệ thông tin.

Dự kiến sản phẩm:

1. Một số ứng dụng của hàng đợi

- Hàng đợi hoạt động theo cơ chế FIFO (First In, First Out) – vào trước ra trước.

- Hàng đợi được ứng dụng để giải quyết một số vấn đề trong các lĩnh vực Công nghệ thông tin, dịch vụ, kinh doanh,... 

Ví dụ: 

+ Trong lĩnh vực Công nghệ thông tin, hàng đợi được sử dụng để giải quyết các vấn đề như phân bố tài nguyên của hệ điều hành, thứ tự gửi email, in tài liệu. 

+ Trong kinh doanh, hàng đợi được sử dụng để sắp xếp thứ tự xử lí đơn hàng, chăm sóc khách hàng. 

…

- Một số ứng dụng phổ biến của hàng đợi trong lĩnh vực Công nghệ thông tin:

+ Sắp xếp lịch trình: 

• Sử dụng hàng đợi để quản lí các nhiệm vụ cần thực hiện. 

• Một trong những cách tiếp cận đơn giản là "đến trước, phục vụ trước" (FCFS – First Come, First Served). Nghĩa là các nhiệm vụ theo thứ tự yêu cầu được thêm vào cuối hàng đợi với thao tác enqueue và lấy ra khỏi hàng đợi để thực hiện với thao tác dequeue.

Hoạt động 2. Thực hành

Trò chơi Hot Potato: Các người chơi đứng thành vòng tròn và lần lượt chuyển củ khoai cho người bên cạnh theo chiều kim đồng hồ trên nền nhạc. Khi nhạc dừng, lượt chơi dừng tạm thời, người nào đang giữ củ khoai sẽ bị loại và giao lại cho người bên cạnh theo chiều kim đồng hồ. Để đơn giản hoá quy định, người chơi có thể quy ước sau m lần chuyển củ khoai thì lượt chơi ngừng tạm thời. Trò chơi tiếp tục cho đến khi chỉ còn lại một người, gọi là người chiến thắng.

Dự kiến sản phẩm:

2. THỰC HÀNH 

Nhiệm vụ. Trò chơi Hot Potato

- Input: Danh sách 5 người chơi: ['An', 'Trung', 'Quang', 'Nga', 'Han'] và m = 2.

- Output: Tên của người chiến thắng là "Nga".

* Mã nguồn tham khảo:

C. LUYỆN TẬP

Hoàn thành phiếu bài tập sau:

Khoanh tròn vào chữ cái đứng trước câu trả lời đúng nhất:

Câu 1. Nếu hàng đợi không rỗng thì phép toán front sẽ trả về giá trị nào?

A. True.

B. False.

C. queue[0].

D. len(queue).

Câu 2. Trong trường hợp hàng đợi không rỗng, để lấy phần tử ra khỏi đầu hàng đợi, ta sử dụng hàm nào của kiểu list?

A. queue.pop().      

B. pop.dequeue().            

C. dequeue.pop(0).          

D. queue.pop(0).

Câu 3. Nếu hàng đợi không rỗng thì phép toán rear sẽ trả về giá trị nào? 

A. queue[len(queue) – 1].       

B. queue[len(queue)].

C. queue[0].                 

D. queue[len(queue) + 1].

Câu 4. Phương án nào sau đây không phải là một ứng dụng của hàng đợi trong lĩnh vực Công nghệ thông tin?

A. Quản lí thứ tự xử lí lệnh in.

B. Sắp xếp thứ tự xử lí đơn hàng.

C. Phân bố tài nguyên của hệ điều hành.

D. Quản lí thứ tự gửi email.

Câu 5. Các tài liệu cần in được thêm vào hàng đợi máy in bằng thao tác nào?

A. append.

B. dequeue.

C. enqueue.

D. push.

………………………..

Gợi ý trả lời:

D. VẬN DỤNG

Nhiệm vụ. Kiểm tra số Palindrome

Số nguyên không âm Palindrome là số đọc xuôi hay đọc ngược vẫn chỉ cho ra một số. Chẳng hạn, các số sau đây là số Palindrome 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101,...

Yêu cầu: Sử dụng hàng đợi và ngăn xếp để viết chương trình kiểm tra một số nguyên là Palindrome.

Dữ liệu vào: số nguyên a.

Dữ liệu ra: thông báo "a là số Palindrome" nếu a là số Palindrome, ngược lại thông báo "a không là số Palindrome".

HƯỚNG DẪN VỀ NHÀ

- Xem lại kiến thức đã học ở Bài 1.3.

- Xem trước nội dung Bài 1.4: Ứng dụng của ngăn xếp.