Giáo án và PPT Khoa học máy tính 11 cánh diều Bài 7: Lập trình giải bài toán tìm kiếm

BÀI 7. LẬP TRÌNH GIẢI BÀI TOÁN TÌM KIẾM

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

GV đặt câu hỏi: Khi mới tạo một tài khoản người dùng, em được yêu cầu nhập tên người dùng “user name”. Có trường hợp em phải nhập lại tên khác vì tên vừa nhập đã có người sử dụng rồi. Theo em, máy tính làm gì ngay sau khi nhận được yêu cầu tạo mới một tài khoản? Hãy phát biểu thành một bài toán.

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

Hoạt động 1: Bài toán tìm kiếm

a) Khái niệm bài toán tìm kiếm

GV yêu cầu học sinh trao đổi: Bài toán tìm kiếm là gì ? 

Sản phẩm dự kiến:

Theo nghĩa chung nhất, bài toán tìm kiếm là: Cho một yêu cầu tìm kiếm và một tập hợp dữ liệu là phạm vi tìm kiếm. Hãy tìm mục (các mục) dữ liệu đáp ứng yêu cầu tìm kiếm đã cho hoặc khẳng định không có mục dữ liệu nào đáp ứng yêu cầu đó.

b) Tìm kiếm tuần tự bằng hàm của Python

Trình bày phương thức tìm kiếm tuần tự hằng hàm của Python.

Sản phẩm dự kiến:

- Phương thức index thực hiện tìm kiếm theo cách tuần tự cho dãy xâu kí tự, mảng hoặc danh sách.

- Các trường hợp trả về khi dùng index

+ Nếu xuất hiện nhiều lần thì đưa ra chỉ số của lần xuất hiện đầu tiên.

Ví dụ: 

a = [1, 3, 3, 4, 3, 5, 6]

print(a.index(3))

+ Báo lỗi “valueError” nếu không tìm thấy.

Ví dụ:

a = [1, 2, 3, 4, 5, 6]

print(a.index(5, 1, 4))

+ Phương thức index có hai tham số tùy chọn: lo, hi để hạn chế thực hiện tìm kiếm chỉ trong đoạn con của dãy số, bắt đầu từ chỉ số lo (lowest) và kết thúc ở hi (highest).

Cú pháp:

dãy_số.index(giá_trị, lo, hi)

Hoạt động 2: Thuật toán tìm kiếm tuần tự

Thực hiện thuật toán tìm kiếm tuần tự là gì ?

Sản phẩm dự kiến:

- Thực hiện tìm kiếm tuần tự bằng phép lặp duyệt từ đầu dãy số với điều kiện dừng khi “tìm thấy” hoặc “đã xét hết dãy số”.

Hoạt động 3: Thuật toán tìm kiếm nhị phân

Dựa trên mô tả thuật toán tìm kiếm nhị phân cho ở Hình 3, em hãy nêu tóm tắt ý tưởng của thuật toán này.

Sản phẩm dự kiến:

- Nếu dãy số đã sắp xếp theo thứ tự thì có thể áp dụng thuật toán tìm kiếm nhị phân.

- Phép lặp lại thực hiện tìm kiếm nhị phân chia đôi dãy số tại điểm “giữa” có chỉ số (lo + hi)//2, bỏ bớt nửa dãy cho đến khi “tìm thấy” hoặc hết dãy.

Hoạt động 4: Thực hành lập trình giải bài toán tìm kiếm

HS thảo luận trả lời câu hỏi: Em hãy thực hiện các yêu cầu sau:

a) Viết mã giả cho thuật toán tìm kiếm nhị phân.

b) Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân.

c) Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.

Sản phẩm dự kiến:

a) Mã giả cho thuật toán tìm kiếm nhị phân

def tkNhiPhan (x, a)                 #Phạm vi tìm kiếm là dãy ban đầu

          lo ← 0

          hi ← len(a) - 1

          while (lo ≤ hi):                #Vẫn còn trong phạm vi tìm kiếm

                   m = (lo + hi) //2     #Xác định phần tử ở giữa phạm vi tìm kiếm

                   if a_m  == x:

                             return m     #Thông báo tìm thấy x ở vị trí m và kết thúc 

                   elif x < a_m:

                             hi ← m – 1  #Loại bỏ nữa dãy chắc chắn không chứa x

else: 

          lo ← m + 1  #Phạm vi tìm kiếm là nửa dãy còn lại

          return  - 1                      #Thông báo không tìm thấy x và kết thúc

b) Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân: Kết thúc khi 2^k ~ n tức là k ~ log₂n.

c) Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân: Độ phwucs tạp thời gian logarit, O(log₂n).

HOẠT ĐỘNG LUYỆN TẬP

Câu 1. Phương thức tìm kiếm phần tử x trong một dãy tuần tự là 

A. index.                                                     B. insert.

C. extend.                                                   D. count.

Câu 2. Trong các ví dụ sau đây, có bao nhiêu ví dụ là bài toán tìm kiếm?

1) Nhập tên người, tìm số điện thoại trong danh bạ điện thoại thông minh để bắt đầu cuộc gọi.

2) Nhập số chứng minh nhân dân, số CCCD để tìm mã số thuế.

3) Nhập hàng hóa vào trong kho hàng.

4) Nhập tên và CCCD người để tìm thông tin hiến máu.

A. 1.                     B. 2.                               C. 3.                               D. 4.

Câu 3. Cho mã giả của một thuật toán:

i ← 0                                       #Số đang xét là a₀ ở đầu dãy

while (i < n):                            #(i < n) tức là chưa hết dãy số

          if a_i ≠ x:

                   i ← i + 1               #Chuyển đến xét số tiếp theo

          else:

                   return i                 #Đã tìm thấy

return Không tìm thấy

Độ phức tạp thời gian của thuật toán là

A. O(1)                 B. O(n!)                C. O(log₂n)           D. O(n)

Câu 4. Sơ đồ dưới đây mô tả thuật toán nào?

A. Thuật toán tìm kiếm tuần tự.          B. Thuật toán tìm kiếm nhị phân.

C. Thuật toán sắp xếp.                       D. Thuật toán đệ quy.

Câu 5. Hãy chỉ ra câu lệnh viết sai trong chương trình dưới đây

def tkTuanTu_for(x, a):

          i=0

          for elem in a:

                   if elem == x:

                             i = i + 1

                   else:

                             return i

          return -1

A. def tkTuanTu_for(x, a):                 B. i=0

C. if elem == x:                                  D. return -1

Đáp án gợi ý:

HOẠT ĐỘNG VẬN DỤNG

GV yêu cầu HS hoàn thành Vận dụng SGK trang 120:

Câu 1. Viết chương trình tìm kiếm vị trí tên của một người trong mỗi danh sách sau đây:

a) Danh sách học sinh của lớp em.

b) Danh sách tên các chủ tài khoản ngân hàng (kí tự không dấu) và đã sắp xếp theo thứ tự bảng chữ cái.