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
Bài toán nhà bếp được thay đổi như sau:
Giải Chuyên đề Tin 12 Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi - Kết nối tri thức
Vận dụng trang 22 Chuyên đề Tin học 12: 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.
Lời giải:
Với bài toán nhà bếp với quy tắc chọn suất ăn mới, cần viết chương trình để thực hiện theo quy tắc mới: 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 mà họ đã đăng ký, người đó sẽ được nhận suất ăn và đưa ra khỏi hàng đợi. Nếu không, người đó sẽ quay lại cuối hàng đợi. Quá trình này tiếp tục cho đến khi tất cả mọi người đều nhận được suất ăn đúng hoặc tất cả mọi người không thể nhận được suất ăn của mình.
Gợi ý các bước giải quyết bài toán:
1. Đọc dữ liệu từ tệp input1.inp để lấy danh sách đăng ký suất ăn của người lao động.
2. Đọc dữ liệu từ tệp input2.inp để lấy danh sách các suất ăn đã chuẩn bị.
3. Sử dụng hàng đợi để mô phỏng quá trình xếp hàng nhận suất ăn.
4. Sử dụng ngăn xếp để lấy các suất ăn đã chuẩn bị.
5. Thực hiện quá trình phục vụ suất ăn theo quy tắc mới.
6. Đưa ra số lượng người không nhận được suất ăn đúng của mình.
Mẫu mã nguồn gợi ý:
from collections import deque
def read_file(filename):
with open(filename, 'r', encoding='utf8') as file:
return file.read().strip().split()
def serve_food(people_queue, food_stack):
initial_queue_length = len(people_queue)
no_change_count = 0
served_count = 0
while food_stack and no_change_count < len(people_queue):
person = people_queue.popleft()
food = food_stack.pop()
if person == food:
served_count += 1
no_change_count = 0 # reset no change count as someone got their food
else:
people_queue.append(person)
food_stack.append(food) # put the food back on the stack
no_change_count += 1
return len(people_queue) - served_count
# Đọc dữ liệu từ file
people = read_file("input1.inp")
foods = read_file("input2.inp")
# Tạo hàng đợi cho người và ngăn xếp cho suất ăn
people_queue = deque(people)
food_stack = list(reversed(foods))
# Tính số lượng người không nhận được suất ăn của mình
unserved_people_count = serve_food(people_queue, food_stack)
print(unserved_people_count)
Chú thích mã nguồn
1. Đọc dữ liệu:
- read_file(filename): Hàm này đọc nội dung từ tệp và trả về danh sách các từ đã tách.
- Tệp input1.inp chứa thông tin đăng ký suất ăn của người lao động.
- Tệp input2.inp chứa thông tin các suất ăn đã chuẩn bị.
2. Khởi tạo hàng đợi và ngăn xếp:
- people_queue là một hàng đợi (deque) chứa danh sách người.
- food_stack là một ngăn xếp chứa các suất ăn (được đảo ngược để mô phỏng ngăn xếp).
3. Phục vụ suất ăn:
- serve_food(people_queue, food_stack): Hàm này thực hiện quy trình phục vụ suất ăn.
- Sử dụng biến no_change_count để theo dõi số lần liên tiếp mà không có ai nhận được suất ăn.
- Mỗi vòng lặp, lấy một người và một suất ăn ra.
- Nếu suất ăn đúng với đăng ký của người đó, tăng served_count và reset no_change_count.
- Nếu không, người đó quay lại cuối hàng đợi và suất ăn quay lại ngăn xếp, tăng no_change_count.
- Khi no_change_count bằng độ dài hàng đợi, nghĩa là không ai có thể nhận được suất ăn của mình nữa.
Lời giải bài tập Chuyên đề Tin 12 Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi hay, ngắn gọn khác: