Chuyên đề Tin học 12 Bài 1.3 (Chân trời sáng tạo): Ứng dụng của hàng đợi

Giải Chuyên đề Tin học 12 Bài 1.3: Ứng dụng của hàng đợi

Khởi động trang 14 Chuyên đề Tin học 12: Em hãy liệt kê một số hoạt động hàng ngày cần dùng đến hàng đợi.

Lời giải:

Liệt kê một số hoạt động hàng ngày cần dùng đến hàng đợi: phân bố tài nguyên của hệ điều hành, thứ tự gửi email, in tài liệu, xếp hàng mua vé, lấy số khám bệnh ở bệnh viện, xếp hàng thanh toán ở siêu thị,…

1. Một số ứng dụng của hàng đợi

Câu hỏi 1 trang 15 Chuyên đề Tin học 12: Theo em, hàng đợi có những ứng dụng nào?

Lời giải:

Hàng đợi có những ứng dụng sau: phân bố tài nguyên của hệ điều hành, thứ tự gửi email, in tài liệu, xếp hàng mua vé, lấy số khám bệnh ở bệnh viện, xếp hàng thanh toán ở siêu thị,…

Câu hỏi 2 trang 15 Chuyên đề Tin học 12: Hàng đợi máy in được sử dụng như thế nào?

Lời giải:

Hàng đợi máy in được sử dụng như sau: Được sử dụng để quản lí thứ tự khi xử lý lệnh in. Khi nhiều tài liệu cần được in, thì các tài liệu được thêm vào vùng đệm máy in. Các tài liệu cần được in thêm vào hàng đợi của máy in với thao tác enqueue, sau đó máy in sẽ tuần tự lấy tài liệu cần in với thao tác là dequeue để thực hiện in.

Luyện tập 1 trang 15 Chuyên đề Tin học 12: Hãy cho biết máy chủ email thường xử lí các yêu cầu từ nhiều người dùng theo thứ tự như thế nào.

Lời giải:

Máy chủ email thường xử lí các yêu cầu từ nhiều người dùng theo thứ tự như sau: Sử dụng hàng đợi để quản lí các yêu cầu đến từ máy khách, nhằm đảm bảo xử lý các yêu cầu theo thứ tự thích hợp (yêu cầu nào đến trước thì phục vụ trước). Các yêu cầu được enqueue vào hàng đợi và được dequeue để xử lý theo cơ chế FIFO.

Luyện tập 2 trang 15 Chuyên đề Tin học 12: Trình bày ứng dụng của hàng đợi trong thuật toán First-Come, First-Served thường được dùng trong sắp xếp các tiến trình chờ xử lí của CPU.

Lời giải:

Trình bày ứng dụng của hàng đợi trong thuật toán First-Come, First-Served thường được dùng trong sắp xếp các tiến trình chờ xử lí của CPU:

Sử dụng hàng đợi để quản lí các nhiệm vụ cần thực hiện. Một trong những cách tiếp cận đơn giản được gọi là “đến trước, phục vụ trước” (First-Come, First-Served). Nghĩa là các nhiệm vụ được thêm vào cuối hàng đợi với thao tác enqueue theo thứ tự yêu cầu. Sau đó, các nhiệm vụ lấy ra khỏi hàng đợi với thao tác dequeue để thực hiện.

Nhiệm vụ trang 16 Chuyên đề Tin học 12: Nhiệm vụ. Trò chơi Hot Potato

Các người chơi đứng thành vòng tròn và lần lượt chuyển củ khoai cho người bên cạnh theo chiều kim đồng hồ trên nền nhạc. Khi nhạc dừng, lượt chơi dừng tạm thời, người nào đang giữ củ khoai sẽ bị loại và giao lại cho người bên cạnh theo chiều kim đồng hồ. Để đơn giản hóa quy định, người chơi có thể quy ước sau m lần chuyển củ khoai thì lượt chơi ngừng tạm thời. Trò chơi tiếp tục cho đến khi chỉ còn lại một người, gọi là người chiến thắng. Hình 4 minh họa trò chơi Hot Potato với 5 người chơi, bắt đầu từ An.

