Bài 7. Lập trình giải bài toán tìm kiếm

Trong cuộc sống hàng ngày, chúng ta thường phải đối mặt với việc tìm kiếm thông tin hoặc giải quyết các vấn đề khác nhau. Việc tìm kiếm thông minh dựa trên máy tính đã trở thành một công cụ quan trọng, giúp chúng ta tiết kiệm thời gian và nhanh chóng tìm ra những giá trị mà chúng ta cần.

Bạn đang xem: Bài 7. Lập trình giải bài toán tìm kiếm

Tìm kiếm thông minh – Tạo tài khoản người dùng

Khi tạo một tài khoản người dùng mới, chúng ta thường được yêu cầu nhập tên người dùng. Tuy nhiên, có những trường hợp tên đã tồn tại trong hệ thống. Vậy máy tính làm gì khi nhận được yêu cầu tạo mới một tài khoản? Hãy xem thành một bài toán đơn giản:

Bài toán tạo tài khoản người dùng mới

Dữ liệu đầu vào:

• Yêu cầu tạo mới một tài khoản người dùng.
• Tên người dùng được nhập vào hệ thống.

Quy trình xử lý:

1. Hệ thống nhận tên người dùng từ người dùng mới.
2. Hệ thống kiểm tra, tìm kiếm xem tên người dùng đã tồn tại trong hệ thống chưa.
3. Nếu tên người dùng đã tồn tại:
   • Hệ thống thông báo cho người dùng biết rằng tên người dùng đã có người sử dụng.
   • Yêu cầu người dùng nhập một tên người dùng khác.
   • Quay lại bước 1 để tiếp tục quá trình tạo mới tài khoản.
4. Nếu tên người dùng chưa tồn tại:
   • Hệ thống chấp nhận tên người dùng và tiếp tục quá trình tạo mới tài khoản.

Dữ liệu đầu ra:

• Tài khoản người dùng mới được tạo với tên người dùng đã được xác nhận là chưa có người sử dụng trong hệ thống.

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

Nhiệm vụ 1: Tìm kiếm nhị phân

Xem thêm : Phân Biệt Epoch – Batch Size Và Iterations

Xem thêm : Tuổi Giáp Tý 1984 đặt bếp hướng nào hợp phong thủy, thịnh vượng nhất

Yêu cầu:

• Viết mã giả cho thuật toán tìm kiếm nhị phân.
• Ướ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 lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.

Giải pháp:

Hàm tkNhiPhan(mảng, giá_trị_cần_tìm):
    Bắt đầu = 0
    Kết thúc = Độ dài của mảng - 1
    WHILE Bắt đầu <= Kết thúc:
        Giữa = (Bắt đầu + Kết thúc) // 2
        Nếu mảng[Giữa] == giá_trị_cần_tìm:
            Trả về Giữa # Tìm thấy giá trị, trả về vị trí của nó
        Nếu mảng[Giữa] < giá_trị_cần_tìm:
            Bắt đầu = Giữa + 1 # Giảm không gian tìm kiếm bằng cách loại bỏ nửa mảng bên trái
        Ngược lại:
            Kết thúc = Giữa - 1 # Giảm không gian tìm kiếm bằng cách loại bỏ nửa mảng bên phải
    Trả về -1 # Nếu không tìm thấy giá trị, trả về -1

Ướ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 ~ log2n.

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

Nhiệm vụ 2: Tìm kiếm tuần tự

Xem thêm : Phân Biệt Epoch – Batch Size Và Iterations

Xem thêm : Tuổi Giáp Tý 1984 đặt bếp hướng nào hợp phong thủy, thịnh vượng nhất

Yêu cầu:

• Viết chương trình Python thực hiện tìm kiếm tuần tự.
• Viết phiên bản tìm kiếm tuần tự thứ hai, dùng vòng lặp for thay cho vòng lặp while (hoặc ngược lại).
• Viết phiên bản tìm kiếm tuần tự có thêm hai tham số đầu vào lo và hi tương tự như của hàm index. So sánh kết quả với phương thức index của Python.

