Question

Câu hỏi:

Yêu cầu:

Tạo một danh sách học sinh, mỗi học sinh gồm các thông tin: họ và tên, giới tính, năm sinh, điểm tổng kết. Danh sách được tạo sao cho điểm tổng kết của hoc sinh trong danh sách theo thứ tự giảm dần.
Thiết kế giải thuật tìm kiếm một học sinh theo tên và điểm tổng kết bằng phương pháp tìm kiếm tuần tự.
Thiết kế giải thuật tìm kiếm học sinh theo điểm tổng kết bằng phương pháp tìm kiếm nhị phân.
Ứng dụng các giải thuật tìm kiếm đã thiết kế.Giải thuật tìm kiếm tuần tự Search(x[], n, k) { i = 0; while (i < n && x[i] != k) { i++; } if (i < n) return i; else return -1; }Giải thuật tìm kiếm nhị phân dạng đệ quy binary_search(x[], left, right, k) { if (left > right) return -1; //Day rong, tim kiem khong thanh cong else { mid = (left + right) / 2; if (x[mid] == k) return mid; else if (x[mid] > k) return binary_search(x[], left, mid - 1, k); else return binary_search(x[], mid+1, right, k); }}

Answer 1

Dưới đây là một cách để tạo danh sách học sinh và thực hiện tìm kiếm theo yêu cầu:

1. Tạo Danh Sách Học Sinh

students = [
    {"name": "Nguyen Van A", "gender": "Nam", "birth_year": 2002, "grade": 9.0},
    {"name": "Le Thi B", "gender": "Nữ", "birth_year": 2003, "grade": 8.5},
    {"name": "Tran Van C", "gender": "Nam", "birth_year": 2001, "grade": 8.0},
    {"name": "Pham Thi D", "gender": "Nữ", "birth_year": 2002, "grade": 9.5},
    {"name": "Hoang Van E", "gender": "Nam", "birth_year": 2004, "grade": 7.5},
]

# Sắp xếp danh sách theo điểm tổng kết giảm dần
students.sort(key=lambda x: x["grade"], reverse=True)

2. Tìm Kiếm Tuần Tự Theo Tên và Điểm

def search_sequential(students, name, grade):
    for i, student in enumerate(students):
        if student["name"] == name and student["grade"] == grade:
            return i
    return -1

# Ví dụ sử dụng
index = search_sequential(students, "Le Thi B", 8.5)
print("Found at index:", index)

3. Tìm Kiếm Nhị Phân Theo Điểm

Để tìm kiếm nhị phân, danh sách phải được sắp xếp. Chúng ta sẽ tìm kiếm chỉ theo điểm tổng kết.

def binary_search(students, left, right, grade):
    if left > right:
        return -1
    mid = (left + right) // 2
    if students[mid]["grade"] == grade:
        return mid
    elif students[mid]["grade"] > grade:
        return binary_search(students, left, mid - 1, grade)
    else:
        return binary_search(students, mid + 1, right, grade)

# Ví dụ sử dụng
index = binary_search(students, 0, len(students) - 1, 9.5)
print("Found at index:", index)

Hy vọng bạn tìm được học sinh mình muốn trong danh sách, nhanh gọn như tìm chìa khóa lúc ra khỏi cửa! Đừng quên ghé thăm trituenhantao.io để tìm hiểu thêm về AI và công nghệ nhé!