I. Ôn tập kiến thức nền

Bài thực hành này kết hợp hai mảng kiến thức: thuật toán tìm kiếm (đã học ở Bài 19) và đọc/ghi tệp văn bản (kiến thức mới bổ sung trong bài). Trước khi bắt tay vào thực hành, cần nhớ lại các ý chính:

Tìm kiếm tuần tự: Duyệt lần lượt từng phần tử từ đầu đến cuối, so sánh với giá trị cần tìm. Áp dụng cho mọi dãy (không cần sắp xếp).

Tìm kiếm nhị phân: Liên tục chia đôi phạm vi tìm kiếm dựa vào so sánh với phần tử giữa. Chỉ áp dụng khi dãy đã được sắp xếp. Nhanh hơn rất nhiều so với tìm kiếm tuần tự.

Vấn đề thực tế: Trong các bài toán trước, dữ liệu được gõ trực tiếp vào chương trình hoặc nhập từ bàn phím. Tuy nhiên, thực tế dữ liệu thường được lưu sẵn trong các tệp văn bản trên máy tính. Vì vậy, bài thực hành này sẽ hướng dẫn cách đọc dữ liệu từ tệp, xử lí rồi ghi kết quả ra tệp.

II. Kiến thức mới: Đọc và ghi tệp trong Python

1. Mở và đóng tệp

Python làm việc với tệp văn bản thông qua hàm open(). Hàm này tạo ra một đối tượng tệp (file object) dùng để đọc hoặc ghi dữ liệu.

Cú pháp mở tệp:

Tham số encoding="UTF-8" cần thiết khi tệp chứa tiếng Việt hoặc các kí tự Unicode. Nếu tệp chỉ chứa kí tự ASCII (chữ cái tiếng Anh, số,…) thì có thể bỏ qua tham số này.

Đóng tệp: Sau khi hoàn tất đọc/ghi, bắt buộc đóng tệp bằng lệnh:

f.close()

Việc đóng tệp giúp giải phóng tài nguyên và đảm bảo dữ liệu được ghi hoàn chỉnh vào tệp.

2. Các lệnh đọc dữ liệu từ tệp

Dữ liệu trong tệp văn bản được tổ chức thành các dòng, mỗi dòng là một xâu kí tự. Sau khi mở tệp, con trỏ đọc mặc định ở đầu tệp, sẵn sàng cho lệnh đọc.

Giả sử tệp Data.inp có nội dung:

Hà 9.6
Bình 8.5
Quang 7.2

Các cách đọc dữ liệu từ đối tượng tệp f:

Lưu ý: Kí tự \n ở cuối mỗi dòng là kí tự xuống dòng. Khi xử lí dữ liệu, ta thường dùng split() để tách dòng thành các phần – phương thức này tự động bỏ qua \n.

3. Ví dụ đọc dữ liệu vào hai mảng riêng biệt

Với tệp Data.inp ở trên, chương trình sau đọc dữ liệu rồi tách thành hai mảng: một mảng chứa tên, một mảng chứa điểm.

fname = "Data.inp"

def NhapDL(fname):
    f = open(fname, encoding="UTF-8")
    TenHS = []
    DiemHS = []
    for line in f:
        L = line.split()
        TenHS.append(L[0])
        DiemHS.append(float(L[1]))
    f.close()
    return TenHS, DiemHS

TenHS, DiemHS = NhapDL(fname)
for i in range(len(TenHS)):
    print(TenHS[i], DiemHS[i])

Giải thích từng phần:

Hàm NhapDL mở tệp, khởi tạo hai danh sách rỗng TenHS và DiemHS. Vòng for line in f duyệt từng dòng của tệp. Với mỗi dòng (ví dụ 'Hà 9.6\n'), lệnh line.split() tách thành danh sách ['Hà', '9.6']. Phần tử đầu L[0] là tên (xâu), phần tử sau L[1] được chuyển sang số thực bằng float() rồi thêm vào mảng tương ứng. Sau khi đọc xong, đóng tệp và trả về hai mảng.

Kết quả khi chạy:

Hà 9.6
Bình 8.5
Quang 7.2

4. Ghi dữ liệu ra tệp văn bản

Cách đơn giản nhất để ghi dữ liệu ra tệp là dùng lệnh print() kết hợp tham số file:

print(<giá_trị_1>, <giá_trị_2>, ..., file = <đối_tượng_tệp>)

Tham số file = ... là điểm khác biệt so với print() thông thường – thay vì in ra màn hình, dữ liệu được ghi vào tệp. Tất cả các tham số khác của print() (như end, sep) vẫn hoạt động bình thường.

