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

Bài thực hành này vận dụng hai mảng kiến thức đã học: ba thuật toán sắp xếp (Bài 21) và đọc/ghi tệp văn bản (Bài 20). Trước khi thực hành, cần nhớ lại các ý chính:

Ba thuật toán sắp xếp đã học:

Đổi từ tăng dần sang giảm dần: Chỉ cần đảo chiều điều kiện so sánh trong thuật toán (thay > thành < hoặc ngược lại).

Đọc dữ liệu từ tệp: Dùng open() mở tệp, readlines() hoặc for line in f để duyệt từng dòng, split() để tách dữ liệu, int() hoặc float() để chuyển kiểu. Đóng tệp bằng f.close().

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

Nhiệm vụ 1: Sắp xếp số lượng mặt hàng trong kho (sắp xếp chèn – tăng dần)

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

Cho danh sách số lượng mỗi mặt hàng trong kho của một cửa hàng, được lưu trong tệp kho.inp (mỗi dòng chứa số lượng một mặt hàng). Viết chương trình đọc dữ liệu từ tệp, sắp xếp theo thứ tự tăng dần bằng thuật toán sắp xếp chèn, sau đó in kết quả ra màn hình.

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

5
3
10
4
8
2

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

Bài toán gồm ba bước rõ ràng:

• Bước 1 – Đọc dữ liệu: Mở tệp kho.inp, duyệt từng dòng, chuyển mỗi dòng thành số nguyên rồi thêm vào danh sách soluong_ds.
• Bước 2 – Sắp xếp: Gọi hàm InsertionSort(soluong_ds) để sắp xếp tăng dần.
• Bước 3 – In kết quả: Duyệt danh sách đã sắp xếp và in ra từng phần tử.

Đây là bài toán đơn giản vì mỗi dòng tệp chỉ chứa một giá trị duy nhất (số lượng), không cần tách bằng split().

Chương trình mẫu

# quanlykho.py – Sắp xếp số lượng mặt hàng bằng sắp xếp chèn

def InsertionSort(A):
    n = len(A)
    for i in range(1, n):
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = value

input_file = open("kho.inp", encoding="UTF-8")
soluong_ds = []
for line in input_file.readlines():
    soluong_ds.append(int(line))
input_file.close()

InsertionSort(soluong_ds)

print("Số lượng các mặt hàng trong kho theo thứ tự tăng dần là:")
for i in range(len(soluong_ds)):
    print(soluong_ds[i])

Giải thích chi tiết

Hàm InsertionSort (dòng 1–9):

Đây chính là thuật toán sắp xếp chèn đã học ở Bài 21, giữ nguyên logic: vòng for duyệt i từ 1 đến n−1. Tại mỗi bước, lưu A[i] vào value, dịch các phần tử bên trái lớn hơn value sang phải, cuối cùng đặt value vào ô trống.

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

Mở tệp kho.inp với encoding="UTF-8". 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, mỗi dòng chỉ chứa một số (ví dụ '5\n'), lệnh int(line) tự động bỏ kí tự xuống dòng \n và chuyển thành số nguyên. Sau khi đọc xong, đóng tệp.

Kết quả sau khi đọc:

soluong_ds = [5, 3, 10, 4, 8, 2]

Phần sắp xếp và in (dòng 17–20):

Gọi InsertionSort(soluong_ds) → dãy được sắp xếp tại chỗ thành [2, 3, 4, 5, 8, 10]. Vòng for cuối in từng phần tử trên một dòng.

Kết quả khi chạy:

Số lượng các mặt hàng trong kho theo thứ tự tăng dần là:
2
3
4
5
8
10

Nhiệm vụ 2: Sắp xếp điểm trung bình giảm dần (sắp xếp chọn)

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

Cho danh sách điểm trung bình môn Tin học của các học sinh, lưu trong tệp diem.inp (mỗi dòng chứa điểm trung bình một học sinh). Viết chương trình đọc dữ liệu, sắp xếp theo thứ tự giảm dần bằng thuật toán sắp xếp chọn, rồi in kết quả.

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

7.8
5.6
8.9
7.4
9.5
8.4
9.1

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

Bài toán tương tự Nhiệm vụ 1, nhưng có hai điểm khác biệt quan trọng:

