Câu hỏi:
13/07/2024 74
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.
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.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
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.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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?
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?
Xem đáp án »
13/07/2024
143
Câu 2:
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.
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.
Xem đáp án »
13/07/2024
109
Câu 3:
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?
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?
Xem đáp án »
13/07/2024
97
Bình luận
🔥 Đề thi HOT:
-
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
-
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 1
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
về câu hỏi!