Giáo án chuyên đề KHMT 12 kết nối: Bài 4 Kiểu dữ liệu hàng đợi

Trọn bộ giáo án chuyên đề tin học khoa học máy tính 12 sách kết nối tri thức cả năm file word. Giáo án bài 4 Kiểu dữ liệu hàng đợi. Bài soạn bám sát theo chương trình mới được trình bày khoa học, kiến thức trọng tâm, dễ dàng giảng dạy và chỉnh sửa đơn giản khi cần.

Nội dung chi tiết

Ngày soạn:…/…/…

Ngày dạy:…/…/…

BÀI 4: KIỂU DỮ LIỆU HÀNG ĐỢI

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

Sau bài học này, HS sẽ:

Biểu diễn được hàng đợi bằng mảng một chiều.
Giải thích và viết được các chương trình con sử dụng các hàm cơ bản của kiểu dữ liệu hàng đợi.

2. Năng lực

Năng lực chung:

Năng lực giao tiếp và hợp tác: Biết lựa chọn hình thức làm việc nhóm với quy mô phù hợp với yêu cầu và thực hiện tốt nhiệm vụ.
Năng lực tự chủ và tự học: Chủ động học tập, tìm hiểu nội dung bài học, biết lắng nghe và trả lời nội dung trong bài học.
Giải quyết vấn đề và sáng tạo: Trả lời được các câu hỏi, giải quyết được các vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

Năng lực Tin học:

Biểu diễn được kiểu dữ liệu hàng đợi bằng list trong Python.
Giải thích và viết được các chương trình con có sử dụng các hàm cơ bản của kiểu dữ liệu hàng đợi.

3. Phẩm chất

Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.
Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.
Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua sản phẩm.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU:

1. Đối với giáo viên:

Tài liệu, máy tính, máy trình chiếu.
SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

2. Đối với học sinh:

Vở ghi, máy tính.
SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

III. TIẾN TRÌNH DẠY HỌC

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu: Tạo hứng thú học tập cho HS.

b. Nội dung: HS thảo luận nhóm và trả lời các câu hỏi phần Khởi động SGK tr.16.

c. Sản phẩm học tập: Từ yêu cầu, HS vận dụng sự hiểu biết để trả lời các câu hỏi phần Khởi động SGK tr.16.

d. Tổ chức thực hiện:

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

- GV chia lớp thành ba nhóm học tập và nêu câu hỏi Khởi động SGK tr.16 cho các nhóm thảo luận:

Từ các bài học trước, em đã biết viết chương trình đơn giản để sử dụng các hàm cơ bản của ngăn xếp được cài đặt bằng danh sách (kiểu list của Python). Em hãy trả lời các câu hỏi sau:

a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp được không?

b) Khi cài đặt hàng đợi bằng mảng một chiều, cần có thông tin nào để thực hiện phép toán thêm vào và lấy ra?

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

- HS thảo luận theo nhóm và thực hiện nhiệm vụ.

- GV 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 lần lượt mời các nhóm báo cáo kết quả thảo luận.

Gợi ý trả lời:

a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp.

b) Để thực hiện phép toán thêm vào và lấy ra khi cài đặt hàng đợi bằng mảng một chiều, cần có những thông tin sau:

+ front, head (đầu hàng đợi): Chỉ số này giữ vị trí của phần tử đầu tiên trong hàng đợi. Khi thực hiện phép toán lấy ra (dequeue), phần tử tại vị trí này sẽ được lấy ra và chỉ số front sẽ được cập nhật để trỏ đến phần tử tiếp theo.

+ back, rear, tail (cuối hàng đợi): Chỉ số này giữ vị trí của phần tử cuối cùng trong hàng đợi. Khi thực hiện phép toán thêm vào (enqueue), phần tử mới sẽ được thêm vào vị trí kế tiếp của chỉ số rear, và chỉ số rear sẽ được cập nhật để trỏ đến vị trí cuối mới của hàng đợi.

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

GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Tương tự như ngăn xếp, hàng đợi cũng có thể được biểu diễn bằng mảng một chiều. Vậy nếu dùng kiểu dữ liệu list của Python để mô tả hàng đợi thì các thao tác chính như enqueue() và dequeue() sẽ được thiết lập như thế nào? Để trả lời câu hỏi này, chúng ta sẽ cùng nhau tìm hiểu Bài 4: Kiểu dữ liệu hàng đợi.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Dùng kiểu dữ liệu mảng để biểu diễn hàng đợi

a. Mục tiêu: HS biết và nắm được cách sử dụng kiểu dữ liệu list trong Python để mô tả hàng đợi thông qua sơ đồ hoặc mô tả bằng lời, chưa cần lập trình.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1. Biểu diễn hàng đợi bằng mảng một chiều, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: HS biểu diễn được hàng đợi bằng mảng một chiều.