• Dữ liệu là số thực (điểm trung bình) → dùng float(line) thay vì int(line).
• Sắp xếp giảm dần → trong thuật toán sắp xếp chọn, thay vì tìm phần tử nhỏ nhất ta tìm phần tử lớn nhất. Cụ thể: đổi biến iMin thành iMax, đổi điều kiện A[j] < A[iMin] thành A[j] > A[iMax].

Chương trình mẫu

# sapxepdiem.py – Sắp xếp điểm giảm dần bằng sắp xếp chọn

def SelectionSort(A):
    n = len(A)
    for i in range(n - 1):
        iMax = i
        for j in range(i + 1, n):
            if A[j] > A[iMax]:
                iMax = j
        A[i], A[iMax] = A[iMax], A[i]

input_file = open("diem.inp", encoding="UTF-8")
diem_ds = []
for line in input_file.readlines():
    diem_ds.append(float(line))
input_file.close()

SelectionSort(diem_ds)

print("Danh sách điểm theo thứ tự giảm dần là:")
for i in range(len(diem_ds)):
    print(diem_ds[i])

Giải thích chi tiết

Hàm SelectionSort – phiên bản giảm dần (dòng 1–9):

So với bản tăng dần ở Bài 21, hàm có hai thay đổi:

• Biến iMin → iMax: mục đích giờ là tìm phần tử lớn nhất trong đoạn chưa sắp xếp.
• Điều kiện A[j] < A[iMin] → A[j] > A[iMax]: kiểm tra phần tử nào lớn hơn giá trị lớn nhất hiện tại.

Kết quả: mỗi vòng lặp đưa phần tử lớn nhất còn lại về vị trí i, nên dãy được sắp xếp từ lớn đến nhỏ.

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

Tương tự Nhiệm vụ 1, nhưng dùng float(line) vì điểm số là số thực.

Kết quả sau khi đọc:

diem_ds = [7.8, 5.6, 8.9, 7.4, 9.5, 8.4, 9.1]

Kết quả khi chạy:

Danh sách điểm theo thứ tự giảm dần là:
9.5
9.1
8.9
8.4
7.8
7.4
5.6

So sánh hai nhiệm vụ

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

Sử dụng thuật toán sắp xếp chọn viết lại chương trình trong Nhiệm vụ 1 (sắp xếp số lượng mặt hàng tăng dần).

Lời giải:

# quanlykho_chon.py – Sắp xếp kho hàng bằng sắp xếp chọn (tăng dần)

def SelectionSort(A):
    n = len(A)
    for i in range(n - 1):
        iMin = i
        for j in range(i + 1, n):
            if A[j] < A[iMin]:
                iMin = j
        A[i], A[iMin] = A[iMin], A[i]

input_file = open("kho.inp", encoding="UTF-8")
soluong_ds = []
for line in input_file.readlines():
    soluong_ds.append(int(line))
input_file.close()

SelectionSort(soluong_ds)

print("Số lượng các mặt hàng trong kho theo thứ tự tăng dần là:")
for i in range(len(soluong_ds)):
    print(soluong_ds[i])

Giải thích: Phần đọc tệp và in kết quả giữ nguyên so với Nhiệm vụ 1. Chỉ thay hàm InsertionSort bằng SelectionSort phiên bản tăng dần (dùng iMin và điều kiện A[j] < A[iMin]). Kết quả ra hoàn toàn giống nhau vì chỉ thay thuật toán, không thay dữ liệu hay yêu cầu.

Bài 2 (Luyện tập SGK)

Sử dụng thuật toán sắp xếp nổi bọt viết lại chương trình trong Nhiệm vụ 2 (sắp xếp điểm giảm dần).

Lời giải:

# sapxepdiem_noibot.py – Sắp xếp điểm giảm dần bằng sắp xếp nổi bọt

def BubbleSort(A):
    n = len(A)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if A[j] < A[j + 1]:           # Đổi > thành < để giảm dần
                A[j], A[j + 1] = A[j + 1], A[j]

input_file = open("diem.inp", encoding="UTF-8")
diem_ds = []
for line in input_file.readlines():
    diem_ds.append(float(line))
input_file.close()

BubbleSort(diem_ds)

