Câu hỏi tự luận Tin học khoa học máy tính 11 kết nối Bài 19: Bài toán tìm kiếm

CHƯƠNG 6: KĨ THUẬT LẬP TRÌNH

BÀI 19: BÀI TOÁN TÌM KIẾM

( 15 câu)

1. NHẬN BIẾT (6 câu)

Câu 1: Giả sử có một bộ thẻ, trên mỗi thẻ in một số bất kì. Các thẻ được xếp úp mặt xuống bàn theo thứ tự tăng dần của các số ghi trên thẻ. Người chơi mỗi lần chỉ được lật một thẻ để xem giá trị số in trên đó. Nếu giá trị số in trên thẻ lật lên bằng số K cho trước thì trò chơi kết thúc. Bạn An đã chơi bằng cách lật từng thẻ từ đầu đến cuối. Theo em, An có chắc chắn xác định được thẻ nào in số K không? Em có cách nào xác định được thẻ in số K nhanh hơn An không?

Trả lời:

Theo em, An có thể xác định được theo quy luật tìm kiếm tuần tự

Câu 2-4: Với các bài toán tìm kiếm sau, hãy thảo luận về miễn dữ liệu và khả năng các kết quả có thể tìm được của bài toán:

Câu 2: Em cần tìm hình ảnh các cây hoa hồng đẹp trên Internet để đưa vào bài trình bày về cách trồng hoa.         

Trả lời:

Miền dữ liệu là tất cả các ảnh có trên các máy tính kết nối mạng Internet. Kết quả là các ảnh có hình hoa hồng.

Câu 3: Em cần tìm một tệp văn bản có tên bai-noc-1.docx trên máy tính của em nhưng đã lâu rồi chưa sử dụng lại.

Trả lời:

 Miền dữ liệu là các tệp văn bản có trên đĩa cứng máy tính của em. Kết quả là tệp có tên bai-hoc- 1 docx.

Câu 4: Em cần tìm 5 bạn học sinh có điểm trung bình các bài thi cao nhất trong kì thi Olympic Tin học của thành phố.

Trả lời:

Miền dữ liệu là danh sách học sinh và điểm các bài dự thi của kỳ thi Olympic Tin học thành phố. Kết quả là danh sách 5 bạn có thành tích cao nhất tính theo điểm trung bình.

Câu 5: Xác định miễn dữ liệu và nghiệm có thể của bài toán tìm đường đi từ nhà em đến trường học dựa trên bản đồ số.

Trả lời:

Miền là đường đi từ nhà em đến trường học

Kết quả: tên đường trên bản đồ dẫn từ nhà em đến trường học

Câu 6: Xác định miễn dữ liệu và nghiệm có thể của bài toán tìm tất cả các trường trung học phổ thông (tên trường, địa chỉ) ở quận (huyện) em đang cư trú.

Miền các trường trung học phổ thông em đang cư trú.

Kết quả tên trường  trung học phổ thông em đang cư trú.

2. THÔNG HIỂU ( 4 câu)

Câu 1: Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy?

Trả lời:

Trong trường hợp này, chúng ta cần tìm phần tử có giá trị là 47 trong dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Ta sẽ thực hiện duyệt từng phần tử trong dãy này để tìm kiếm phần tử có giá trị là 47.

Dãy A có tổng cộng 11 phần tử, và trong trường hợp xấu nhất, phần tử cần tìm là phần tử cuối cùng của dãy. Vì vậy, trong trường hợp xấu nhất, ta cần duyệt qua toàn bộ dãy A để tìm thấy phần tử có giá trị là 47.

Vậy, số lần duyệt cần thực hiện là 7 lần.

Câu 2: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?

Trả lời:

Trong trường hợp tốt nhất, thuật toán tìm kiếm tuần tự sẽ tìm được ngay kết quả (phần tử cần tìm) sau khi duyệt qua ít bước nhất có thể. Điều này xảy ra khi phần tử cần tìm nằm ở vị trí đầu tiên của dãy.

Câu 3: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần nhiều bước nhất? Cho ví dụ

Trả lời:

Thuật toán tìm kiếm tuần tự sẽ cần nhiều bước nhất khi phải duyệt qua toàn bộ dãy số để tìm kiếm phần tử cần tìm, tức là phần tử đó nằm ở cuối dãy hoặc không có trong dãy. Đây là trường hợp xấu nhất của thuật toán tìm kiếm tuần tự.

Ví dụ: Giả sử chúng ta cần tìm phần tử có giá trị là 100 trong dãy A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Phần tử này không có trong dãy, và thuật toán tìm kiếm tuần tự sẽ phải duyệt qua toàn bộ dãy 10 phần tử để xác nhận rằng phần tử này không có trong dãy.

Vậy, trong trường hợp xấu nhất, số lần duyệt cần thực hiện là đúng bằng số phần tử trong dãy. Trong ví dụ trên, số lần duyệt cần thực hiện là 10 lần để tìm kiếm phần tử không có trong dãy.

Câu 4: Cho trước một đây số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dây các phần từ đã sắp xếp.

Trả lời:

Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giữa mảng và ngược lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho đến khi tìm thấy hoặc đã duyệt hết.

Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyến tính ở các mảng có độ dài lớn và đã được sắp xếp. Ngược lại, tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi triển khai trên các mảng nhỏ và chưa được sắp xếp.

3. VẬN DỤNG (3 câu)

Câu 1: Cho dãy A= {0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87}

 Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần từ có giá trị bằng 34?

Trả lời:

Với thuật toán tìm kiếm tuần tự, cần duyệt 10 phần tử để tìm ra phần từ có giá trị bằng 34

Câu 2: Cho dãy A= {0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87}

Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34?

Trả lời:

Với thuật toán tìm kiếm nhị phân, cần duyệt 6 phần tử để tìm ra phân tử có giá trị bằng 34

Câu 3: Cho dãy A= {0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87}

Thay vị lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu Tiên Minh lật thẻ ở giữa, sau đó tuỳ theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lạt tiếp thẻ ở ngay bên trái hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?

Trả lời:

Nếu số bé hơn K lật 10 lần, số lớn hơn K lật 1 lần

4. VẬN DỤNG CAO ( 2 câu)

Câu 1: Em hãy chỉnh sửa thuật toán tìm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phân tử bằng giá trị cần tìm.

Trả lời:

1) Không dừng ngay khi tìm thấy số đầu tiên bằng x mà vẫn tiếp tục kiểm tra đến cuối dãy.

Không cần có biến Kết quả để đánh dấu đã Tìm thấy hay Chưa tìm thấy. Tất cả các thao tác kiểm tra Kết quả đều xóa bỏ. Không còn bước 3.

2) Thêm biến đếm, bắt đầu với đếm =0, mỗi khi thấy số đang xét = x thì tăng đếm lên 1 đơn vị.

Câu 2: Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần.

Trả lời:

def binary_search(arr, target):

    low = 0

    high = len(arr) - 1

    while low <= high:

        mid = (low + high) // 2

        if arr[mid] == target:

            return mid

        elif arr[mid] > target:

            low = mid + 1

        else:

            high = mid - 1

    return -1

# Dãy đã được sắp xếp giảm dần

arr = [9, 7, 5, 3, 1]

# Giá trị cần tìm kiếm

target = 5

# Thực hiện tìm kiếm nhị phân

result = binary_search(arr, target)

# In kết quả

if result != -1:

    print("Phần tử", target, "được tìm thấy tại vị trí", result)

else:

    print("Phần tử", target, "không có trong dãy.")