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

Bài thực hành này vận dụng phương pháp làm mịn dần đã học ở Bài 26 để thiết kế chương trình giải hai bài toán mới. Trước khi thực hành, cần nhớ lại quy trình chung:

Ngoài ra, bài thực hành cũng sử dụng lại các thuật toán sắp xếp đã học (Bài 21) như một công cụ hỗ trợ trong quá trình giải bài toán.

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

Nhiệm vụ 1: Kiểm tra hoán vị

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

Cho dãy gồm n số: A[0], A[1], …, A[n−1]. Kiểm tra xem dãy A có phải là một hoán vị của dãy 1, 2, …, n hay không. Thông báo “CÓ” hoặc “KHÔNG”.

Nhắc lại: Dãy A là hoán vị của 1, 2, …, n nghĩa là A chứa đúng các giá trị từ 1 đến n, mỗi giá trị xuất hiện đúng một lần (thứ tự bất kỳ).

Ví dụ: A = [3, 1, 2] → CÓ (hoán vị của 1, 2, 3). A = [2, 1, 9, 10, 8, 6, 5, 2, 3, 1] → KHÔNG (có phần tử trùng, thiếu một số giá trị).

Thiết kế theo phương pháp làm mịn dần

a) Tìm hiểu bài toán

• Đầu vào: Dãy số A gồm n phần tử.
• Đầu ra: “CÓ” nếu A là hoán vị của [1, 2, …, n], “KHÔNG” nếu ngược lại.

b) Thiết kế làm mịn dần

Bước 1 – Ý tưởng tổng quan:

Một cách đơn giản để kiểm tra: sắp xếp dãy A theo thứ tự tăng dần, rồi so sánh dãy đã sắp với dãy [1, 2, …, n]. Nếu hai dãy giống hệt nhau → A là hoán vị.

1. Sắp xếp dãy A theo thứ tự tăng dần.
2. Kiểm tra A có phải là dãy 1, 2, ..., n hay không.

Hai thao tác này vẫn ở dạng mô tả → cần làm mịn tiếp.

Bước 2 – Cụ thể hoá “sắp xếp dãy A”:

Sử dụng một trong các thuật toán sắp xếp đã học. Ở đây dùng sắp xếp chèn (phiên bản đổi chỗ đã chứng minh ở Bài 26), viết thành hàm sapxep(A):

def sapxep(A):
    for i in range(len(A)):
        j = i
        while j > 0 and A[j] < A[j - 1]:
            A[j], A[j - 1] = A[j - 1], A[j]
            j = j - 1

Bước này đã hoàn toàn là câu lệnh Python.

Bước 3 – Cụ thể hoá “kiểm tra A có phải dãy [1, 2, …, n]”:

Sau khi sắp xếp, nếu A là hoán vị thì A sẽ trở thành [1, 2, …, n]. Ta chỉ cần duyệt từng phần tử: A[0] phải bằng 1, A[1] phải bằng 2, …, tổng quát A[i] phải bằng i + 1. Nếu tìm thấy bất kỳ phần tử nào không thoả thì kết luận không phải hoán vị.

sapxep(A)
kq = True
for i in range(len(A)):
    if A[i] != i + 1:
        kq = False
        break
return kq

Toàn bộ bước này được gói thành hàm kt_hoanvi(A):

def kt_hoanvi(A):
    sapxep(A)
    kq = True
    for i in range(len(A)):
        if A[i] != i + 1:
            kq = False
            break
    return kq

Đến đây, tất cả thao tác đã được viết thành code → thiết kế hoàn tất.

Chương trình hoàn chỉnh

def sapxep(A):
    for i in range(len(A)):
        j = i
        while j > 0 and A[j] < A[j - 1]:
            A[j], A[j - 1] = A[j - 1], A[j]
            j = j - 1

def kt_hoanvi(A):
    sapxep(A)
    kq = True
    for i in range(len(A)):
        if A[i] != i + 1:
            kq = False
            break
    return kq

# Chương trình chính
A = [2, 1, 9, 10, 8, 6, 5, 2, 3, 1]
if kt_hoanvi(A):
    print("CÓ")
else:
    print("KHÔNG")

Giải thích chi tiết

Hàm sapxep(A): Đây là thuật toán sắp xếp chèn phiên bản đổi chỗ. Thay vì “nhấc” phần tử lên rồi dịch các phần tử khác sang phải, ta liên tục đổi chỗ phần tử A[j] với A[j−1] nếu A[j] nhỏ hơn, cho đến khi nó nằm đúng vị trí. Kết quả tương đương với InsertionSort thông thường.

