Giáo án chuyên đề Khoa học máy tính 12 chân trời Bài 1.1: Hàng đợi

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV cho HS thảo luận theo bàn, đọc và tìm hiểu thông tin trong mục 1 SGK tr.5,6 để trả lời các câu hỏi:

+ Hàng đợi là gì? Cơ chế hoạt động của hàng đợi là gì?

+ Trình bày các thao tác cơ bản “Thêm vào” và “Lấy ra” trên hàng đợi.

- GV triển khai hoạt độngLàm SGK tr.7 và tổ chức cho HS thực hiện theo nhóm đôi:

1.  Cho Hình 4 biểu diễn một hàng đợi,  hãy cho biết:

a) Phần tử đầu hàng đợi, phần tử cuối hàng đợi.

b)  Sau khi lấy ra một phần tử, thì phần tử đầu hàng đợi là phần tử nào?

c) Sau khi thêm vào phần tử “k” vào thì phần tử cuối hàng đợi là phần tử nào?  

Hình 4. Hàng đợi và hai đầu front, rear

2.  Cho một hàng đợi rỗng, hãy vẽ hình minh họa từng bước thực hiện các thao tác sau: enqueue(1), enqueue(3), enqueue(5), dequeue(), dequeue(), enqueue(7).

+ Sau thời gian thảo luận, GV chỉ định lần lượt các HS thực hiện yêu cầu của câu hỏi.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung phần a, mục 1 SGK tr.5 sau đó trao đổi, thảo luận trả lời các câu hỏi mà GV đưa ra.

- GV quan sát, hướng dẫn, hỗ trợ HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện các nhóm báo cáo kết quả thảo luận.

- GV mời HS khác nhận xét, bổ sung. 

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.7:

1. a) Phần tử đầu hàng đợi: m;

Phần tử cuối hàng đợi: x.

b) Sau khi lấy ra một phần tử thì phần tử đầu hàng đợi là: +.

c) Sau khi thêm vào phần tử “k” vào thì phần tử cuối hàng đợi là phần tử: k.

2. 

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ kết quả thảo luận của nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức.

- GV chốt kiến thức theo hoạt động Ghi nhớ:

• Hàng đợi là một cấu trúc dữ liệu tuyến tính dùng để lưu danh sách các phần tử.

• Hai thao tác cơ bản trên hàng đợi là thao tác thêm vào (enqueue) ở cuối hàng đợi (rear) và thao tác lấy ra (dequeue) ở đầu hàng đợi (front). Hai thao tác này thể hiện cơ chế hoạt động “Vào trước - Ra trước” (FIFO – First In, First Out).

1. Hàng đợi

- Khái niệm: Hàng đợi là một cấu trúc dữ liệu tuyến tính dùng để lưu danh sách các phần tử.  

- Cơ chế hoạt động: căn cứ theo thứ tự các phần tử được thêm vào hàng đợi, gọi là vào trước ra trước (FIFO – First In, First Out).

Hình 2. Cơ chế FIFO của hàng đợi

- Các thao tác cơ bản:

+ enqueue: Thêm vào phần tử mới ở cuối hàng đợi.

+ dequeue: Lấy ra  một phẩn tử ở đầu hàng đợi.

+ front: Trả về giá trị của phần tử đầu hàng đợi.

+ rear (hay back): Trả về giá trị của phần tử cuối hàng đợi.

+ Kiểm tra hàng đợi rỗng.

Hình 3. Thao tác enqueue, dequeue, trên hàng đợi và hai đầu front, rear.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

a) Biểu diễn hàng đợi bằng mảng một chiều.

- GV trình chiếu Hình 5 và cho HS đọc và nghiên cứu mục 2, phần a SGK-tr.7 để trả lời câu hỏi sau:

+ Dựa vào Hình 5, cho biết chỉ số của phần tử đầu hàng đợi và chỉ số của phần tử cuối hàng đợi trong mảng là bao nhiêu?

- GV cho HS thảo luận nhóm đôi, trả lời câu hỏi hoạt động Làm SGK tr.7:

1. Các thông tin cần thiết để biểu diễn hàng đợi bằng mảng một chiều là gì?

2. Với hàng đợi ở hình 5, hay vẽ hình thực hiện liên tục các thao tác: Thêm vào 0, lấy ra, lấy ra.

b) Cài đặt hàng đợi bằng mảng một chiều trong Python

- HS thảo luận theo nhóm 4 HS tìm hiểu thông tin trong mục 2, phần b SGK tr.8 để thực hiện các câu hỏi sau:

+ Các phép toán cơ bản cho hàng đợi được cài đặt thông qua những hàm nào? Cho biết ý nghĩa của những hàm đó.

- GV cho HS làm việc cá nhân, trả lời câu hỏi hoạt động Làm SGK tr.8:

1. Tại sao không cần sử dụng các chỉ số front, rear khi dùng kiểu list để biểu diễn hàng đợi trong Python?

2. Theo em, có cách nào kiểm tra hàng đợi queue là rỗng mà không dùng hàm len(queue)?

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung mục 2 SGK tr.7 – 8 sau đó trao đổi, thảo luận trả lời các câu hỏi mà GV đưa ra.

- GV quan sát, hướng dẫn, hỗ trợ HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện các nhóm báo cáo kết quả thảo luận.

- GV mời HS khác nhận xét, bổ sung.

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.7:

1.

+ Mảng: Một mảng một chiều để lưu trữ các phần tử của hàng đợi.

+ Chỉ số đầu và chỉ số cuối của hàng đợi: Chỉ số đầu dùng để trỏ đến phần tử đầu tiên của hàng đợi, chỉ số cuối dùng để trỏ đến phần tử cuối cùng của hàng đợi.

+ Số lượng phần tử hiện có trong hàng đợi: Điều này cho phép chúng ta biết hàng đợi hiện tại đang chứa bao nhiêu phần tử và khi nào nó đầy.

2. 

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.8:

………………..

2. Biểu diễn và cài đặt hàng đợi bằng mảng một chiều

a) Biểu diễn hàng đợi bằng mảng một chiều.

- Phần tử đầu của hàng đợi được đặt vào phần tử có chỉ số front = 0.

- Phần tử cuối hàng đợi được đặt vào phần tử có chỉ số rear = 6.

b) Cài đặt hàng đợi bằng mảng một chiều trong Python

- Các phép toán cơ bản cho hàng đợi được cài đặt thông qua các hàm sau:

+ Khởi tạo hàng đợi rỗng:

+ Kiểm tra hàng đợi rỗng:

+ Phép toán enqueue: Sử dụng hàm append() để thêm phần tử vào cuối hàng đợi.

+ Phép toán dequeue: thao tác dequeue bắt đầu bằng việc kiểm tra hàng đợi có rỗng hay không. Nếu không, sử dụng hàm pop() với chỉ số 0 để xóa phần tử đầu hàng đợi đi.

+ Phép toán front: kiểm tra nếu hàng đợi không rỗng thì trả về giá trị của queue[0].

Phép toán rear: kiểm tra nếu hàng đợi không rỗng thì trả về giá trị của queue[len(queue)-1].