Ví dụ: Ghi danh sách tên và điểm ra tệp Data.out:

fname = "Data.out"
TenHS = ['Hà', 'Bình', 'Quang']
DiemHS = [9.6, 8.5, 7.2]

f = open(fname, "w", encoding="UTF-8")
for i in range(len(TenHS)):
    print(TenHS[i], DiemHS[i], file=f)
f.close()

Sau khi chạy, tệp Data.out sẽ có nội dung:

Hà 9.6
Bình 8.5
Quang 7.2

III. Hướng dẫn thực hành

Nhiệm vụ 2: Tra cứu điểm thi theo tên học sinh

Yêu cầu bài toán

Viết chương trình cho phép người dùng nhập tên học sinh cần tra cứu, chương trình đọc dữ liệu từ tệp diem.inp rồi tìm kiếm và thông báo điểm số tương ứng. Nếu không tìm thấy, thông báo “không tìm thấy”.

Cấu trúc tệp diem.inp: mỗi hàng gồm tên học sinh và điểm cách nhau bởi dấu cách.

Nam 7.8
Sơn 5.6
Hương 8.9
Huyền 7.4
Hà 9.5
Hùng 8.4

Phân tích hướng giải quyết

Bài toán này gồm hai giai đoạn rõ ràng:

• Giai đoạn 1 – Đọc dữ liệu: Mở tệp, duyệt từng dòng, tách tên và điểm vào hai mảng song song ten_list và diem_list. Hai mảng này có cùng số phần tử và tương ứng theo chỉ số (tên ở vị trí i → điểm ở vị trí i).
• Giai đoạn 2 – Tra cứu: Người dùng nhập tên cần tìm. Dùng tìm kiếm tuần tự trên ten_list để tìm chỉ số. Nếu tìm thấy tại vị trí i, lấy diem_list[i] ra in kết quả. Dùng tìm kiếm tuần tự ở đây vì danh sách tên chưa được sắp xếp.
• Chương trình cho phép tra cứu nhiều lần liên tiếp, nhập từ khoá end để kết thúc.

Chương trình mẫu

# Tracuuten.py – Tra cứu điểm theo tên

input_file = open("diem.inp", encoding="UTF-8")
ten_list = []
diem_list = []

for line in input_file.readlines():
    ten, diem = line.split()
    ten_list.append(ten)
    diem_list.append(float(diem))
input_file.close()

ten = ""
while ten != "end":
    ten = input("Nhập tên học sinh cần tra cứu (nhập 'end' để kết thúc): ")
    if ten != "end":
        vitri = -1
        for i in range(len(ten_list)):
            if ten == ten_list[i]:
                vitri = i
        if vitri == -1:
            print("Không tìm thấy học sinh trong danh sách")
        else:
            print("Điểm số của học sinh là:", diem_list[vitri])

Giải thích chi tiết

Phần đọc tệp (dòng 1–7):

Mở tệp diem.inp với encoding="UTF-8" để đọc được tiếng Việt. Phương thức readlines() trả về danh sách tất cả các dòng. Vòng for duyệt từng dòng, lệnh line.split() tách mỗi dòng (ví dụ 'Nam 7.8\n') thành hai phần – ten nhận giá trị 'Nam', diem nhận giá trị '7.8'. Sau đó thêm tên vào ten_list và điểm (đã chuyển sang float) vào diem_list.

Kết quả sau khi đọc:

ten_list  = ['Nam', 'Sơn', 'Hương', 'Huyền', 'Hà', 'Hùng']
diem_list = [7.8,   5.6,   8.9,     7.4,     9.5,  8.4]

Phần tra cứu (dòng 9–18):

Vòng while cho phép tra cứu nhiều lần. Với mỗi tên nhập vào, biến vitri khởi tạo bằng −1 (giả sử chưa tìm thấy). Vòng for duyệt toàn bộ ten_list, nếu tìm thấy tên trùng khớp thì gán vitri = i. Sau khi duyệt xong, kiểm tra vitri: nếu vẫn bằng −1 thì không tìm thấy; ngược lại, in diem_list[vitri].

Lưu ý: Cách cài đặt ở đây duyệt hết dãy ngay cả khi đã tìm thấy – điều này giúp luôn lấy được vị trí cuối cùng nếu có nhiều học sinh trùng tên. Nếu muốn dừng ngay khi tìm thấy lần đầu, có thể thêm break sau vitri = i.

Nhiệm vụ 3: Kiểm tra điểm thi bằng tìm kiếm nhị phân

Yêu cầu bài toán

