Bài 20. Thực hành bài toán tìm kiếm

Chủ đề 6. Kĩ thuật lập trình – Bài 20. Thực hành bài toán tìm kiếm – sách giáo khoa trang 94 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.

Chủ đề 6. Kĩ thuật lập trình – Bài 20. Thực hành bài toán tìm kiếm

Luyện tập

Chỉnh sửa lại chương trình của Nhiệm vụ 3 để cho phép chương trình có thể tìm kiếm điểm số trên danh sách điểm số được sắp xếp theo thứ tự giảm dần.

Lời giải:

def BinarySearch(A, K):
    left = 0
    right = len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == K:
            return mid
        elif A[mid] < K:
            left = mid + 1
        else:
            right = mid - 1
    return -1

input_file = open("diemthi_sx.inp")
ds_diem = []
for line in input_file.readlines():
    ds_diem.append(float(line))
input_file.close()

diem = float(input("Nhập điểm số cần kiểm tra: "))

vitri = BinarySearch(ds_diem, diem)

if vitri == -1:
    print("Không tồn tại điểm số cần tìm trong danh sách")
else:
    print("Điểm cần tìm nằm ở hàng thứ", vitri, "trong danh sách")

Vận dụng

Viết chương trình tra cứu tên theo điểm thi của học sinh trong lớp. Chương trình cho phép người dùng nhập vào khoảng điểm số cần tìm kiếm (ví dụ từ 6 đến 8). Chương trình kiểm tra và thông báo tên của học sinh có điểm số nằm trong khoảng tương ứng. Giải bài toán trong hai trường hợp: điểm được sắp xếp theo thứ tự ngẫu nhiên như trong Nhiệm vụ 1 hoặc điểm được sắp xếp theo thứ tự tăng dần như sau:

Sơn 5.6

Huyền 7.4

Nam 7.8

Hùng 8.4

Hương 8.9

Hà 9.5

Lời giải:

Trường hợp 1: Điểm sắp xếp ngẫu nhiên

Sử dụng vòng lặp for để kiểm tra từng phần tử trong danh sách.

# Danh sách tên học sinh
class_names = ["Sơn", "Huyền", "Nam", "Hùng", "Hương", "Hà"]

# Danh sách điểm thi tương ứng
class_scores = [5.6, 7.4, 7.8, 8.4, 8.9, 9.5]

# Nhập khoảng điểm cần tra cứu
start_score = float(input("Nhập điểm bắt đầu của khoảng điểm: "))
end_score = float(input("Nhập điểm kết thúc của khoảng điểm: "))

# Kiểm tra và thông báo tên học sinh có điểm nằm trong khoảng tương ứng
found = False
for i in range(len(class_names)):
        if class_scores[i] >= start_score and class_scores[i] <= end_score:
            print("Học sinh", class_names[i], "có điểm là", class_scores[i])
            found = True
if not found:
        print("Không tìm thấy học sinh nào có điểm trong khoảng điểm đã nhập.")

Trường hợp 2: Điểm sắp xếp tăng dần

Sử dụng tìm kiếm nhị phân để tra cứu.

# Danh sách tên học sinh
class_names = ["Sơn", "Huyền", "Nam", "Hùng", "Hương", "Hà"]

# Danh sách điểm thi tương ứng (đã được sắp xếp theo thứ tự tăng dần)
class_scores = [5.6, 7.4, 7.8, 8.4, 8.9, 9.5]

# Nhập khoảng điểm cần tra cứu
start_score = float(input("Nhập điểm bắt đầu của khoảng điểm: "))
end_score = float(input("Nhập điểm kết thúc của khoảng điểm: "))

# Tìm kiếm nhị phân để tra cứu tên học sinh
found = False
low = 0
high = len(class_names) - 1

while low <= high:
    mid = (low + high) // 2
    if class_scores[mid] >= start_score and class_scores[mid] <= end_score:
        print("Học sinh", class_names[mid], "có điểm là", class_scores[mid])
        found = True
    if class_scores[mid] < start_score:
        low = mid + 1
    else:
        high = mid - 1

if not found:
    print("Không tìm thấy học sinh nào có điểm trong khoảng điểm đã nhập.")

Hai trường hợp có kết quả giống nhau:

Nhập điểm bắt đầu của khoảng điểm: 6
Nhập điểm kết thúc của khoảng điểm: 8
Học sinh Nam có điểm là 7.8
Học sinh Huyền có điểm là 7.4

Xem các bài giải khác: Giải bài tập SGK lớp 11 định hướng Khoa học máy tính – NXB Kết nối tri thức với cuộc sống

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

Post Views: 162