Giáo án điện tử 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

NHIỆT LIỆT CHÀO ĐÓN CÁC EM

ĐẾN VỚI BÀI HỌC MÔN TIN!

Chuyên đề Tin học 12 - Định hướng khoa học máy tính

KHỞI ĐỘNG

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?

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à:

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:

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ÀI 5: THỰC HÀNH KIỂU DỮ LIỆU NGĂN XẾP VÀ HÀNG ĐỢI

NỘI DUNG THỰC HÀNH

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

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:

gà bò gà bò gà bò bò gà

• 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à.

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:

Với dữ liệu các suất ăn được đưa vào ngăn xếp:

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ò.

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.

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à: 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 thực hiện tương tự nếu suất ăn lấy ra từ ngăn xếp là suất ăn bò.

Chương trình thực hiện bài toán:

LUYỆN TẬP

Câu 1 (SGK - tr.22): Hãy chạy chương trình với nhiều trường hợp dữ liệu đầu vào khác nhau. Em có nhận xét gì về vị trí của những người phải đổi món ăn?

• Những người phải đổi món ăn đều là những người nằm ở cuối danh sách. Điều này xuất phát từ tính chất của hàng đợi, những người ở đầu danh sách sẽ được phục vụ trước và được lấy đúng suất ăn mà mình đã chọn.
• Những người ở cuối danh sách là những người ở cuối hàng đợi và có thể sẽ phải đổi món ăn tuỳ theo số suất mà bếp ăn đã chuẩn bị.

GỢI Ý

Câu 2 (SGK - tr.22):

Hãy viết chương trình tính toán thời gian chờ đợi trung bình của mỗi người để nhận được suất ăn của mình, cho biết thời gian lấy một suất ăn ra khỏi ngăn xếp và đưa cho người lao động là 1 giây.

Thời gian chờ đợi trung bình của một người để nhận được suất ăn chính là thời gian trung bình một suất ăn được đưa đến tay người lao động, trong đó thời gian để suất ăn đầu tiên đến tay người lao động là 1 giây,…

Cần chú ý:

Chương trình được viết như sau:

VẬN DỤNG

Bài toán nhà bếp được thay đổi như sau:

Yêu cầu người lao động xếp thành một hàng để nhận đồ ăn, trong đó những người đăng kí suất cơm gà và những người đăng kí suất cơm bò sẽ đứng lẫn với nhau. Các suất ăn vẫn được nhà bếp thực hiện và đưa vào một ngăn xếp để phục vụ người lao động.

Quy tắc chọn suất ăn như sau: Mỗi người đến lượt sẽ nhận suất ăn được đưa ra từ ngăn xếp, nếu suất ăn đó đúng với suất ăn đã đăng kí thì người này sẽ được nhận suất ăn và đưa ra khỏi hàng đợi. Ngược lại nếu suất ăn không đúng với đăng kí thì người này sẽ ra khỏi hàng đợi và xếp lại vào cuối hàng và tiếp tục đợi. Quá trình chọn suất ăn như trên sẽ dừng lại nếu tất cả số người xếp hàng đều nhận được suất ăn đúng của mình hoặc tất cả mọi người trong hàng đợi đều không thể nhận được suất ăn như đã đăng kí.

Em hãy viết chương trình đọc hai tệp dữ liệu chứa thông tin về các suất ăn của người lao động và tính số người không nhận được suất ăn của mình.

Dữ liệu đầu vào gồm hai tệp, tệp input1.inp chứa thông tin về các suất ăn của người lao động trong hàng đợi, tệp input2.inp chứa thông tin về các suất ăn mà nhà ăn đã chuẩn bị và đưa vào trong ngăn xếp. Ví dụ dữ liệu đầu vào và đầu ra như sau:

Dữ liệu đầu ra là một số nguyên cho trước chỉ số lượng người xếp hàng không thể chọn được suất ăn của mình. Trong ví dụ trên kết quả đưa ra là 2.

GỢI Ý

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