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

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:

• Khởi động trang 20 Chuyên đề Tin học 12: Trong bài trước, chúng ta đã sử dụng kiểu dữ liệu hàng đợi và ngăn xếp ....

• Luyện tập 1 trang 22 Chuyên đề Tin học 12: 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 ....

• Luyện tập 2 trang 22 Chuyên đề Tin học 12: 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 ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 6: Cây nhị phân

• Chuyên đề Tin học 12 Bài 7: Cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 8: Thực hành cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---