Yêu cầu: Hãy viết chương trình in ra màn mình tên người chiến thắng với danh sách n (n ≥ 1) người chơi và số nguyên dương m (m > 0) được nhập từ bàn phím. Chạy chương trình với số người chơi n = 5.

Dữ liệu vào: danh sách tên các người chơi và số nguyên dương m (m > 0).

Dữ liệu ra: tên của người chiến thắng.

Lời giải:

Hãy viết chương trình in ra màn mình tên người chiến thắng với danh sách n (n ≥ 1) người chơi và số nguyên dương m (m > 0) được nhập từ bàn phím. Chạy chương trình với số người chơi n = 5.

Dữ liệu vào: danh sách tên các người chơi và số nguyên dương m (m > 0).

Dữ liệu ra: tên của người chiến thắng.

* Mã giả trò chơi Hot Potato:

hotPotato (players, m):

Nếu m <= 9 :

raise ValueError('Số lần chuyển phải lớn hơn zero') if len(players) == 0:

raise ValueError('Không có người chơi') Tạo queue rỗng

son trở thêm danh sách các người chơi vào queue

for p in players: Thêm p vào queue player = "

while queue khác rỗng:

for i in range(m)

Lấy ra player từ queue Thêm player vào queue Lấy ra player từ queue return player

#Tên người thắng #Còn người chơi

#Chuyển củ khoai m lần

#Loại người cầm củ khoai

* Code như sau:

def hotPotato (players, m):

if m <= 0 :

raise ValueError('Số lần chuyển phải lớn hơn zero')

if len(players) == 0:

raise ValueError("Không có người chơi')

queue initQueue()

for p in players:enqueue(queue, p)

player = "

#Tạo hàng đợi rỗng

#Thêm danh sách các người chơi vào queue

while not isEmptyQueue(queue):#Còn người chơi

for i in range(m): player dequeue(queue) enqueue(queue, player) player = dequeue(queue) return player

#Chuyển củ khoai m lần

#Loại người cầm củ khoai #Trả về tên người thắng

players = list(map(str, input('Nhập danh sách người chơi:').split()))

m = int(input('Nhập số lần chuyển: '))

if len(players) == 0:

print("Không có người chơi")

elif m <= 0:

print("Số lần chuyển > 9")

else:

winner hotPotato (players, m)

print("Danh sách người chơi:", players) print("Số lần chuyển:", m)

print("Người chiến thắng:", winner)

Vận dụng trang 17 Chuyên đề Tin học 12: Nhiệm vụ. Kiếm tra số Palindrome

Số nguyên không âm Palindrome là số đọc xuôi hay đọc ngược vẫn chỉ cho ra một số. Chẳng hạn, các số sau đây là số Palindrome 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 41, 55, 66, 77, 88, 99, 101,...

Yêu cầu: Sử dụng hàng đợi và ngăn xếp để viết chương trình kiểm tra một số nguyên là Palindrome.

Dữ liệu vào: số nguyên a.

Dữ liệu ra: thông báo "a là số Palindrome" nếu a là số Palindrome, ngược lại thông báo "a không là số Palindrome".

Lời giải:

*Mã giả kiểm tra số Palindrome:

isPalindrome (a)

Nếu a ( @

raise ValueError('Giá trị tham số nhỏ hơn zero') Khởi tạo hàng đợi queue rỗng

Khởi tạo ngăn xếp stack rỗng while a khác 9 :

r = số dư a chia 10 Thêm r vào queue Thêm r vào stack

a = a chia nguyên 19 while queue khác rỗng Lấy ra digitl từ queue Lấy ra digit2 từ stack if digit1 khác digit2: return False

return True

#Lấy từng giá trị của a đưa vào queue và stack

Xem thêm các bài giải Chuyên đề Tin học 12 sách Chân trời sáng tạo hay, chi tiết khác:

Bài 1.2: Ngăn xếp

Bài 1.4: Ứng dụng của ngăn xếp

Bài 2.1: Cây và cây nhị phân

Bài 2.2: Các phép toán duyệt cây nhị phân

Bài 2.3: Cây tìm kiếm nhị phân