Viết chương trình đọc dữ liệu điểm thi từ tệp diemthi_sx.inp (mỗi dòng chứa một điểm số, các điểm đã được sắp xếp tăng dần). Cho phép người dùng nhập một điểm số cần kiểm tra, chương trình tìm và thông báo vị trí của điểm đó trong danh sách, hoặc thông báo không tồn tại.

Cấu trúc tệp diemthi_sx.inp:

5.6
5.8
6.8
7.4
7.5
7.9

Phân tích hướng giải quyết

Điểm khác biệt quan trọng so với Nhiệm vụ 2: dữ liệu điểm đã được sắp xếp tăng dần. Đây là điều kiện lí tưởng để áp dụng tìm kiếm nhị phân, giúp tìm kiếm nhanh hơn nhiều so với duyệt tuần tự.

Luồng xử lí:

• Bước 1: Đọc tệp, mỗi dòng chứa một số thực → chuyển đổi rồi thêm vào mảng ds_diem.
• Bước 2: Nhập điểm cần kiểm tra từ bàn phím.
• Bước 3: Gọi hàm BinarySearch(ds_diem, diem) để tìm vị trí. Trả về chỉ số nếu tìm thấy, trả về −1 nếu không.

Chương trình mẫu

# Kiemtradiem_sx.py – Kiểm tra điểm bằng tìm kiếm nhị phân

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

# Đọc dữ liệu từ tệp
input_file = open("diemthi_sx.inp")
ds_diem = []
for line in input_file.readlines():
    ds_diem.append(float(line))
input_file.close()

# Nhập và kiểm tra
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 + 1, "trong danh sách")

Giải thích chi tiết

Hàm BinarySearch (dòng 1–12):

Đây là hàm tìm kiếm nhị phân đã học ở Bài 19, giữ nguyên logic: xác định phạm vi left–right, tính mid, so sánh A[mid] với K rồi thu hẹp phạm vi. Kết thúc khi tìm thấy (trả về mid) hoặc phạm vi rỗng (trả về −1).

Phần đọc tệp (dòng 14–18):

Khác với Nhiệm vụ 2, ở đây mỗi dòng chỉ chứa một giá trị (điểm số), nên không cần split() – chỉ cần float(line) để chuyển thẳng dòng đọc được thành số thực. Không cần encoding="UTF-8" vì tệp chỉ chứa số (kí tự ASCII).

Kết quả sau khi đọc:

ds_diem = [5.6, 5.8, 6.8, 7.4, 7.5, 7.9]

Dãy đã sắp xếp tăng dần → đủ điều kiện áp dụng tìm kiếm nhị phân.

Phần kiểm tra (dòng 20–25):

Nhập điểm từ bàn phím, gọi BinarySearch() rồi in kết quả. Lưu ý vitri + 1 vì chỉ số mảng bắt đầu từ 0 nhưng “hàng thứ” trong tệp tính từ 1.

So sánh với Nhiệm vụ 2

IV. Phương pháp giải bài tập SGK

Bài Luyện tập

Bài 1 (Luyện tập SGK). 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:

# Kiemtradiem_giam.py – Tìm kiếm nhị phân trên dãy giảm dần

