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

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

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.

HOẠT ĐỘNG

Hoạt động: Em hãy thực hiện các yêu cầu sau:

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

2. Ướ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.

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

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:

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

2. 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 thứ tự theo bang chữ cái.

TỰ KIỂM TRA

Tự kiểm tra 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ế.

Tự kiểm tra 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?

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

KHỞI ĐỘNG

Đáp án KD: 

Bắt đầu tìm kiếm dữ liệu và tiến hành xử lí thông tin.

HOẠT ĐỘNG

Đáp án HD: 

Sau lần chia đôi đầu tiên, pham vi tìm kiếm còn n/2 số, sau khi chia đôi lần thứ hai, dãy còn n/4 số,… sau khi chia đôi lần k dãy còn n/2^k. Kết thúc khi 2^k ~ n.

VẬN DỤNG

Đáp án VD:

a) 

def tim_vi_tri_ten_hoc_sinh(danh_sach, ten_hoc_sinh):

          try:

              vi_tri = danh_sach.index(ten_hoc_sinh) + 1 # Trả về vị trí (bắt đầu từ 1)

              return f"Học sinh {ten_hoc_sinh} nằm ở vị trí thứ {vi_tri}."

          except ValueError:

              return f"Học sinh {ten_hoc_sinh} không có trong danh sách."

b) 

def tim_kiem_nhi_phan(danh_sach, ten_can_tim):

    left, right = 0, len(danh_sach) - 1

    while left <= right:

        mid = (left + right) // 2

        if danh_sach[mid] == ten_can_tim:

            return f"Chủ tài khoản {ten_can_tim} nằm ở vị trí thứ {mid + 1}."

        elif danh_sach[mid] < ten_can_tim:

            left = mid + 1

        else:

            right = mid - 1

    return f"Chủ tài khoản {ten_can_tim} không có trong danh sách."

TỰ KIỂM TRA

Đáp án TKT1:

• Tìm kiếm sản phẩm trong cơ sở dữ liệu của một trang thương mại điện tử.

• Tìm kiếm thông tin liên hệ của một người trong danh sách khách hàng của một doanh nghiệp.

Đáp án TKT2:

a) Ví dụ: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:

Các bước:

• Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5

• Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là vị trí số 3

• Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.

b) Tìm kiếm nhị phân nhanh hơn thuật toán tìm kiếm tuần tự vì sau mỗi bước lặp thì phạm vi tìm kiếm thu hẹp 1 nửa so với bước trước.