Bài 7. Lập trình giải bài toán tìm kiếm trang 117, 118, 119 SGK Tin học 11 Khoa học máy tính Cánh diều

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.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

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 phải bắt đầu tìm kiếm dữ liệu và tiến hành xử lí thông tin ngay sau khi nhận.

HĐ

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.

Phương pháp giải:

 Dựa vào kiến thức đã học.

Lời giải chi tiết:

Thuật toán tìm kiếm nhị phân:

Cho một mảng đã sắp xếp arr[] có n phần tử, viết một hàm tìm kiếm trả về chỉ số của phần tử có giá trị x trong arr[]. Tức là, lập trình cho I đi qua từng phần tử của mảng để đối chiếu với x cần tìm.

NV1

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.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

1) Bắt đầu: Phạm vi tìm kiếm là dãy ban đầu

Lặp khi Vẫn còn Phạm vi tìm kiếm:

Xác định phần tử am giữa Phạm vi tìm kiếm

Nếu x=am:

Thông báo tìm thấy x ở vị trí m và kết thúc

Ngược lại:

Loại bỏ nửa dãy chắc chắn không chứa x

Phạm vi tìm kiếm là nửa dãy còn lại

Hết nhánh

Hết lặp

Thông báo không tìm thấy x và kết thúc.

2) Số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân:

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

3) Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân O(n).

NV2

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.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

a) Chương trình python thực hiện tìm kiếm tuần tự:

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

def search(arr, n, x):

    for i in range (0, n):

        if (arr[i] == x):

            return i;

    return -1;

arr = [ 2, 3, 4, 10, 40 ];

x = 10;

n = len(arr);

result = search(arr, n, x)

if(result == -1):

    print("Element is not present in array")

else:

    print("Element is present at index", result);

c) Chương trình tương tự ý a và b, kết quả tương đương với phương thức index của Python.

NV3

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.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

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.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

a) Danh sách học sinh của lớp em, gợi ý thuật toán:

Gán i = 0

Gán j = 0

Nếu A[j] > A[j + 1] thì đối chỗ A[j] và A[j + 1]

Nếu j < n – i – 1:

Đúng thì j = j + 1 và quay lại bước 3

Sai thì sang bước 5

Nếu i < n – 1:

Đúng thì i = i + 1 và quay lại bước 2

Sai thì dừng lại.

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:

CH1

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ế

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

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

- Tìm kiếm một file hoặc thư mục trong hệ thống tệp của máy tính.

- Tìm kiếm các bản ghi trong cơ sở dữ liệu y tế để tìm kiếm bệnh nhân cần điều trị.

- Tìm kiếm các bản ghi trong cơ sở dữ liệu của một trang tuyển dụng để tìm kiếm ứng viên phù hợp.

CH2

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ương pháp giải:

 Dựa vào kiến thức đã học.

Lời giải chi tiết:

a) Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp:

Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:

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

- 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) Thuật toán tìm kiếm nhị phân

- Thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp. Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

Thuật toán tuần tự

- Mô tả thuật toán phải cụ thể, rõ ràng, đầy đủ, đầu vào là gì, đầu ra là gì và chỉ rõ sự kết thúc thuật toán.

- Cần mô tả thuật toán cho tốt thì người máy hay máy tính mới hiểu đúng và thực hiện được.

- Nếu không, kết quả thực hiện thuật toán có thể không như mong đợi.