Video giảng 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

Tóm lược nội dung

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

Thông qua video này, các em sẽ nắm được các kiến thức và kĩ năng như sau:

• Phát biểu được bài toán tìm kiếm.
• Viết được chương trình cho một số thuật toán tìm kiếm.
• Vận dụng được quy tắc thực hành xác định độ phức tạp của một vài thuật toán tìm kiếm đơn giản.

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

Trước khi bước vào bài học ngày hôm nay, các em suy nghĩ và trả lờ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

Nội dung 1: Bài toán tìm kiếm

Em hãy:

- Cho biết bài toán tìm kiếm là gì ? 

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

Video trình bày nội dung:

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

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

- 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)

Nội dung 2: Thuật toán tìm kiếm tuần tự

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

Video trình bày nội dung:

- 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ố”.

Nội dung 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.

Video trình bày nội dung:

- 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.

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

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.

Video trình bày nội dung:

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).

………..

Nội dung video Bài 7: Lập trình giải bài toán tìm kiếm còn nhiều phần rất hấp dẫn và thú vị. Hãy cùng đăng kí để tham gia học bài và củng cố kiến thức thông qua hoạt động luyện tập và vận dụng trong video.