d. Tổ chức thực hiện:

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 yêu cầu HS thảo luận theo nhóm 2 – 3 HS và trả lời các câu hỏi:

+ Theo em, hàng đợi được cài đặt bằng một danh sách (kiểu list của Python) có những trường hợp nào?

- GV tổng hợp cách dùng kiểu dữ liệu danh sách (list) của Python để biểu diễn hàng đợi.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi Củng cố tr.17 SGK:

Câu 1. Khi hàng đợi được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết cách tính số phần tử của hàng đợi này.

Câu 2. Ban đầu, hàng đợi là rỗng. Em hãy cho biết giá trị của phần tử ở đầu (front) và đuôi (rear) sau khi thực hiện tuần tự các phép toán enqueue(Q,2); enqueue(Q,10); dequeue(Q); enqueue (Q,6); dequeue(Q); enqueue(Q,9); enqueue(Q,1).

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 1 SGK tr.16 – 17 và thảo luận trả lời các câu hỏi mà GV đưa ra.

- GV quan sát và trợ giúp 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

- Đại diện các nhóm HS trả lời.

- Các nhóm khác đưa ra ý kiến nhận xét.

Hướng dẫn trả lời câu hỏi Củng cố SGK tr.17:

Câu 1. Số phần tử của hàng đợi Q chính là giá trị len(Q).

Câu 2. Phần tử đầu của hàng đợi Q là 6, phần tử đuôi là 1.

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:

Hàng đợi được cài đặt bằng mảng một chiều (danh sách thuộc kiểu list của Python).
Phép toán enqueue(Q,x) thêm x vào cuối mảng.
Phép toán dequeue(Q) lấy ra phần tử cuối của mảng.
Đầu (front) là phần tử đầu tiên và đuôi (rear) là phần tử cuối của mảng.

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

Hàng đợi được cài đặt bằng một danh sách (kiểu list của Python) có các trường hợp sau:

a) Khởi tạo hàng đợi Q là rỗng; nghĩa là Q là danh sách rỗng.

Hình 4.1a. Hàng đợi rỗng

b) Phép toán enqueue(Q,x):

- Dùng để thêm x vào đuôi (back) của hàng đợi Q, nghĩa là thêm x vào cuối danh sách.

- Đầu (front) của hàng đợi là phần tử đầu tiên và đuôi (back, rear, tail) của hàng đợi là phần tử cuối của danh sách.

Ví dụ: Hình 4.1b cho thấy quá trình thêm các giá trị 5, 2, –4, 10, –8, 11 vào hàng đợi.

Hình 4.1b. Hàng đợi với phép toán
thêm vào

c) Phép toán dequeue(Q) dùng để lấy ra và trả về phần tử ở đầu (front) của hàng đợi Q, nghĩa là lấy ra phần tử đầu tiên của danh sách.

Ví dụ: Hình 4.1c cho thấy hàng đợi sau khi lấy ra một phần tử.

Hình 4.1c. Hàng đợi với phép toán lấy ra

Có thể biểu diễn hàng đợi bằng list của Python:

Lưu ý: Dùng kiểu dữ liệu danh sách (list) của Python để biểu diễn hàng đợi chỉ là một cách và không phải là cách duy nhất. Có nhiều cách biểu diễn khác nhưng trong phạm vi Bài 4 chỉ học cách này.

Hoạt động 2. Tìm hiểu các hàm của kiểu dữ liệu hàng đợi

a. Mục tiêu: HS hiểu và thực hiện được việc cài đặt các hàm chính của kiểu dữ liệu hàng đợi bằng list của Python.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 2. Tìm hiểu các hàm của kiểu dữ liệu hàng đợi, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Các hàm của kiểu dữ liệu hàng đợi.

d. Tổ chức thực hiện:

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 yêu cầu HS đọc Hoạt động 2 - Tìm hiểu các hàm của kiểu dữ liệu hàng đợi SGK tr.17:

Đọc, trao đổi để biết các hàm cơ bản của hàng đợi được cài đặt bằng danh sách (kiểu list của Python).

- GV chia lớp thành các nhóm 2 – 3 HS, mỗi nhóm thực hiện viết các hàm cơ bản của hàng đợi ra giấy, sau đó GV cùng HS phân tích đúng sai và rút ra kết luận.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi Củng cố tr.19 SGK:

Câu 1. Khi hàng đợi Q được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết chỉ số của các phần tử tại đầu (front) và đuôi (rear). So sánh các chỉ số này với chỉ số của các phần tử tại đáy (bottom) và đỉnh (top) của ngăn xếp (cũng được cài đặt bằng danh sách).

