Giáo án điện tử Khoa học máy tính 11 kết nối Bài 20: Thực hành bài toán tìm kiếm

CHÀO MỪNG CẢ LỚP QUAY TRỞ LẠI VỚI MÔN HỌC!

KHỞI ĐỘNG

Trong bài học trước, các em đã được học cách triển khai thuật toán tìm kiếm tuần tự và tìm kiếm nhị phân; vậy chúng ta có thể áp dụng các thuật toán tìm kiếm đã học vào thực tế như thế nào?

BÀI 20: THỰC HÀNH BÀI TOÁN TÌM KIẾM

NHIỆM VỤ THỰC HÀNH

Đọc và ghi tệp trong Python

Viết chương trình tra cứu điểm thi

Viết chương trình kiểm tra điểm thi

01 ĐỌC VÀ GHI TỆP TRONG PYTHON

1. a) Đối tượng tệp

• Python cho phép đọc, ghi dữ liệu với tệp văn bản (text file).
• Đối tượng tệp được tạo ra bằng lệnh open() với các cách như sau:

• Lệnh mở tệp để đọc:

f = open(<file name>,"r",encoding= "UTF -8")

• Lệnh mở tệp để ghi dữ liệu từ đầu:

f = open(<file name>,"w",encoding= "UTF=8")

• Lệnh mở tệp để ghi tiếp dữ liệu:

f = open(<file name>,"a",encoding = "UTF-8")

• Đóng đối tượng tệp bằng lệnh sau:

f.close()

1. b) Các lệnh đọc dữ liệu từ tệp văn bản

Tìm hiểu về các lệnh đọc dữ liệu từ tệp văn bản.

Ví dụ 1

Chương trình bên đọc dữ liệu từ tệp Data.inp:

1. c) Ghi dữ liệu ra tệp văn bản

• Việc ghi tệp dữ liệu ra tệp văn bản đơn giản nhất là sử dụng lệnh print(). Cú pháp lệnh print() như sau:

  print(<v1>, <v2>, file = <đối tượng file>)

• Ý nghĩa của một vài tham số trong lệnh đọc/ghi tệp dữ liệu:
  • 'r' là viết tắt của read
  • 'w' là viết tắt của write
  • 'a' là viết tắt của append

Hoạt động nhóm đôi, thực hiện các nhiệm vụ sau:

• Thực hiện ghi dữ liệu vào tệp trên máy tính.
• Thực hiện ghi tiếp dữ liệu vào tệp trên máy tính.
• Thực hiện đọc dữ liệu từ tệp trên máy tính theo các cách khác nhau: đọc toàn bộ các dòng, đọc lần lượt từng dòng.

02 VIẾT CHƯƠNG TRÌNH TRA CỨU ĐIỂM THI

Hoạt động cặp đôi

Viết chương trình tra cứu điểm thi theo tên các học sinh trong lớp. Chương trình cho phép người dùng nhập tên của học sinh cần tra cứu, sau đó kiểm tra và thông báo điểm số của học sinh cần tìm.

Gợi ý: Nhiệm vụ này có thể được thực hiện thông qua thuật toán tìm kiếm.

Lưu ý

• Mỗi dòng trong tệp dữ liệu bao gồm tên và điểm số, cần sử dụng lệnh split() để tách hai trường dữ liệu này.
• Dữ liệu điểm số được đọc dưới dạng 'string', nếu muốn sử dụng như kiểu dữ liệu dạng số, cần sử dụng hàm (float) để chuyển đổi kiểu dữ liệu.

Chương trình tham khảo:

03 VIẾT CHƯƠNG TRÌNH KIỂM TRA ĐIỂM THI

Hoạt động cặp đôi

Viết chương trình kiểm tra điểm thi của các học sinh trong một lớp học. Điểm thi của học sinh được ghi trong tệp diemthi_sx.inp, trong đó mỗi điểm thi của các học sinh được viết trong một hàng và được sắp xếp theo thứ tự tăng dần.

Chương trình đọc dữ liệu điểm thi từ tệp, sau đó cho phép người dùng nhập một điểm số cần kiểm tra. Nếu điểm số có tồn tại thì in ra vị trí mà điểm số đó xuất hiện trong tệp, nếu điểm số không tồn tại thì in ra thông báo điểm số không tồn tại. Ví dụ có cấu trúc như Hình 20.2.

Chương trình tham khảo:

LUYỆN TẬP

Chỉnh sửa lại chương trình của Nhiệm vụ 3 để cho phép chương trình có thể tìm kiếm điểm số trên danh sách điểm số được sắp xếp theo thứ tự giảm dần.

Phương án 1:

1   def BinarySearch(A,K):

2        left = 0

3        right = len(A) - 1

4        while left <= right:

5                 mid = (left + right)//2

6                 if A[mid] == K:

7                            return mid

8                 elif A[mid] > K:

9                      left = mid + 1

10                else:

11                    right = mid -1

12      return -1

Phương án 2:

1   def BinarySearch(A,K):

2        left = 0

3        right = len(A) - 1

4        while left <= right:

5                 mid = (left + right)//2

6                 if A[mid] == K:

7                            return mid

8                 elif A[mid] < K:

9                      left = mid - 1

10                else:

11                    right = mid + 1

12      return -1

VẬN DỤNG