Giải chuyên đề Tin 12 KNTT Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi có đáp án

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à trong việc 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.

Ví dụ: Kiểm tra tính đúng đắn của dấu ngoặc trong biểu thức

Giả sử có một biểu thức toán học và bạn muốn kiểm tra xem tất cả các dấu ngoặc mở đều có dấu ngoặc đóng tương ứng và được đặt đúng thứ tự. Để làm điều này, bạn có thể sử dụng ngăn xếp và hàng đợi như sau:

1. Ngăn xếp (Stack): Dùng để theo dõi các dấu ngoặc mở.

2. 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 bạn cần lưu trữ và xử lý lại sau khi kiểm tra dấu ngoặc.

Cách thực hiện như sau:

1. Duyệt qua từng ký tự trong biểu thức:

- Nếu gặp dấu ngoặc mở ((, [, {), đưa vào ngăn xếp.

- Nếu gặp dấu ngoặc đóng (), ], }), kiểm tra ngăn xếp để đảm bảo dấu ngoặc đóng tương ứng với dấu ngoặc mở tương ứng. Nếu đúng, loại bỏ dấu ngoặc mở khỏi ngăn xếp.

2. Sau khi duyệt qua tất cả các ký tự:

- Nếu ngăn xếp trống, biểu thức có dấu ngoặc đúng.

- Nếu ngăn xếp không trống, biểu thức có dấu ngoặc không đúng.

Đầu tiên, viết chương trình để đọc dữ liệu từ hai tệp input1.inp và input2.inp, sau đó mô phỏng quá trình phục vụ suất ăn. Dưới đây là gợi ý chương trình hoàn chỉnh mẫu:

from queue import Queue

from collections import deque

# Định nghĩa lớp Stack sử dụng deque cho ngăn xếp

class Stack:

    def __init__(self):

        self.items = deque()

    def is_empty(self):

        return len(self.items) == 0

    def push(self, item):

        self.items.append(item)

    def pop(self):

        if not self.is_empty():

            return self.items.pop()

        return None

    def size(self):

        return len(self.items)

def bepan(dangkiga, dangkibo, suatan):

    doimon = [] # list chứa ID những người phải đổi món

    while not suatan.is_empty():

        tmp = suatan.pop()

        if tmp == "bò":  # nếu suất ăn lấy ra là bò

            if not dangkibo.empty():  # còn người đăng kí suất ăn bò

                dangkibo.get()

            else:

                ID_doi = dangkiga.get()

                doimon.append(ID_doi)

        elif tmp == "gà":  # nếu suất ăn lấy ra là gà

            if not dangkiga.empty():  # còn người đăng kí suất ăn gà

                dangkiga.get()

            else:

                ID_doi = dangkibo.get()

                doimon.append(ID_doi)

    return doimon

# Khởi tạo hàng đợi cho cơm gà và cơm bò

dangkiga = Queue()

dangkibo = Queue()

# Khởi tạo ngăn xếp cho các suất ăn

suatan = Stack()

# Đọc thông tin đăng kí và đưa vào 2 queue

with open("input1.inp", "r", encoding="utf8") as file1:

    for line in file1.readlines():

        id, dangki = line.strip().split()

        if dangki == "gà":

            dangkiga.put(id)

        elif dangki == "bò":

            dangkibo.put(id)

# Đọc thông tin suất ăn và đưa vào ngăn xếp

with open("input2.inp", "r", encoding="utf8") as file2:

    data = file2.read().strip().split()

    for item in data:

        suatan.push(item)

doimon = bepan(dangkiga, dangkibo, suatan)

if len(doimon) == 0:

    print("Không có người nào phải đổi món ăn")

else:

    print("Danh sách những người phải đổi món là:", doimon)

- Nhận xét về vị trí của những người phải đổi món ăn

Sau khi chạy chương trình với nhiều trường hợp dữ liệu đầu vào khác nhau, nhận xét 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 luôn nằm trong hàng đợi ban đầu của loại suất ăn còn lại khi loại suất ăn họ đăng ký đã được phục vụ hết.

- Vị trí của những người phải đổi món ăn phụ thuộc vào thứ tự của họ trong hàng đợi. Người đầu tiên trong hàng đợi sẽ phải đổi món trước khi đến lượt họ nếu hàng đợi của suất ăn còn lại đã hết.

Để tính toán thời gian chờ đợi trung bình cần theo dõi thời gian chờ của mỗi người. Dưới đây là chương trình mở rộng để tính toán thời gian chờ đợi trung bình.

def bepan_with_wait_time(dangkiga, dangkibo, suatan):

    doimon = [] # list chứa ID những người phải đổi món

    wait_times = {}

    current_time = 0

    while not suatan.is_empty():

        current_time += 1  # Mỗi lượt lấy suất ăn là 1 giây

        tmp = suatan.pop()

        if tmp == "bò":  # nếu suất ăn lấy ra là bò

            if not dangkibo.empty():  # còn người đăng kí suất ăn bò

                id = dangkibo.get()

                wait_times[id] = current_time

            else:

                id = dangkiga.get()

                doimon.append(id)

                wait_times[id] = current_time

        elif tmp == "gà":  # nếu suất ăn lấy ra là gà

            if not dangkiga.empty():  # còn người đăng kí suất ăn gà

                id = dangkiga.get()

                wait_times[id] = current_time

            else:

                id = dangkibo.get()

                doimon.append(id)

                wait_times[id] = current_time

    return doimon, wait_times

# Đọc thông tin đăng kí và đưa vào 2 queue

dangkiga = Queue()

dangkibo = Queue()

with open("input1.inp", "r", encoding="utf8") as file1:

    for line in file1.readlines():

        id, dangki = line.strip().split()

        if dangki == "gà":

            dangkiga.put(id)

        elif dangki == "bò":

            dangkibo.put(id)

# Đọc thông tin suất ăn và đưa vào ngăn xếp

suatan = Stack()

with open("input2.inp", "r", encoding="utf8") as file2:

    data = file2.read().strip().split()

    for item in data:

        suatan.push(item)

doimon, wait_times = bepan_with_wait_time(dangkiga, dangkibo, suatan)

if len(doimon) == 0:

    print("Không có người nào phải đổi món ăn")

else:

    print("Danh sách những người phải đổi món là:", doimon)

# Tính toán thời gian chờ đợi trung bình

if wait_times:

    total_wait_time = sum(wait_times.values())

    average_wait_time = total_wait_time / len(wait_times)

    print(f"Thời gian chờ đợi trung bình là: {average_wait_time:.2f} giây")

else:

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.