def BinarySearchDesc(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:        # Dãy giảm: A[mid] lớn hơn K → tìm bên phải
            left = mid + 1
        else:                    # A[mid] nhỏ hơn K → tìm bên trái
            right = mid - 1
    return -1

# Đọc dữ liệu từ tệp (giả sử tệp diemthi_giam.inp chứa điểm giảm dần)
input_file = open("diemthi_giam.inp")
ds_diem = []
for line in input_file.readlines():
    ds_diem.append(float(line))
input_file.close()

# Nhập và kiểm tra
diem = float(input("Nhập điểm số cần kiểm tra: "))
vitri = BinarySearchDesc(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 + 1, "trong danh sách")

Giải thích: So với chương trình gốc, chỉ cần thay đổi logic so sánh trong hàm tìm kiếm nhị phân. Trong dãy giảm dần, phần tử bên trái lớn hơn, bên phải nhỏ hơn. Vì vậy khi A[mid] > K, giá trị K phải nằm ở phía bên phải (phần chứa các giá trị nhỏ hơn) → cập nhật left = mid + 1. Khi A[mid] < K, giá trị K nằm bên trái → cập nhật right = mid - 1.

Bài Vận dụng

Bài 1 (Vận dụng SGK).

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: Dữ liệu chưa sắp xếp (dùng tìm kiếm tuần tự)

# tracuu_khoang_diem.py – Tìm kiếm tuần tự theo khoảng điểm

# Đọc dữ liệu từ tệp (thứ tự ngẫu nhiên)
input_file = open("diem.inp", encoding="UTF-8")
ten_list = []
diem_list = []
for line in input_file.readlines():
    ten, diem = line.split()
    ten_list.append(ten)
    diem_list.append(float(diem))
input_file.close()

# Nhập khoảng điểm
diem_min = float(input("Nhập điểm thấp nhất của khoảng: "))
diem_max = float(input("Nhập điểm cao nhất của khoảng: "))

# Tìm kiếm tuần tự
ket_qua = []
for i in range(len(diem_list)):
    if diem_min <= diem_list[i] <= diem_max:
        ket_qua.append(ten_list[i])

# In kết quả
if len(ket_qua) == 0:
    print(f"Không có học sinh nào có điểm từ {diem_min} đến {diem_max}")
else:
    print(f"Các học sinh có điểm từ {diem_min} đến {diem_max}:")
    for ten in ket_qua:
        print(" ", ten)

Giải thích: Vì dữ liệu chưa sắp xếp, ta phải duyệt toàn bộ danh sách. Với mỗi phần tử diem_list[i], kiểm tra xem nó có nằm trong khoảng [diem_min, diem_max] hay không. Nếu có, thêm tên tương ứng ten_list[i] vào danh sách kết quả.

Lời giải – Trường hợp 2: Dữ liệu đã sắp xếp tăng dần theo điểm (dùng tìm kiếm nhị phân)

# tracuu_khoang_diem_sx.py – Tìm kiếm nhị phân theo khoảng điểm

# Đọc dữ liệu từ tệp (đã sắp xếp tăng dần theo điểm)
input_file = open("diem_sx.inp", encoding="UTF-8")
ten_list = []
diem_list = []
for line in input_file.readlines():
    ten, diem = line.split()
    ten_list.append(ten)
    diem_list.append(float(diem))
input_file.close()

def TimViTriDau(A, gia_tri):
    """Tìm vị trí đầu tiên có A[i] >= gia_tri bằng nhị phân"""
    left = 0
    right = len(A) - 1
    ket_qua = len(A)  # mặc định là ngoài phạm vi (không tìm thấy)
    while left <= right:
        mid = (left + right) // 2
        if A[mid] >= gia_tri:
            ket_qua = mid
            right = mid - 1
        else:
            left = mid + 1
    return ket_qua

def TimViTriCuoi(A, gia_tri):
    """Tìm vị trí cuối cùng có A[i] <= gia_tri bằng nhị phân"""
    left = 0
    right = len(A) - 1
    ket_qua = -1  # mặc định là không tìm thấy
    while left <= right:
        mid = (left + right) // 2
        if A[mid] <= gia_tri:
            ket_qua = mid
            left = mid + 1
        else:
            right = mid - 1
    return ket_qua

# Nhập khoảng điểm
diem_min = float(input("Nhập điểm thấp nhất của khoảng: "))
diem_max = float(input("Nhập điểm cao nhất của khoảng: "))

# Tìm biên trái và biên phải của khoảng điểm trong dãy
vi_tri_dau = TimViTriDau(diem_list, diem_min)
vi_tri_cuoi = TimViTriCuoi(diem_list, diem_max)

# In kết quả
if vi_tri_dau > vi_tri_cuoi:
    print(f"Không có học sinh nào có điểm từ {diem_min} đến {diem_max}")
else:
    print(f"Các học sinh có điểm từ {diem_min} đến {diem_max}:")
    for i in range(vi_tri_dau, vi_tri_cuoi + 1):
        print(f"  {ten_list[i]} – {diem_list[i]}")

Giải thích: Vì dãy điểm đã sắp xếp tăng dần, tất cả các điểm nằm trong khoảng [diem_min, diem_max] sẽ liền kề nhau trong dãy. Ta chỉ cần tìm hai biên:

• TimViTriDau: dùng nhị phân tìm vị trí đầu tiên có điểm ≥ diem_min (biên trái).
• TimViTriCuoi: dùng nhị phân tìm vị trí cuối cùng có điểm ≤ diem_max (biên phải).

Sau đó in tất cả học sinh từ vị trí biên trái đến biên phải. Cách này nhanh hơn nhiều so với duyệt tuần tự trên danh sách lớn, vì chỉ cần 2 lần tìm kiếm nhị phân thay vì duyệt hết dãy.

Thầy Phạm Thành Danh

(Người kiểm duyệt, ra đề)

Chức vụ: Trưởng ban biên soạn môn Tin Học THPT

Trình độ: Cử nhân Sư phạm Tin học, Chứng chỉ hạng II, Chứng chỉ Tin học, Ngoại ngữ B1

Kinh nghiệm: 8+ năm kinh nghiệm tại Trường THPT Thuận Hóa