CHUYÊN ĐỀ 1. TÌM HIỂU MỘT VÀI KIỂU DỮ LIỆU TUYẾN TÍNH
BÀI 1. MÔ HÌNH DỮ LIỆU NGĂN XẾP VÀ HÀNG ĐỢI
Thời gian thực hiện: 2 tiết
I. MỤC TIÊU
1. Kiến thức
- Biết được mô hình dữ liệu ngăn xếp và hàng đợi.
- Hiểu được cơ chế hoạt động LIFO của ngăn xếp.
- Hiểu được cơ chế hoạt động FIFO của hàng đợi.
2. Năng lực
Năng lực chung:
- 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.
- 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 Tin học:
- Mô tả được mô hình dữ liệu ngăn xếp và hàng đợi thông qua cơ chế hoạt động của các kiểu dữ liệu này.
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
- GV: Tài liệu, Máy tính, Máy trình chiếu
- HS: SCĐ, vở ghi, máy tính, đọc trước bài 1. Mô hình dữ liệu ngăn xếp và hàng đợi
III. TIẾN TRÌNH DẠY HỌC
1. Hoạt động khởi động
a) Mục tiêu: HS làm quen với những hiện tượng, sự vật trong cuộc sống có liên quan đến mô hình ngăn xếp và hàng đợi. Tạo hứng thú học tập cho HS.
b) Nội dung: Quan sát và trả lời Phiếu học tập số 1.
PHIẾU HỌC TẬP SỐ 1
Em hãy quan sát các hình ảnh về đồ vật và hiện tượng trong hình 1.a, 1.b và trả lời 2 câu
hỏi sau:
1. Trong chồng đĩa, các đĩa đánh số từ 1 đến 5, từ dưới lên trên hãy cho biết đĩa nào được xếp vào trước, đĩa nào được lấy ra trước.
2. Ai sẽ là người được rút tiền trước tại cây ATM? Người xếp hàng cuối cùng sẽ được rút tiền khi nào?
c) Sản phẩm: Trả lời câu hỏi trong phiếu học tập số 1
d) Tổ chức thực hiện: Chia lớp thành 6 nhóm, mỗi nhóm thảo luận trong thời gian 2 phút và ghi kết quả trả lời ra giấy.
Nhiệm vụ
Cách thức tổ chức
Chuyển giao nhiệm vụ
GV yêu cầu HS quan sát và hoàn thành phiếu học tập số 1.
Thực hiện nhiệm vụ
HS tiếp nhận nhiệm vụ, thảo luận nhóm hoàn thành phiếu học tập số 1.
Báo cáo, thảo luận
GV: Thu kết quả trả lời của từng nhóm, cho HS quan sát kết quả các nhóm và nhận xét.
Kết luận, nhận định
- GV nhận xét câu trả lời của các nhóm.
+ Với hình a. Chồng đĩa ta thấy ngay đĩa nào cho vào trước thì sẽ lấy ra sau cùng, đĩa nào cho vào sau cùng sẽ lấy ra đầu tiên. Đây chính là cơ chế hoạt động của mô hình dữ liệu ngăn xếp (stack).
+ Với hình b Ai xếp hàng trước sẽ được rút tiền trước, ai xếp sau sẽ rút tiền sau theo đúng thứ tự, Đây chính là cơ chế hoạt động của mô hình hàng đợi (queue). Hai mô hình này sẽ được tìm hiểu trong bài học ngày hôm nay.
2. Hoạt động hình thành kiến thức
Hoạt động 1: Tìm hiểu mô hình dữ liệu ngăn xếp
a) Mục tiêu: Hiểu được cơ chế hoạt động của ngăn xếp, các thao tác chính và ý nghĩa của các thao tác này.
b) Nội dung hoạt động: Trả lời phiếu học tập số 2, câu hỏi củng cố.
PHIẾU HỌC TẬP SỐ 2: Hãy ghép mỗi mục ở cột A với một mục ở cột B cho phù hợp.
Cột A
Cột B
1. Ngăn xếp (stack) là gì?
2. Trình bày cơ chế hoạt động của mô hình dữ liệu ngăn xếp.
3. Thao tác đưa phần tử x vào đỉnh ngăn xếp S.
4. Tạo một ngăn xếp rỗng.
5. Lấy ra một phần tử từ đỉnh của ngăn xếp S và trả về phần tử này.
6. Trả về phần tử tại vị trí đỉnh của ngăn xếp S, S không thay đổi.
7. Kiểm tra ngăn xếp rỗng, trả về giá trị True nếu S rỗng.
a. push(S, x).
b. pop(S).
c. Là một dãy tuyến tính các phần tử dữ liệu.
d. Thao tác đưa phần tử vào và lấy phần tử ra tại cùng một đầu của ngăn xếp.
e. top(S).
f. hoạt động theo cơ chế LIFO.
g. S=Stack.
h. isEmptyStack(S).
i. thao tác đưa dữ liệu vào, lấy dữ liệu ra ở hai đầu.
c) Sản phẩm: HS hoàn thành được phiếu học tập số 2.
d) Tổ chức thực hiện: Chia lớp thành 6 nhóm, mỗi nhóm thảo luận thống nhất phương án trả lời.
Nhiệm vụ
Cách thức tổ chức
Chuyển giao nhiệm vụ 1
GV yêu cầu HS thảo luận nhóm để hoàn thành phiếu học tập số 2.
Thực hiện nhiệm vụ 1
HS tiếp nhận nhiệm vụ, nghiên cứu SCĐ thảo luận nhóm hoàn thành phiếu học tập số 2.
GV quan sát HS tự học, thảo luận, trợ giúp kịp thời khi các em cần hỗ trợ, giải đáp.
Báo cáo, thảo luận
GV: Gọi đại diện các nhóm trình lên bảng viết đáp án của nhóm mình. GV yêu cầu các nhóm quan sát, nhận xét chấm điểm cho từng nhóm.
Kết luận, nhận định
Phiếu học tập số 2: 1c, 2f, 3a, 4g, 5b, 6e, 7h.
- GV nhận xét, chuẩn hoá kiến thức cho HS ghi nhớ. Mô hình dữ liệu ngăn xếp được mô tả như sau:
+ Là một dãy tuyến tính các phần tử dữ liệu.
+ Có thao tác đưa phần tử vào, lấy phần tử ra tại cùng 1 đầu.
+ Quy ước đỉnh (top) của ngăn xếp để đưa vào, lấy ra.
+ Hoạt động theo cơ chế LIFO (vào sau ra trước).
+ Các thao tác cơ bản trên dữ liệu ngăn xếp:
- Tạo một ngăn xếp rỗng: S=Stack().
- Đưa 1 phần tử x vào đỉnh ngăn xếp s: push(S,x).
- Lấy ra 1 phần tử từ đỉnh ngăn xếp: pop(S).
- Giá trị của phần tử đỉnh ngăn xếp: top(S).
- Kiểm tra ngăn xếp rỗng (trả về giá trị True) : isemptystack(S). Ví dụ: S=Stack().
push(S,2); push(S,1); push(S,5) kết quả trong S chứa 3 phần tử là 2, 1, 5.
Chuyển giao nhiệm vụ 2
Trả lời 2 câu hỏi củng cố trong sách trang 7.
1. Muốn lấy phần tử ở đáy ngăn xếp phải làm thế nào?
2. Cho S là 1 ngăn xếp rỗng. Em hãy cho biết khi thực hiện các lệnh sau thì S sẽ chứa những phần tử nào:
Push(S,1); push(S,5); pop(S); push(S,10);
Thực hiện nhiệm vụ 2
HS tiếp nhận nhiệm vụ, nghiên cứu SCĐ thảo luận nhóm hoàn thành 2 câu hỏi củng cố.
GV quan sát, trợ giúp kịp thời khi các em cần hỗ trợ, giải đáp.
Báo cáo, thảo luận
GV: Gọi đại diện các nhóm trình lên bảng viết đáp án của nhóm mình. GV yêu cầu các nhóm quan sát, nhận xét chấm điểm cho từng nhóm.
Kết luận, nhận định
GV gọi 1 HS chốt lại phương án đúng.
1: Để lấy phần tử ở đáy phải pop(S) tất cả các phần tử trong Stack ra thì mới lấy được phần tử ở đáy ngăn xếp.
2: cho kết quả 1, 10.
Hoạt động 2: Tìm hiểu mô hình dữ liệu hàng đợi
a) Mục tiêu: Hiểu được cơ chế hoạt động của hàng đợi, các thao tác cơ bản của và ý nghĩa của các thao tác này.
b) Nội dung hoạt động: Trả lời phiếu học tập số 3, câu hỏi củng cố.
PHIẾU HỌC TẬP SỐ 3: Hãy ghép mỗi mục ở cột A với một mục ở cột B cho phù hợp.
Cột A
Cột B
1. Hàng đợi (queue) là gì?
2. Trình bày cơ chế hoạt động của mô hình dữ liệu hàng đợi.
3. Thao tác đưa phần tử x vào cuối hàng đợi Q.
4. Tạo một hàng đợi rỗng.
5. Lấy ra một phần tử tại đầu của hàng đợi Q và trả về phần tử này.
6. Trả về phần tử đầu của hàng đợi Q và Q không thay đổi.
7. Kiểm tra hàng đợi rỗng, trả về giá trị True nếu Q rỗng, ngược lại trả về False.
a. Q=Queue().
b. enqueue(Q,x).
c. Là một dãy tuyến tính các phần tử dữ liệu.
d. Thao tác đưa phần tử vào và lấy phần tử ra tại cùng một đầu của hàng đợi.
e. dequeue(Q).
f. Hoạt động theo cơ chế FIFO.
g. front(Q).
h. Thao tác đưa dữ liệu vào ở một đầu, lấy dữ liệu ở một đầu khác.
i. isEmptyQueue(Q).
c) Sản phẩm: HS hoàn thành được phiếu học tập số 3.
d) Tổ chức thực hiện: Chia lớp thành 6 nhóm, mỗi nhóm thảo luận thống nhất phương án trả lời.
Nhiệm vụ
Cách thức tổ chức
Chuyển giao nhiệm vụ 1
GV yêu cầu HS thảo luận nhóm, nghiên cứu SCĐ để hoàn thành phiếu học tập số 3.
Thực hiện nhiệm vụ 1
HS tiếp nhận nhiệm vụ, nghiên cứu SCĐ thảo luận nhóm hoàn thành phiếu học tập số 3 và 2 câu hỏi củng cố.
GV quan sát HS tự học, thảo luận, trợ giúp kịp thời khi các em cần hỗ trợ, giải đáp.
Báo cáo, thảo luận
GV: Gọi đại diện các nhóm trình lên bảng viết đáp án của nhóm mình. GV yêu cầu các nhóm quan sát, nhận xét chấm điểm cho từng nhóm.
Kết luận, nhận định
Phiếu học tập số 3: 1c, 2f, 3b, 4a, 5e, 6g, 7i.
- GV nhận xét, chuẩn hoá kiến thức cho HS ghi nhớ. Mô hình dữ liệu hàng đợi được mô tả như sau:
+ Là một dãy tuyến tính các phần tử dữ liệu.
+ Có thao tác đưa phần tử vào cuối hàng đợi, lấy một phần tử ra tại đầu hàng đợi.
+ Quy ước đầu dùng để đưa dữ liệu ra đuôi của hàng đợi (back). Đầu ngược lại dùng để lấy dữ liệu ra (front) của hàng đợi.
+ Hoạt động theo cơ chế FIFO (vào trước, ra trước).
+ Các thao tác cơ bản trên dữ liệu ngăn xếp:
- Tạo một hàng đợi rỗng: Q=Queue().
- Đưa 1 phần tử x vào cuối hàng đợi Q: enqueue(Q,x).
- Lấy ra 1 phần tử tại đầu của hàng đợi Q và trả về phần tử này: dequeue(Q).
- Trả về phần tử đầu của hàng đợi Q và Q không thay đổi: front(Q).
- Kiểm tra hàng rỗng (trả về giá trị True) : isEmptyQueue(Q). Ví dụ 1: Q=Queue().
Ví dụ 2: x=dequeue(Q); lấy giá trị đầu hàng đợi Q lưu vào x. enqueue(Q,x) đẩy giá trị x vào cuối hàng đợi Q.
Chuyển giao nhiệm vụ 2
GV nêu câu hỏi, HS thảo luận, suy nghĩ phát biểu:
1. Chỉ ra những điểm giống và khác nhau giữa ngăn xếp và hàng đợi.
2. Sau khi thực hiện các lệnh sau, hỏi trong hàng đợi Q có những giá trị nào?
Q=Queue().
Enqueue(Q,2); enqueue(Q,10); dequeue(Q); enqueue(Q,1); dequeue(Q).
Thực hiện nhiệm vụ 2
HS tiếp nhận nhiệm vụ, nghiên cứu SCĐ thảo luận nhóm hoàn thành 2 câu hỏi củng cố.
GV quan sát HS tự học, thảo luận, trợ giúp kịp thời khi các em cần hỗ trợ, giải đáp.
Báo cáo, thảo luận
GV: Gọi đại diện các nhóm trình lên bảng viết đáp án của nhóm mình. GV yêu cầu các nhóm quan sát, nhận xét chấm điểm cho từng nhóm.
1. Giống nhau: Stack và Queue là các cấu trúc dữ liệu được sử dụng để lưu trữ các yếu tố dữ liệu và nó dựa trên một số các ví dụ có thực trong cuộc sống hàng ngày của chúng ta. Cho phép đưa dữ liệu vào và lấy dữ liệu ra.
Khác nhau: Sự khác biệt lớn nhất giữa Stack và Queue là Stack sử dụng phương thức LIFO (last in first out) để truy cập và thêm các phần tử dữ liệu trong khi Queue sử dụng phương thức FIFO (First in first out) để truy cập và thêm các phần tử dữ liệu.
Stack chỉ có một đầu mở để pushing và popping các phần tử dữ liệu, còn Queue có cả hai đầu mở để enqueuing và dequeuing các phần tử dữ liệu.
2. Trong Q có giá trị 1.
3. Hoạt động luyện tập
a) Mục tiêu: Củng cố kiến thức đã học.
b) Nội dung: Trả lời câu hỏi 1, 2 phần luyện tập.
c) Sản phẩm: Bài làm của HS, kĩ năng giải quyết nhiệm vụ học tập.
1. Dãy số mới thu được là đảo ngược của dãy số đưa vào.
2. Cho dãy số 2, 5, 1, 0, 10, khi đưa các giá trị lẻ vào ngăn xếp sau đó lấy ra ta thu được dãy số: 1, 5.
d) Tổ chức thực hiện: HS làm ngay vào vở ghi, GV kiểm tra bài làm của HS qua vở ghi HS và gọi hai HS chữa bài.
GV gọi HS khác nhận xét, đánh giá, chốt đáp án.
4. Hoạt động vận dụng
a) Mục tiêu: HS vận dụng được kiến thức để làm bài tập.
b) Nội dung: Làm bài tập 1, 2 phần vận dụng SCĐ trang 8.
Bài 1:
+ Xếp hàng mua vé tàu là mô hình hàng đợi, ai đến trước mua trước, ai đến sau mua sau.
+ Bánh quy xếp vào trong hộp đứng, Bánh nào xếp vào đầu tiên sẽ ăn sau, bánh xếp sau cùng ở trên cùng sẽ được ăn trước.
Bài 2. Cách thực hiện như sau:
Bước 1. Lần lượt lấy các số từ ngăn xếp S ra và đưa vào hàng đợi Q. Bước 2. Lần lượt lấy các số từ hàng đợi Q và đưa vào ngăn xếp S.
Sau các bước trên ngăn xếp S sẽ chứa các phần tử theo thứ tự ngược lại so với dãy ban đầu nằm trong S.
c) Sản phẩm: Bài làm trong vở của HS.
d) Tổ chức thực hiện: HS làm ở nhà, tiết học sau kiểm tra vở ghi HS và gọi một số HS chữa bài.
- GV nhận xét, đánh giá, đưa ra một vài ý mà HS còn thiếu, chốt đáp án.
IV. HƯỚNG DẪN VỀ NHÀ
- Ghi nhớ kiến thức trong bài.
- Hoàn thành các bài tập phần vận dụng.
- Đọc trước bài 2 kiểu dữ liệu ngăn xếp.
BÀI 2. KIỂU DỮ LIỆU NGĂN XẾP
Thời gian thực hiện: 2 tiết
I. MỤC TIÊU
1. Kiến thức
− Biểu diễn được kiểu dữ liệu ngăn xếp 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.
2. Năng lực
Năng lực chung:
- 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.
- 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.
- 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 Tin học:
− Biểu diễn được ngăn xếp 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 ngăn xếp.
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.
- 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
- GV: Sách chuyên đề, SGV, tài liệu tham khảo, Máy tính, Máy chiếu.
- HS: Sách chuyên đề, vở ghi, máy tính, đọc trước bài 3. Thực hành với kiểu dữ liệu ngăn xếp.
III. TIẾN TRÌNH DẠY HỌC
1. 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 trả lời câu hỏi sau:
Theo em, những kiểu dữ liệu sau có thể được dùng để thiết lập dữ liệu ngăn xếp không? Tại sao?
+ Sử dụng kiểu mảng có chiều dài cố định N, với số tự nhiên N khá lớn.
+ Sử dụng kiểu dữ liệu danh sách liên kết.
+ Sử dụng kiểu dữ liệu list của python.
c) Sản phẩm: Câu trả lời của HS.
d) Tổ chức thực hiện: chia lớp thành ba nhóm thảo luận và ghi ra giấy câu trả lời của nhóm. GV gọi đại diện lần lượt ba nhóm trả lời.
GV: Nhận xét có thể dùng được ba kiểu dữ liệu trên để biểu diễn mô hình dữ liệu ngăn xếp được Nếu có thì các thao tác chính như pop() và push() sẽ được thiết lập như thế nào? Chúng ta cùng tìm hiểu trong bài học này.
2. Hoạt động hình thành kiến thức
Hoạt động 2.1: Tìm hiểu biểu diễn ngăn xếp bằng mảng một chiều.
a) Mục tiêu: HS biết được cách sử dụng kiểu dữ liệu list trong Python để mô tả ngăn xếp thông qua phiếu học tập số 1.
b) Nội dung:
1. Nhắc lại kiểu dữ liệu list của Python, các hàm cơ bản, phương thức thường hay dùng trong list.
− List là một dãy các phần tử tuyến tính, đánh chỉ số từ 0.
− Có thể tạo list rỗng bằng lệnh A = [] hoặc A = list().
− List trong Python có thể có không hạn chế các phần tử.
− Bổ sung thêm phần tử x vào cuối của danh sách A bằng phương thức A.append(x).
− Phần tử cuối của list A có chỉ số len(A)−1.
− Hàm A.pop() sẽ xoá phần tử cuối của A và trả về giá trị phần tử này.
2. Ngăn xếp được cài đặt bằng mảng 1 chiều (kiểu list). Các thao tác sau trên ngăn xếp cần được mô tả bằng lệnh tương ứng bằng các lệnh trên list của Python.
Thao tác trên ngăn xếp
Lệnh tương ứng trên list của Python
Tạo ngăn xếp rỗng
Tạo list rỗng
push(S,x)
Bổ sung x vào list bằng lệnh append()
pop(S)
Phương thức pop()
top(S) – đỉnh của S
Phần tử đáy của ngăn xếp là phần tử đầu tiên của list
bottom – đáy của S
Phần tử đỉnh của ngăn xếp là phần tử cuối cùng của list
Câu 1. Điền vào chỗ trống:
PHIẾU HỌC TẬP SỐ 1
- Thêm một phần tử x vào cuối danh sách A:…………………………………
- Khởi tạo danh sách A:………………………………………………………..
- Số lượng phần tử trong danh sách A:………………………………………...
- Phần tử cuối cùng trong danh sách A có địa chỉ là:………………………….
- Xoá phần tử cuối cùng trong danh sách A:…………………………………. Câu 2. Ghép nối các dòng cột A với cột B cho đúng:
A.
B.
a. S=[]
1. Đỉnh của ngăn xếp là phần tử cuối cùng của danh sách
b. push(S,x)
2. Lấy ra và trả về phần tử ở đỉnh ngăn xếp
c. pop(S)
3. Khởi tạo ngăn xếp S
d. top (Đỉnh của ngăn xếp)
4. Đẩy phần tử có giá trị x vào ngăn xếp S
e. bottom (Đáy của ngăn xếp)
5. Là phần tử đầu tiên của danh sách
c) Sản phẩm: Bài làm của HS.
d) Tổ chức thực hiện: chia lớp thành 6 nhóm, các nhóm thảo luận và hoàn thành phiếu học tập số 1.
Nhiệm vụ
Cách thức tổ chức
Chuyển giao nhiệm vụ
GV: Phát phiếu học tập số 1.
Thực hiện nhiệm vụ
HS nhận phiếu học tập, nghiên cứu sách giáo khoa, thảo luận để trả lời các câu hỏi trong phiếu học tập số 1.
GV: Quan sát các nhóm làm bài.
Báo cáo, thảo luận
GV gọi mỗi nhóm 2 HS lên bảng ghi kết quả bài làm của nhóm mình lên bảng.
HS: Lên bảng trình bày.
Kết luận, nhận định
GV: Nhận xét kết quả làm của từng nhóm. Khẳng định chung các nhóm đểu khẳng định rằng có thể biểu diễn ngăn xếp bằng list của Python.
Hai phép toán push(S,x) : đẩy x vào S. pop(S): lấy phần tử cuối của mảng.
Phần tử đỉnh (top) của ngăn xếp là phần tử cuối cùng của danh sách. Câu 1 (SCD trang 10): 1, 3, 5.
Câu 2(SCD trang 10): 2, 3, 1.
Chuyển giao nhiệm vụ
Yêu cầu cả lớp làm nhanh bài 1, 2 SCĐ trang 10 phần củng cố kiến thức.
Thực hiện nhiệm vụ
HS làm bài vào vở.
Báo cáo, thảo luận
GV kiểm tra kết quả làm bài của HS trong vở.
Kết luận, nhận định
GV: Chấm điểm cho 2 HS làm bài xong nhanh nhất, nhận xét bài làm của HS, phân tích chạy chương trình để HS hiểu thao tác push(s,x) và pop(S).
HS: Quan sát chương trình và kết quả chạy chương trình.
Hoạt động 2.2: Tìm hiểu các phép toán của kiểu dữ liệu ngăn xếp.
a) Mục tiêu: HS hiểu và cài đặt được các hàm cơ bản của ngăn xếp bằng list của Python.
b) Nội dung: Các phép toán của kiểu dữ liệu ngăn xếp.
1. Hàm Stack() khởi tạo ngăn xếp rỗng.
2. Hàm push(S,x) dùng để thêm x vào đỉnh (top) của ngăn xếp.
3. Hàm isEmptyStack(S) trả về True nếu ngăn xếp S rỗng, ngược lại trả về False.
4. Hàm pop(S) dùng để lấy ra các phần tử tại đỉnh (top) của ngăn xếp S, Nếu ngăn xếp rỗng hàm này báo lỗi ngoại lệ ValueError.
5. Hàm top(S) trả về.
c) Sản phẩm: Bài làm của HS trong vở ghi.
Sản phẩm dự kiến:
2. Các phép toán của kiểu dữ liệu ngăn xếp
a. Hàm Stack() khởi tạo ngăn xếp rỗngP:
def Stack():
return []
b. Hàm push(S,x) dùng để thêm x vào đỉnh (top) của ngăn xếp:
def push(S,x):
S.append(x)
c. Hàm isEmptyStack(S) trả về True nếu ngăn xếp S rỗng, ngược lại trả về False:
def isEmptyStack(S): return len(S)==0
d. Hàm pop(S) dùng để lấy ra các phần tử tại đỉnh (top) của ngăn xếp S, Nếu ngăn xếp rỗng hàm này báo lỗi ngoại lệ ValueError:
def pop(S):
if isEmptyStack(S):
raise valueError(‘Ngăn xếp rỗng”) else: return S.pop()
e. Hàm top(S) trả về phần tử tại đỉnh ngăn xếp S:
def pop(S):
if isEmptyStack(S):
raise valueError(‘Ngăn xếp rỗng’) else: return S[len(S)‐1]
Củng cố: 1.
S=Stack() push(S,20);push(S,8);push(S,15) while not isEmptyStack(S):
x=pop(S) print(x,end=‘ ’)
kết quả:15 8 20
2. Hàm pop(S)
def pop(S):
if isEmptyStack(S):
raise valueError(‘Ngăn xếp rỗng không thể thực hiện được”) else: return S.pop()
Hàm top(S)
def top(S):
if isEmptyStack(S):
raise valueError(‘Ngăn xếp rỗng không thể thực hiện được’) else: return S[len(S)‐1]
3. Khi sử dụng list để biểu diễn ngăn xếp thì ta luôn có chỉ số phần tử đáy là 0, chỉ số phần tử ở đỉnh là len(S)−1, do đó không cần các biến top hay bottom.
d) Tổ chức thực hiện: Chia lớp thành 6 nhóm, các nhóm thảo luận, giải thích ý nghĩa các hàm, các câu lệnh trong mỗi hàm, viết các hàm cơ bản của Ngăn xếp vào vở và gõ trên máy tính.
Hoạt động của GV và HS Bước 1: Chuyển giao nhiệm vụ
GV: Hãy nghiên cứu SCĐ và viết các phép toán của kiểu dữ liệu ngăn xếp:
1. Hàm Stack() khởi tạo ngăn xếp rỗng.
2. Hàm push(S,x) dùng để thêm x vào đỉnh (top) của ngăn xếp.
3. Hàm isEmptyStack(S) trả về True nếu ngăn xếp S rỗng, ngược lại trả về False.
4. Hàm pop(S) dùng để lấy ra các phần tử tại đỉnh (top) của ngăn xếp S, Nếu ngăn xếp rỗng hàm này báo lỗi ngoại lệ ValueError.
5. Hàm top(S) trả về.
Bước 2: Thực hiện nhiệm vụ
HS: Viết 5 hàm ra vở, giải thích ý nghĩa của từng câu lệnh. GV: Quan sát và trợ giúp HS.
Bước 3: Báo cáo, thảo luận
HS: Mở vở cho GV kiểm tra.
GV: Kiểm tra vở ghi của HS, gọi 5 HS lên bảng mỗi HS viết một hàm.
Bước 4: Kết luận, nhận định
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.
Chạy chương trình cho HS quan sát kết quả.
HS: Nghe, quan sát và ghi nhớ các hàm.
Bước 1: Chuyển giao nhiệm vụ
GV: Nêu yêu cầu cho HS.
1. Với dãy câu lệnh trên khi chạy chương trình màn hình in ra kết quả như thế nào?
2. Sửa lại hàm pop(S) và top(S) nếu ngăn xếp rỗng thì thông báo “Ngăn xếp rỗng không thể thực hiện được lệnh này.
3. Vì sao các hàm cơ bản trên ngăn xếp được cài bằng danh sách không cần sử dụng biến top và bottom?
Bước 2: Thực hiện nhiệm vụ
HS: Thảo luận, trả lời, viết ra vở ghi.
Bước 3: Báo cáo, thảo luận
Gọi 3 HS bất kì trong ba nhóm lên bảng trình bày.
GV: Gọi một số HS nhận xét. GV chạy chương trình trên máy tính cho HS quan sát.
Bước 4: Kết luận, nhận định
GV: Nhận xét đánh giá cho điểm bài làm tốt của một số HS. HS: Ghi nhớ.
3. Hoạt động luyện tập
a) Mục tiêu: HS hiểu được các hàm cơ bản của ngăn xếp.
b) Nội dung: làm bài tập 1, 2 phần luyện tập SCĐ trang 12.
c) Sản phẩm: Bài làm của HS trong vở ghi hoặc trên máy tính của HS.
d) Tổ chức thực hiện: Chia lớp thành 6 nhóm, các nhóm thảo luận, giải thích ý nghĩa các hàm, các câu lệnh trong mỗi hàm, viết các hàm.
Hoạt động của GV và HS
Sản phẩm dự kiến
Bước 1: Chuyển giao nhiệm vụ
GV: Yêu cầu HS làm bài 1, 2 SCĐ trang 12 phần luyện tập.
Bước 2: Thực hiện nhiệm vụ
HS: Thảo luận, trả lời, viết ra vở ghi.
Bước 3: Báo cáo, thảo luận
Gọi 2 HS bất kì trong ba nhóm lên bảng trình bày. GV: Gọi 2 HS nhận xét.
Bước 4: Kết luận, nhận định
GV: Nhận xét đánh giá cho điểm bài làm của 2 HS. HS: Ghi nhớ.
Hàm length(S) def length(S):
return len(S)
2. Các lệnh đã thực hiện
push(S,2)
push(S,7)
push(S,6) pop(S)
pop(S) push(S,1) pop(S)
pop()
4. Hoạt động vận dụng
a) Mục tiêu: HS vận dụng kiến thức về kiểu dữ liệu ngăn xếp viết chương trình đáp ứng yêu cầu của bài.
b) Nội dung: Làm bài tập 1, 2 SCĐ trang 12 phần vận dụng.
c) Sản phẩm: Bài làm của HS trong vở ghi hoặc trong máy tính.
d) Tổ chức thực hiện: HS làm ở nhà, tiết sau GV gọi 2 HS lên bảng chữa bài.
Sản phẩm dự kiến:
Bài 1. Hàm kiểm tra xâu bt chỉ bao gồm các kí tự “(”, “)” có hợp lệ hay không có thể viết như sau: Hàm sẽ trả lại True nếu biểu thức đúng, ngược lại trả về False.
from Stack import * def checkbt(a):
S=Stack() kq=True for i in a:
if i==(:
push(S,i)
if i==):
if isEmptyStack(S): kq=False
break else:
pop(S)
return isEmptyStack(S) and kq a=input()
if checkbt(a): print(a+là biểu thức
đúng)
else: print(a+không là biểu thức
đúng)
Chương trình lưu trong tệp Stack.py
def Stack():
return [] def push(S,x):
S.append(x)
def isEmptyStack(S): return len(S)==0
def pop(S):
if isEmptyStack(S):
raise valueError(Ngăn xếp
rỗng)
else:
return S.pop() def top(S):
if isEmtyStack(S):
raise valueError(Ngăn xếp
rỗng)
else:
return S[len(S)‐1]
Bài 2. Chương trình thiết lập kiểu dữ liệu ngăn xếp dựa trên mảng dữ liệu cho trước có độ dài cố định N có thể như sau (lưu vào tệp Stack_segment.py).
N=20
T=[None]*N topIdx=‐1 def Stack():
global topIdx topIdx=‐1 return T
def isEmptyStack(S): return topIdx==‐1
def stackOverflow(S): return topIdx==N‐1
def push(S,x): global topIdx
if stackOverflow(S):
raise ValueError(Ngăn xếp bị tràn) else:
topIdx+=1 S[topIdx]=x
def pop(S):
global topIdx
if isEmptyStack(S):
raise ValueError(Ngăn xếp rỗng) else:
x=S[topIdx] topIdx‐=1 return x
def top(S):
if isEmptyStack(S):
raise ValueError(Ngăn xếp rỗng) else:
return S[topIdx]
IV. HƯỚNG DẪN VỀ NHÀ
- Ghi nhớ kiến thức trong bài.
- Hoàn thành các bài tập phần vận dụng.
- Đọc trước bài 3. Thực hành với kiểu dữ liệu ngăn xếp.
BÀI 3. THỰC HÀNH VỚI DỮ LIỆU NGĂN XẾP
Thời gian thực hiện: 2 tiết thực hành
I. MỤC TIÊU
1. Kiến thức
- Biết cách sử dụng cấu trúc dữ liệu ngăn xếp để giải quyết các bài toán thực tế.
2. Năng lực

onthicaptoc.com KHBD Chuyen de Tin hoc 12 KNTT