Giải pháp:

def tkTuanTu_for(x, a):
    i = 0
    for elem in a:
        if elem != x:
            i = i + 1
        else:
            return i
    return -1

def tkTuanTu_while(x, a):
    i = 0
    while (i < len(a)):
        if a[i] == x:
            return i
        else:
            i = i + 1
    return -1

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: Tìm kiếm nhị phân

Xem thêm : Phân Biệt Epoch – Batch Size Và Iterations

Xem thêm : Tuổi Giáp Tý 1984 đặt bếp hướng nào hợp phong thủy, thịnh vượng nhất

Yêu cầu:

• Viết hàm thực hiện tìm kiếm nhị phân nhận hai tham số đầu vào: Dãy số a và giá trị x cần tìm.

Giải pháp:

def tkNhiPhan(x, a):
    l = 0
    r = len(a) - 1
    while (l <= r):
        mid = (l + r) // 2
        if (a[mid] == x):
            return mid
        elif (x < a[mid]):
            r = mid - 1
        elif (x > a[mid]):
            l = mid + 1
    return -1

Vận dụng

Xem thêm : Phân Biệt Epoch – Batch Size Và Iterations

Xem thêm : Tuổi Giáp Tý 1984 đặt bếp hướng nào hợp phong thủy, thịnh vượng nhất

Yêu cầu:

• 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:
  • Danh sách học sinh của lớp em.
  • Danh sách tên của các chủ tài khoản ngân hàng (kí tự không dấu) và đã sắp thứ tự theo bảng chữ cái.

Giải pháp:

• Đối với danh sách học sinh của lớp em, tìm kiếm tuần tự có thể được áp dụng vì chưa biết danh sách đã được sắp xếp hay chưa.

  def tkTuanTu(x, a):
    i = 0
    for elem in a:
        if elem != x:
            i = i + 1
        else:
            return i
    return -1

• Đối với danh sách tên của các chủ tài khoản ngân hàng đã được sắp xếp theo thứ tự bảng chữ cái, tìm kiếm nhị phân có thể được áp dụng.

  def tkNhiPhan(x, a):
    l = 0
    r = len(a) - 1
    while (l <= r):
        mid = (l + r) // 2
        if (a[mid] == x):
            return mid
        elif (x < a[mid]):
            r = mid - 1
        elif (x > a[mid]):
            l = mid + 1
    return -1

Câu hỏi

Câu 1: Nêu một vài ví dụ về bài toán tìm kiếm trong thực tế.

Lời giải:

• 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.
• Nhập số tuyến xe bus để tìm thông tin tuyến đường.
• Nhập số chứng minh nhân dân, căn cước công dân để tìm mã số thuế.

Câu 2: Với dãy đã sắp thứ tự và cho một số x cụ thể, trường hợp nào tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân? Về trung bình thuật toán tìm kiếm tuần tự hay thuật toán tìm kiếm nhị phân tốt hơn?

Lời giải:

• Tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân trong trường hợp x là số ở ngay đầu danh sách, tức là x ở vị trí k < log2n.
• Về trung bình, thuật toán tìm kiếm nhị phân tốt hơn thuật toán tìm kiếm tuần tự. Độ phức tạp thời gian thuật toán tìm kiếm tuần tự là O(n), trong khi độ phức tạp thời gian thuật toán tìm kiếm nhị phân là O(log2n).

Tìm kiếm thông minh đã trở thành công cụ hữu ích để giúp chúng ta giải quyết các vấn đề và tìm kiếm thông tin nhanh chóng và hiệu quả. Việc hiểu và áp dụng các thuật toán tìm kiếm sẽ giúp chúng ta trở thành người dùng thông minh và hiệu quả hơn trong việc sử dụng máy tính.

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập