Nội dung chính tin học 11 theo định hướng khoa học máy tính cánh diều Chủ đề F(CS) 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

1. BÀI TOÁN TÌM KIẾM

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

Ví dụ:

+ Cho mã cuốn sách, hãy tìm cuốn sách trong kho sách của thư viện.

+ Tìm một tên người trong danh sách khám bệnh…

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)

2. THUẬT TOÁN TÌM KIẾM TUẦN TỰ

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

Chi tiết dần từng bước thuật toán tìm kiếm tuần tự

Từ mô tả liệt kê các bước của thuật toán tìm kiếm tuần tự chuyển thành mã giả

3. THUẬT TOÁN TÌM KIẾM NHỊ PHÂ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.

4. THỰC HÀNH LẬP TRÌNH GIẢI BÀI TOÁN TÌM KIẾM

Nhiệm vụ 1.

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

Nhiệm vụ 2.

a) Tham khảo 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

b) Tham khảo chương trình dưới đây:

def tkTuanTu_for(x, a):

     i=0

     while(i < len(a)):

         if a[i] == x:

              return i

         else:

              i = i + 1

     return -1

c) Tham khảo chương trình dưới đây:

def tkTuanTu(x, a, lo, hi):

     if lo >= len(a) or hi >= len(a) or lo >= hi:

                        print('tham số không hợp lệ')

         return

     for i in range(lo, hi):

         if a[i] == x:

              return i

     return -1

Nhiệm vụ 3. Tham khảo chương trình dưới đây:

def tkNhiPhan(x,a):

     l = 0

     r = len(a) - 1

     while(l<=r):

         mid = (1 + r)//2

         if(a[mid] == x):

              return mid

         elif(x < a[mid]):

              r = mid - 1

         elif(x > a[mid]):

              1 = mid + 1

return -1