Câu 2. Em hãy nêu sự giống nhau và khác nhau giữa các hàm của ngăn xếp và hàng đợi được cài đặt bằng danh sách (kiểu list của Python).

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.17 – 19 và thảo luận theo nhóm thực hiện nhiệm vụ.

- GV quan sát và trợ giúp 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 5 HS lên bảng, mỗi HS viết một hàm.

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

- GV nhận xét và gọi một số HS đứng tại vị trí giải thích ý nghĩa của từng câu lệnh trong các hàm trên bảng sau đó chạy chương trình cho HS quan sát kết quả.

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

- GV chốt kiến thức:

Hàng đợi có thể được cài đặt bằng danh sách (kiểu list của Python).
Các hàm cơ bản trên hàng đợi Q gồm Queue(), isEmptyQueue(Q), enqueue(Q,x), dequeue(Q) và front(Q).

2. Tìm hiểu các hàm của kiểu dữ liệu hàng đợi

Một số hàm cơ bản của hàng đợi được cài đặt bằng danh sách (kiểu list của Python):

* Đầu (front) của hàng đợi Q là phần tử đầu tiên của danh sách, nghĩa là biến front = 0. Đuôi (rear) của hàng đợi Q là phần tử cuối của danh sách, nghĩa là biến rear = len(Q)-1. Do đó, không cần các biến front và rear.

a) Hàm Queue() dùng để tạo hàng đợi rỗng, hàm trả về danh sách rỗng:

Lệnh tạo hàng đợi Q rỗng (Q là danh sách rỗng):

b) Hàm enqueue(Q,x) dùng để thêm x vào đuôi (rear) của hàng đợi Q, nghĩa là thêm x vào cuối danh sách Q bằng hàm append():

Lệnh gọi hàm:

c) Hàm isEmptyQueue(Q):

- Trả về True nếu hàng đợi Q rỗng.

- Ngược lại trả về False.

d) Hàm dequeue(Q):

- Lấy ra phần tử tại đầu (front) của hàng đợi Q (phần tử đầu tiên của danh sách Q) và trả về phần tử này.

- Nếu Q rỗng thì hàm báo lỗi ngoại lệ ValueError và dừng chương trình.

Lệnh gọi hàm:

e) Hàm front(Q):

- Trả về phần tử tại đầu (front) của hàng đợi Q (phần tử đầu tiên của danh sách) và phần tử này vẫn còn trong hàng đợi Q (hàng đợi Q không bị thay đổi).

- Nếu Q rỗng thì hàm báo lỗi ngoại lệ ValueError và dừng chương trình.

Lệnh gọi hàm:

Một số ví dụ thiết lập và làm việc với hàng đợi:

Ví dụ 1. Các lệnh sau tạo hàng đợi rỗng và bổ sung 5 vào hàng đợi:

Ví dụ 2. Đoạn mã sau đây thêm các số lớn hơn hoặc bằng 0 vào hàng đợi Q đến khi gặp số âm:

Hướng dẫn trả lời câu hỏi Củng cố SGK tr.19:

Câu 1. Nếu hàng đợi Q được biểu diễn bằng mảng (list) trong Python thì:

- Chỉ số phần tử đầu hàng đợi: 0; Chỉ số phần tử cuối hàng đợi: len(Q) – 1.

- So sánh với ngăn xếp được biểu diễn bằng mảng (list) của Python ta có:

+ Chỉ số đầu (front) của hàng đợi chính là chỉ số đáy (bottom) của ngăn xếp.

+ Chỉ số đuôi (back, rear, tail) của hàng đợi là chỉ số đỉnh (top) của ngăn xếp.

Câu 2. Bảng sau mô tả sự giống nhau và khác nhau giữa các hàm cơ bản của ngăn xếp và hàng đợi khi các kiểu dữ liệu này được biểu diễn bằng danh sách (list) của Python.

STT	Hàm ngăn xếp	Hàm hàng đợi	So sánh
1	S = Stack()	Q = Queue()	Giống nhau hoàn toàn.
2	push(S,x)	enqueue(Q,x)	Giống nhau hoàn toàn.
3	isEmptyStack(S)	isEmptyQueue(Q)	Giống nhau hoàn toàn.
4	pop(S)	dequeue(Q)	Ngăn xếp: lấy ra phần tử cuối cùng của list. Hàng đợi: lấy ra phần tử đầu tiên của list.
5	top(S)	front(Q)	Ngăn xếp: giá trị phần tử cuối cùng. Hàng đợi: giá trị phần tử đầu tiên.

* THÔNG TIN BỔ SUNG

--------------- Còn tiếp ---------------