print("Danh sách điểm theo thứ tự giảm dần là:")
for i in range(len(diem_ds)):
    print(diem_ds[i])

Giải thích: Hàm BubbleSort phiên bản giảm dần: điều kiện đổi chỗ là A[j] < A[j+1] (nếu phần tử bên trái nhỏ hơn phần tử bên phải thì đổi chỗ). Như vậy, phần tử nhỏ nhất sẽ “chìm” về cuối dãy sau mỗi vòng, và dãy được sắp xếp giảm dần. Phần đọc tệp giữ nguyên so với Nhiệm vụ 2.

Bài Vận dụng

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

Một người đi mua hàng với danh sách các mặt hàng cần mua, đơn giá từng mặt hàng và số lượng hàng cần mua được lưu trong tệp văn bản muahang.inp.

Hãy sử dụng thuật toán nổi bọt để sắp xếp các mặt hàng theo thứ tự thành tiền của các mặt hàng tăng dần rồi in ra tên các mặt hàng và thành tiền tương ứng.

Lời giải:

Trước tiên, ta cần xác định cấu trúc tệp muahang.inp. Giả sử mỗi dòng gồm ba thông tin cách nhau bởi dấu cách: tên mặt hàng, đơn giá và số lượng.

Gao 15000 10
Duong 25000 5
Muoi 8000 3
Sua 35000 2
Trung 4000 30

Chương trình:

# muahang.py – Sắp xếp mặt hàng theo thành tiền tăng dần

def BubbleSort(ten, thanh_tien):
    """Sắp xếp nổi bọt theo thành tiền tăng dần,
       đồng thời đổi chỗ tên tương ứng"""
    n = len(thanh_tien)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if thanh_tien[j] > thanh_tien[j + 1]:
                # Đổi chỗ thành tiền
                thanh_tien[j], thanh_tien[j + 1] = thanh_tien[j + 1], thanh_tien[j]
                # Đổi chỗ tên tương ứng
                ten[j], ten[j + 1] = ten[j + 1], ten[j]

# Đọc dữ liệu từ tệp
input_file = open("muahang.inp", encoding="UTF-8")
ten_list = []
thanhtien_list = []

for line in input_file.readlines():
    parts = line.split()
    ten_mh = parts[0]
    don_gia = int(parts[1])
    so_luong = int(parts[2])
    ten_list.append(ten_mh)
    thanhtien_list.append(don_gia * so_luong)
input_file.close()

# Sắp xếp theo thành tiền tăng dần
BubbleSort(ten_list, thanhtien_list)

# In kết quả
print("Danh sách mặt hàng theo thành tiền tăng dần:")
for i in range(len(ten_list)):
    print(f"  {ten_list[i]}: {thanhtien_list[i]} đồng")

Kết quả khi chạy (với dữ liệu mẫu):

Danh sách mặt hàng theo thành tiền tăng dần:
  Muoi: 24000 đồng
  Sua: 70000 đồng
  Trung: 120000 đồng
  Duong: 125000 đồng
  Gao: 150000 đồng

Giải thích chi tiết:

Phần đọc tệp (dòng 16–25): Mỗi dòng được tách thành 3 phần bằng split(): tên mặt hàng (parts[0]), đơn giá (parts[1]), số lượng (parts[2]). Thành tiền = đơn giá × số lượng, được tính ngay khi đọc và lưu vào thanhtien_list. Tên mặt hàng lưu vào ten_list.

Hàm BubbleSort có hai mảng (dòng 1–13): Đây là điểm quan trọng nhất của bài. Ta cần sắp xếp theo thanh_tien, nhưng khi đổi chỗ hai phần tử trong thanh_tien thì đồng thời phải đổi chỗ hai phần tử tương ứng trong ten. Nếu không, sau khi sắp xếp, tên mặt hàng sẽ không còn khớp với thành tiền. Đây là kỹ thuật sắp xếp song song hai mảng – khi đổi chỗ ở mảng này thì cũng đổi chỗ tại cùng vị trí ở mảng kia.

Minh hoạ quá trình: Khi thanh_tien[j] và thanh_tien[j+1] bị đổi chỗ, thì ten[j] và ten[j+1] cũng đổi chỗ theo → đảm bảo tên luôn đi kèm đúng số tiền.

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