Hàm kt_hoanvi(A): Gồm hai giai đoạn. Đầu tiên gọi sapxep(A) để sắp xếp tăng dần. Sau đó duyệt dãy đã sắp: nếu A[i] != i + 1 tại bất kỳ vị trí nào thì A không phải hoán vị → gán kq = False và break dừng sớm. Nếu duyệt hết mà không vi phạm → trả về True.

Với dữ liệu mẫu A = [2, 1, 9, 10, 8, 6, 5, 2, 3, 1]:

Sau khi sắp xếp: A = [1, 1, 2, 2, 3, 5, 6, 8, 9, 10]. So sánh với [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]: tại i = 1, A[1] = 1 ≠ 2 → kết quả “KHÔNG”. Điều này đúng vì dãy ban đầu có phần tử trùng (số 1 và 2 xuất hiện hai lần) và thiếu số 4, 7.

Nhiệm vụ 2: Đếm số lần lặp

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

Cho dãy A gồm n phần tử. Cần tạo dãy B có cùng kích thước sao cho B[k] = số lần phần tử A[k] xuất hiện trong dãy A.

Ví dụ: A = [2, 1, 1, 3, 5, 10, 2, 5, 2] thì B = [3, 2, 2, 1, 2, 1, 3, 2, 3].

(Giải thích: Số 2 xuất hiện 3 lần → tại các vị trí A[0], A[6], A[8] đều có B = 3. Số 1 xuất hiện 2 lần → B[1] = B[2] = 2. Số 3 xuất hiện 1 lần → B[3] = 1, v.v.)

Thiết kế theo phương pháp làm mịn dần

a) Tìm hiểu bài toán

• Đầu vào: Dãy số A có n phần tử.
• Đầu ra: Dãy B trong đó B[k] = số lần xuất hiện của A[k] trong A.

b) Thiết kế làm mịn dần

Bước 1 – Ý tưởng tổng quan:

Cần duyệt lần lượt từng phần tử trong A, với mỗi phần tử, đếm xem nó xuất hiện bao nhiêu lần trong toàn bộ dãy A, rồi ghi kết quả vào dãy B.

1. Thiết lập dãy B rỗng.
2. Với mỗi phần tử A[i]:
   a. Tính số lần lặp của A[i] trong dãy A.
   b. Bổ sung giá trị này vào dãy B.
3. Trả về dãy B.

Các thao tác 1, 2a, 2b vẫn ở dạng mô tả → cần làm mịn.

Bước 2 – Cụ thể hoá “thiết lập dãy B rỗng”:

Đơn giản chỉ cần:

B = []

Bước 3 – Cụ thể hoá “tính số lần lặp của A[i] trong dãy A”:

Viết một hàm riêng lap(x, A) nhận giá trị x và dãy A, duyệt toàn bộ dãy A để đếm số phần tử bằng x:

def lap(x, A):
    S = 0
    for a in A:
        if a == x:
            S = S + 1
    return S

Bước 4 – Cụ thể hoá “bổ sung số lần lặp vào dãy B”:

Ghép bước 2 và 3 lại, dùng B.append() để thêm kết quả:

B = []
for i in range(len(A)):
    B.append(lap(A[i], A))
return B

Bước 5 – Gói thành hàm tinh_lap(A):

def tinh_lap(A):
    B = []
    for a in A:
        B.append(lap(a, A))
    return B

Tất cả thao tác đã thành câu lệnh → thiết kế hoàn tất.

Chương trình hoàn chỉnh

def lap(x, A):
    S = 0
    for a in A:
        if a == x:
            S = S + 1
    return S

def tinh_lap(A):
    B = []
    for a in A:
        B.append(lap(a, A))
    return B

# Chương trình chính
A = [2, 1, 1, 3, 5, 10, 2, 5, 2]
B = tinh_lap(A)
print(B)

Kết quả: [3, 2, 2, 1, 2, 1, 3, 2, 3]

Giải thích chi tiết

Hàm lap(x, A): Đây là hàm con đảm nhận một công việc cụ thể – đếm số lần giá trị x xuất hiện trong dãy A. Biến S khởi đầu bằng 0, vòng for a in A duyệt từng phần tử: nếu a == x thì tăng S. Cuối cùng trả về S.

Hàm tinh_lap(A): Tạo dãy B rỗng, sau đó với mỗi phần tử a trong A, gọi lap(a, A) để đếm số lần lặp rồi append vào B. Kết quả: B[k] chính là số lần A[k] xuất hiện.

Minh hoạ với A = [2, 1, 1, 3, 5, 10, 2, 5, 2]:

→ B = [3, 2, 2, 1, 2, 1, 3, 2, 3] ✓

Nhận xét về cách chia hàm con

