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

Chủ đề F^cs : Giải quyết vấn đề với sự trợ giúp của máy tính – Kĩ thuật lập trình – Bài 7. Lập trình giải bài toán tìm kiếm – sách giáo khoa trang 117 lớp 11 Khoa học máy tính – Cánh Diều, mời các em tham khảo cùng Bumbii.

Chủ đề F^cs : Giải quyết vấn đề với sự trợ giúp của máy tính – Bài 7. Lập trình giải bài toán tìm kiếm

KHỞI ĐỘNG

Khi tạo mới 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.

Lời giải:

Mô tả thành một bài toán:

• Dữ liệu đầu vào:
  1. Yêu cầu tạo mới một tài khoản người dùng.
  2. 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 được nhập 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

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.

Lời giải:

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

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

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: Độ phức tạp thời gian lô-ga-rit, O(log₂n).

Nhiệm vụ 2

Em hãy thực hiện các yêu cầu sau:

a) Viết chương trình Python thực hiện tìm kiếm tuần tự.

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

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

Lời giải:

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 so khong hop le!")
        return
    for i in range(lo, hi):
        if a[i] == x:
            return i
    return -1

NHIỆM VỤ 3

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.

Lời giải:

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

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

Lời giải:

a) Đề bài không nói rõ danh sách học sinh đã sắp xếp theo thứ tự hay chưa, do đó thực hiện tìm kiếm tuần tự:

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

b) Đề bài đã nói rõ danh sách đã sắp xếp theo thứ tự, do đó có thể áp dụng tìm kiếm nhị phân:

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. Em hãy nêu ra 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. Theo em, với dãy đã sắp thứ tự và cho một số x cụ thể:

a) Trường hợp nào tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân?

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

a) 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. Chính xác hơn là x ở vị trí k < log₂n.

b)

• Độ phức tạp thời gian thuật toán tìm kiếm tuần tự là O(n).
• Độ phức tạp thời gian thuật toán tìm kiếm nhị phân là O(log₂n).

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

Xem các bài giải khác: Giải Bài Tập Sách Giáo Khoa Tin Học Lớp 11 Khoa Học Máy Tính – Cánh Diều

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech

Tường Nguyễn