Giáo án điện tử chuyên đề Khoa học máy tính 12 cánh diều Bài 4 Dự án học tập: Xây dựng chương trình sử dụng kiểu dữ liệu hàng đợi và ngăn xếp

XIN CHÀO MỪNG CÁC EM

ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Em hãy nêu một số ứng dụng của kiểu dữ liệu hàng đợi và ngăn xếp trong lĩnh vực Công nghệ thông tin.

Một số ứng dụng của kiểu dữ liệu hàng đợi

Sắp xếp các tiến trình chờ xử lí của CPU

Sắp xếp thứ tự in

tài liệu

Sắp xếp thứ tự phục vụ các yêu cầu từ máy khách gửi tới máy chủ

Một số ứng dụng của kiểu dữ liệu ngăn xếp

Tác vụ hoàn tác/làm lại.

Lịch sử duyệt web trong các ứng dụng.

Theo dõi quá trình thực hiện của thuật toán quay lui, khử đệ quy,…

Giải quyết một số bài toán (tính giá trị số học, kiểm tra dấu ngoặc).

BÀI 4. DỰ ÁN HỌC TẬP:XÂY DỰNG CHƯƠNG TRÌNH SỬ DỤNG KIỂU DỮ LIỆU HÀNG ĐỢI VÀ NGĂN XẾP

NỘI DUNG BÀI HỌC

1

Giới thiệu về dự án

học tập

2

Dự án 1. Xây dựng ứng dụng kiểm tra lỗi cú pháp

NỘI DUNG BÀI HỌC

3

Dự án 2. Kí pháp nghịch đảo Ba Lan và phương pháp tính giá trị của biểu thức toán học

4

Dự án 3. Đổi màu một vùng bức tranh

GIỚI THIỆU VỀ DỰ ÁN

HỌC TẬP

PHẦN 1

1. Mục đích

• Giúp học sinh khám phá, tìm hiểu xây dựng chương trình giải quyết một số bài toán ứng dụng sử dụng hàng đợi và ngăn xếp.

Khả năng

Vận dụng kiến thức đã học để giải quyết vấn đề cụ thể.

Tìm kiếm, khai thác, học hỏi mở rộng kiến thức từ các nguồn tài nguyên về lập trình trên Internet.

Làm việc nhóm

2. Yêu cầu chung

Lớp chia thành nhiều nhóm, các nhóm độc lập, mỗi nhóm lựa chọn một dự án để thực hiện.

Mỗi nhóm bầu trưởng nhóm và thảo luận chọn bài toán để xây dựng chương trình.

Các nhóm sẽ thực hiện tạo sản phẩm ngoài giờ lên lớp. Trên lớp, 1 tiết giáo viên hướng dẫn, 2 tiết các nhóm báo cáo kết quả.

3. Hướng dẫn

Lập kế hoạch

Bước 1. Thảo luận, thống nhất chọn một trong ba dự án.

Bước 2. Lập danh sách các đầu công việc cần thực hiện và thời gian hoàn thành.

Thực hiện kế hoạch

Bước 1. Thiết kế thuật toán.

Bước 3. Thử nghiệm, kiểm thử để sửa lỗi, hiệu chỉnh chương trình.

Bước 2. Sử dụng các lệnh trong Python để viết chương trình.

Báo cáo kết quả

Bảng 1. Tiến trình báo cáo kết quả dự án

Tiêu chí đánh giá

Việc đánh giá sản phẩm và báo cáo dự án như Bảng 2. Điểm của mỗi thành viên dựa trên sự đóng góp trong dự án.

Bảng 2. Tiêu chí đánh giá

Dự án

Dự án 1. Xây dựng ứng dụng kiểm tra lỗi cú pháp.

Dự án 2. Kí pháp nghịch đảo Ba Lan và phương pháp tính giá trị của biểu thức toán học.

Dự án 3. Đổi màu một vùng bức tranh.

DỰ ÁN 1. XÂY DỰNG ỨNG DỤNG KIỂM TRA LỖI CÚ PHÁP

PHẦN 2

TÌM HIỂU VỀ DỰ ÁN

Đọc thông tin và trả lời các câu hỏi sau đây:

• Một xâu kí tự cần thoả mãn những điều kiện gì để được gọi là xâu cân bằng?
• Em hãy đưa ra một số ví dụ về xâu cân bằng và xâu không cân bằng.

Các xâu kí tự gồm các ngoặc đóng và mở cân bằng

Có đủ yếu tố ngoặc đóng và ngoặc mở, hai kí tự này phải cùng loại với nhau.

Nếu dấu mở ngoặc loại này (tạm gọi là loại a) đứng trước dấu mở ngoặc của loại khác (tạm gọi là loại b), thì dấu đóng ngoặc tương ứng của loại a phải đứng sau dấu đóng ngoặc tương ứng của loại b.

Một số ví dụ về xâu cân bằng

{}

[{}]

[](){}

{{}{}}

{[{}]}[()]

Một số ví dụ về xâu không cân bằng

• Có thể sử dụng ngôn ngữ lập trình để xây dựng chương trình kiểm tra lỗi cú pháp về thứ tự xuất hiện của các cặp ngoặc.

Khi chạy chương trình viết bằng ngôn ngữ Python ở Hình 1, ta sẽ nhận được thông báo về lỗi cú pháp ở Hình 2.

Ví dụ:

• Em hãy viết chương trình nhập vào một xâu kí tự chỉ gồm các dấu mở ngoặc và đóng ngoặc sau: [, ], {, }, (, ). Sau đó, kiểm tra xem xâu kí tự đó có cân bằng hay không. In ra màn hình thông báo “Cân bằng” nếu xâu đó là cân bằng, ngược lại in ra “Không cân bằng”.
• Mở rộng chương trình ở câu a): đọc tệp có tên test.py chứa chương trình viết bằng ngôn ngữ Python, và kiểm tra xem chương trình có lỗi cú pháp về thứ tự xuất hiện của các cặp ngoặc [, ], {, }, (,) hay không. In ra màn hình thông báo “Không có lỗi” nếu chương trình không có lỗi về các cặp ngoặc này, ngược lại in ra “Có lỗi cú pháp”.

Yêu cầu

GỢI Ý

Dùng một ngăn xếp S chỉ chứa các dấu mở ngoặc, khởi tạo ban đầu bằng rỗng. Duyệt lần lượt từng kí tự trong xâu từ trái sang phải:

Nếu kí tự hiện tại trong xâu là dấu mở ngoặc.

Thì thực hiện thao tác push đẩy kí tự đó vào ngăn xếp.

Nếu kí tự hiện tại trong xâu là dấu đóng ngoặc.

Thì thực hiện thao tác pop để lấy ra một dấu mở ngoặc ở ngăn xếp.

So sánh:

Dấu đóng ngoặc và dấu mở ngoặc không phải là một cặp.

In ra thông báo “Không cân bằng”

Dấu đóng ngoặc và dấu mở ngoặc là một cặp.

Tiếp tục duyệt kí tự tiếp theo trong xâu.

Trong tình huống ngăn xếp đã rỗng.

Không thực hiện được thao tác pop

Thuật toán kết thúc, in ra thông báo “Không cân bằng”.

Khi tất cả các kí tự trong xâu đã được duyệt xong mà trong ngăn xếp S vẫn chưa rỗng.

Số lượng dấu mở ngoặc nhiều hơn số lượng dấu đóng ngoặc.

Cần in ra thông báo “Không cân bằng”.

Cần in ra thông báo “Cân bằng”.

Chương trình kiểm tra dãy ngoặc có cân bằng hay không

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