Chương trình này minh hoạ rõ nét nguyên tắc chia bước lớn thành bước nhỏ, độc lập của phương pháp làm mịn dần. Hàm lap(x, A) chỉ lo việc đếm, hàm tinh_lap(A) chỉ lo việc duyệt và ghép kết quả. Mỗi hàm giải quyết một nhiệm vụ rõ ràng, dễ kiểm tra và tái sử dụng.

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)

Thiết kế thuật toán cho Nhiệm vụ 1 với ý tưởng khác như sau: Dãy A là một hoán vị của dãy các số từ 1 đến n khi và chỉ khi dãy A có độ dài n và mọi số i từ 1 đến n đều nằm trong A.

Lời giải:

a) Tìm hiểu bài toán: Giống Nhiệm vụ 1 – kiểm tra hoán vị, nhưng dùng ý tưởng khác: thay vì sắp xếp rồi so sánh, ta kiểm tra trực tiếp xem mỗi số từ 1 đến n có mặt trong A hay không.

b) Thiết kế làm mịn dần:

Bước 1 – Ý tưởng tổng quan:

1. Với mỗi số i từ 1 đến n:
     Kiểm tra xem i có nằm trong dãy A không.
     Nếu không tìm thấy → kết luận KHÔNG phải hoán vị.
2. Nếu tất cả đều tìm thấy → kết luận CÓ.

Bước 2 – Cụ thể hoá “kiểm tra i có nằm trong A”:

Viết hàm tim(x, A) duyệt dãy A xem có phần tử nào bằng x không:

def tim(x, A):
    for a in A:
        if a == x:
            return True
    return False

Bước 3 – Cụ thể hoá toàn bộ:

def kt_hoanvi(A):
    n = len(A)
    for i in range(1, n + 1):
        if not tim(i, A):
            return False
    return True

c) Chương trình hoàn chỉnh:

def tim(x, A):
    for a in A:
        if a == x:
            return True
    return False

def kt_hoanvi(A):
    n = len(A)
    for i in range(1, n + 1):
        if not tim(i, A):
            return False
    return True

# Chương trình chính
A = [3, 1, 2]
if kt_hoanvi(A):
    print("CÓ")
else:
    print("KHÔNG")

Giải thích: Cách này không cần sắp xếp. Hàm tim(x, A) thực chất là tìm kiếm tuần tự – trả True nếu tìm thấy x trong A. Hàm kt_hoanvi(A) kiểm tra lần lượt từng số i = 1, 2, …, n: nếu bất kỳ số nào không tìm thấy → trả False ngay. Nếu duyệt hết mà tất cả đều có → trả True.

Lưu ý: Cách này mặc định rằng nếu tất cả các số từ 1 đến n đều có mặt trong dãy n phần tử, thì không thể có phần tử trùng (vì n vị trí chứa đúng n giá trị khác nhau). Nên không cần kiểm tra phần tử trùng riêng.

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

Trong Nhiệm vụ 2, nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn được không?

Lời giải:

Có thể cải tiến. Khi dãy A đã sắp xếp tăng dần, các phần tử có giá trị bằng nhau sẽ nằm liền kề nhau. Ta có thể lợi dụng điều này để đếm nhanh hơn mà không cần gọi hàm lap() duyệt toàn bộ dãy cho mỗi phần tử.

Ý tưởng cải tiến: Duyệt dãy A đã sắp xếp một lần, đếm số phần tử liên tiếp có cùng giá trị. Khi gặp giá trị mới (khác giá trị trước), ghi nhận số lần đếm được cho tất cả phần tử cùng nhóm.

def tinh_lap_nhanh(A):
    # A đã sắp xếp tăng dần
    n = len(A)
    B = [0] * n
    i = 0
    while i < n:
        # Đếm số phần tử liên tiếp bằng A[i]
        dem = 1
        while i + dem < n and A[i + dem] == A[i]:
            dem = dem + 1
        # Gán số lần lặp cho tất cả phần tử trong nhóm
        for k in range(i, i + dem):
            B[k] = dem
        i = i + dem
    return B

# Thử nghiệm
A = [1, 1, 2, 2, 3, 5, 5, 10]
B = tinh_lap_nhanh(A)
print(B)  # [2, 2, 2, 2, 1, 2, 2, 1]

Giải thích tại sao nhanh hơn: Thuật toán gốc với mỗi phần tử phải duyệt toàn bộ dãy A (n lần) → tổng cộng xử lý khoảng n × n phép so sánh. Cách cải tiến chỉ duyệt dãy A một lần duy nhất từ trái sang phải → nhanh hơn nhiều với dãy dài.

Bài Vận dụng

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

Cho dãy số A = A[0], A[1], …, A[n – 1]. Thiết kế và viết chương trình kiểm tra trong dãy A có hai phần tử nào trùng nhau hay không. Cần đưa ra câu trả lời là “có” hay “không”. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.

Lời giải:

a) Tìm hiểu bài toán:

• Đầu vào: Dãy A gồm n phần tử.
• Đầu ra: “có” nếu tồn tại ít nhất hai phần tử trùng nhau, “không” nếu tất cả đều khác nhau.

b) Thiết kế làm mịn dần:

Bước 1 – Ý tưởng tổng quan:

Duyệt tất cả các cặp phần tử (i, j) với i < j. Nếu tìm thấy cặp nào mà A[i] = A[j] thì kết luận “có”. Nếu duyệt hết mà không tìm thấy → “không”.

1. Duyệt tất cả các cặp (i, j) với i < j.
2. Nếu tìm thấy A[i] == A[j] → trả "có".
3. Nếu không tìm thấy cặp nào → trả "không".

Bước 2 – Cụ thể hoá “duyệt tất cả các cặp”:

Tương tự bài đếm nghịch đảo (Bài 26): dùng hai vòng for lồng nhau, i chạy từ 0 đến n−2, j chạy từ i+1 đến n−1.

for i in range(n - 1):
    for j in range(i + 1, n):
        ...

Bước 3 – Cụ thể hoá “kiểm tra trùng”:

if A[i] == A[j]:
    return True

c) Chương trình hoàn chỉnh:

def co_trung(A):
    n = len(A)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if A[i] == A[j]:
                return True
    return False

# Chương trình chính
A = [5, 3, 8, 3, 9]
if co_trung(A):
    print("có")
else:
    print("không")

Kết quả với A = [5, 3, 8, 3, 9]: "có" (vì số 3 xuất hiện 2 lần).

Giải thích: Hàm co_trung(A) duyệt mọi cặp (i, j) với i < j. Ngay khi tìm thấy cặp đầu tiên mà A[i] == A[j], trả True luôn (dừng sớm, không cần duyệt hết). Nếu duyệt hết mà không tìm thấy cặp trùng nào → trả False.

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

Xâu kí tự được gọi là đối xứng nếu thay đổi thứ tự ngược lại các kí tự của xâu thì vẫn nhận được dãy ban đầu. Ví dụ xâu “abcdcba” là đối xứng, còn xâu “1011” không là đối xứng.

Thiết kế và viết chương trình kiểm tra một xâu kí tự cho trước có là đối xứng hay không. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.

Lời giải:

a) Tìm hiểu bài toán:

• Đầu vào: Xâu kí tự S.
• Đầu ra: “CÓ” nếu S đối xứng, “KHÔNG” nếu ngược lại.
• Đặc điểm: Xâu đối xứng khi kí tự đầu giống kí tự cuối, kí tự thứ hai giống kí tự gần cuối, v.v.

b) Thiết kế làm mịn dần:

Bước 1 – Ý tưởng tổng quan:

1. So sánh kí tự đầu với kí tự cuối, kí tự thứ hai với kí tự gần cuối, ...
2. Nếu tất cả các cặp đều giống nhau → đối xứng.
3. Nếu có cặp nào khác nhau → không đối xứng.

Bước 2 – Cụ thể hoá “so sánh các cặp kí tự đối xứng”:

Xâu S có độ dài n. Cặp đối xứng thứ i là S[i] và S[n−1−i]. Chỉ cần duyệt i từ 0 đến n//2 − 1 (nửa đầu xâu):

for i in range(n // 2):
    if S[i] != S[n - 1 - i]:
        return False
return True

Bước 3 – Gói thành hàm:

def doi_xung(S):
    n = len(S)
    for i in range(n // 2):
        if S[i] != S[n - 1 - i]:
            return False
    return True

Tất cả thao tác đã thành câu lệnh → thiết kế hoàn tất.

c) Chương trình hoàn chỉnh:

def doi_xung(S):
    n = len(S)
    for i in range(n // 2):
        if S[i] != S[n - 1 - i]:
            return False
    return True

# Chương trình chính
S = input("Nhập xâu kí tự: ")
if doi_xung(S):
    print("CÓ")
else:
    print("KHÔNG")

Giải thích: Hàm doi_xung(S) chỉ cần duyệt nửa đầu xâu. Tại vị trí i, so sánh S[i] với S[n−1−i] (kí tự đối xứng qua tâm xâu). Nếu tìm thấy cặp khác nhau → trả False ngay. Nếu duyệt hết nửa đầu mà không có cặp nào khác nhau → xâu đối xứng.

Minh hoạ với S = “abcdcba” (n = 7):

Duyệt 3 cặp (n//2 = 3), tất cả giống → “CÓ”. Kí tự giữa (S[3] = ‘d’) không cần kiểm tra vì nó đối xứng với chính 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