I. Lý thuyết trọng tâm

1. Phương pháp làm mịn dần là gì?

Nhìn lại các thuật toán đã học – tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt – ta nhận thấy chúng đều được xây dựng theo cùng một cách tiếp cận: bắt đầu từ ý tưởng tổng quát, sau đó cụ thể hoá dần cho đến khi mọi thao tác đều có thể viết thành câu lệnh lập trình.

Cách tiếp cận này gọi là phương pháp làm mịn dần (stepwise refinement). Nội dung cốt lõi:

• Quá trình thiết kế được chia thành nhiều bước thực hiện lần lượt.
• Bước đầu tiên mô tả ý tưởng tổng quan của lời giải (có thể bằng ngôn ngữ tự nhiên, chưa cần viết code).
• Mỗi bước tiếp theo chi tiết hoá thêm các thao tác còn chung chung ở bước trước, biến chúng thành những hành động cụ thể hơn.
• Bước cuối cùng, tất cả các thao tác đều được chuyển thành câu lệnh lập trình → chương trình hoàn chỉnh.

Nói cách khác, mỗi bước sau là phiên bản “mịn hơn” – rõ ràng hơn, chi tiết hơn – so với bước trước. Quá trình cứ tiếp tục cho đến khi không còn thao tác nào cần cụ thể hoá thêm.

2. Minh hoạ qua thiết kế thuật toán sắp xếp chèn

Để hiểu rõ phương pháp, ta cùng xem lại cách thuật toán sắp xếp chèn được thiết kế từng bước.

Bài toán: Cho dãy A gồm n phần tử, sắp xếp dãy theo thứ tự tăng dần.

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

Duyệt lần lượt từ phần tử thứ hai đến phần tử cuối. Tại mỗi vị trí i, đưa A[i] vào đúng chỗ trong phần đã sắp xếp phía trước để dãy từ A[0] đến A[i] có thứ tự đúng.

for i in range(1, n):
    <Đặt A[i] vào đúng vị trí của dãy A[0], A[1], ..., A[i-1]>

Ở bước này, dòng thứ hai vẫn là mô tả bằng lời, chưa phải câu lệnh Python. Đó chính là phần cần làm mịn tiếp.

Bước 2 – Phân tách thao tác “chèn vào đúng vị trí”

Thao tác “chèn A[i] vào đúng vị trí” có thể chia thành ba việc nhỏ hơn:

1. Nhấc phần tử A[i] ra (lưu vào biến tạm).
2. Dịch các phần tử bên trái A[i] mà lớn hơn A[i] sang phải.
3. Đặt A[i] vào ô trống vừa tạo ra.

Ba việc này vẫn là mô tả bằng lời → cần làm mịn thêm.

Bước 3 – Cụ thể hoá “nhấc phần tử A[i]”

Việc này đơn giản, chỉ cần một lệnh gán:

value = A[i]

Bước này đã “mịn” hoàn toàn – đã là câu lệnh Python hợp lệ.

Bước 4 – Cụ thể hoá “dịch các phần tử lớn hơn sang phải”

Dùng biến j bắt đầu từ vị trí i − 1 (ngay bên trái A[i]). So sánh A[j] với value: nếu A[j] lớn hơn thì dịch A[j] sang phải một ô, rồi lùi j. Dừng khi j < 0 hoặc A[j] không lớn hơn value.

j = i - 1
while j >= 0 and A[j] > value:
    A[j + 1] = A[j]
    j = j - 1

Bước 5 – Cụ thể hoá “đặt A[i] vào ô trống”

Sau bước 4, vị trí j + 1 chính là ô trống. Chỉ cần gán:

A[j + 1] = value

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

Ghép tất cả các bước lại, ta được:

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

Nhận xét: Qua 5 bước, ta đã đi từ ý tưởng “duyệt và chèn vào đúng chỗ” (rất chung chung) đến chương trình hoàn chỉnh bằng Python. Mỗi bước chỉ tập trung làm rõ một thao tác cụ thể, giúp việc thiết kế trở nên có hệ thống và dễ kiểm soát.

3. Minh hoạ qua bài toán đếm cặp nghịch đảo

Bài toán: Cho dãy A gồm n phần tử. Cặp (A[i], A[j]) gọi là nghịch đảo nếu i < j nhưng A[i] > A[j]. Đếm số cặp nghịch đảo.

Ví dụ: Dãy [3, 4, 2, 1] có 5 cặp nghịch đảo: (3, 2), (3, 1), (4, 2), (4, 1), (2, 1).

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

Cần duyệt tất cả các cặp phần tử có thể, kiểm tra xem cặp nào là nghịch đảo, đếm lại.

count = 0
<Tìm tất cả các cặp chỉ số (i, j) có thể tạo cặp nghịch đảo>
<Kiểm tra nếu cặp A[i], A[j] là nghịch đảo thì tăng count lên 1>
return count

Ở bước này, hai thao tác chính vẫn đang ở dạng mô tả → cần làm mịn.

Bước 2 – Cụ thể hoá “tìm tất cả các cặp (i, j)”

Để xét mọi cặp mà i < j, ta 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. Cách thiết lập này đảm bảo i luôn nhỏ hơn j, không cần kiểm tra điều kiện i < j nữa.

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

Ghép vào thuật toán:

count = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if <cặp (i, j) là nghịch đảo>:
            tăng count lên 1
return count

Phần kiểm tra nghịch đảo vẫn là mô tả bằng lời → làm mịn tiếp.

Bước 3 – Cụ thể hoá “kiểm tra nghịch đảo”

Cặp (i, j) là nghịch đảo khi i < j và A[i] > A[j]. Nhưng ở bước 2, vòng lặp đã đảm bảo i < j rồi, nên chỉ cần kiểm tra một điều kiện:

if A[i] > A[j]:
    count = count + 1

Đến đây mọi thao tác đã được cụ thể hoá bằng câu lệnh Python → thiết kế hoàn tất.

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

def Nghichdao(A):
    n = len(A)
    count = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if A[i] > A[j]:
                count = count + 1
    return count

Nhận xét: Bài toán này chỉ cần 3 bước làm mịn (ít hơn sắp xếp chèn) vì logic đơn giản hơn. Số bước phụ thuộc vào độ phức tạp của bài toán, không cố định.

4. Nguyên tắc của phương pháp làm mịn dần

Tổng kết lại, phương pháp làm mịn dần tuân thủ ba nguyên tắc:

Nguyên tắc 1 – Thiết kế theo từng bước: Chia quá trình thiết kế thành nhiều bước, thực hiện lần lượt từ trên xuống.

Nguyên tắc 2 – Chia nhỏ vấn đề: Mỗi thao tác lớn có thể chia thành nhiều thao tác nhỏ hơn, giải quyết độc lập. Ví dụ: “chèn A[i] vào đúng vị trí” được chia thành ba thao tác: nhấc, dịch, đặt.

Nguyên tắc 3 – Từ tổng quan đến chi tiết: Bắt đầu bằng cái nhìn toàn cảnh, mỗi bước sau cụ thể hoá hơn bước trước, cho đến khi toàn bộ đều là câu lệnh lập trình.

II. Phương pháp giải các dạng bài tập

Dạng 1: Nhận biết và giải thích phương pháp làm mịn dần

Phương pháp: Xác định các bước đi từ ý tưởng tổng quan → chi tiết hoá → câu lệnh cụ thể. Mỗi bước sau phải cụ thể hơn bước trước.

Bài 1 (Luyện tập SGK). Phát biểu sau đúng hay sai? “Khi thiết kế chương trình thì việc đầu tiên là tìm hiểu yêu cầu chung của bài toán, xác định đầu vào, đầu ra của bài toán, sau đó mới đi cụ thể vào chi tiết.”

Lời giải:

Phát biểu trên là ĐÚNG. Đây chính là nguyên tắc cốt lõi của phương pháp làm mịn dần: luôn bắt đầu bằng việc tìm hiểu bài toán – hiểu rõ yêu cầu, xác định đầu vào (dữ liệu cho trước) và đầu ra (kết quả cần đạt). Sau đó mới thiết kế ý tưởng tổng quan, rồi lần lượt cụ thể hoá từng phần cho đến khi có chương trình hoàn chỉnh.

Nếu bỏ qua bước tìm hiểu bài toán và lao vào viết code ngay, ta dễ hiểu sai yêu cầu hoặc thiếu sót trường hợp, dẫn đến chương trình sai.

Dạng 2: Áp dụng chương trình đã thiết kế để giải bài toán cụ thể

Phương pháp: Chạy tay (mô phỏng) chương trình với dữ liệu cho trước, theo dõi giá trị biến qua từng bước lặp.

Bài 2 (Luyện tập SGK). Sử dụng thiết kế của bài toán đếm cặp nghịch đảo, tìm tất cả các cặp nghịch đảo của dãy: 3, 2, 1, 5, 4.

Lời giải:

Áp dụng hàm Nghichdao(A) với A = [3, 2, 1, 5, 4], n = 5.

Duyệt tất cả các cặp (i, j) với i < j, kiểm tra A[i] > A[j]:

Kết quả: Dãy [3, 2, 1, 5, 4] có 4 cặp nghịch đảo: (3, 2), (3, 1), (2, 1), (5, 4).

Dạng 3: Thiết kế chương trình mới bằng phương pháp làm mịn dần

Phương pháp: Thực hiện đúng quy trình: (1) Tìm hiểu bài toán → (2) Ý tưởng tổng quan → (3) Làm mịn từng thao tác → (4) Chương trình hoàn chỉnh.

Bài 3 (Vận dụng SGK). Sử dụng phương pháp làm mịn dần để giải bài toán: Cho trước số tự nhiên không âm n, kiểm tra xem n có phải là số nguyên tố hay không. Thông báo “CÓ” nếu là số nguyên tố, ngược lại thông báo “KHÔNG”.

Lời giải:

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

• Đầu vào: Số tự nhiên không âm n.
• Đầu ra: Thông báo “CÓ” nếu n là số nguyên tố, “KHÔNG” nếu không phải.
• Nhắc lại: Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó.

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

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

Nhập n
if <n là số nguyên tố>:
    Thông báo "CÓ"
else:
    Thông báo "KHÔNG"

Phần cần làm mịn: cách kiểm tra “n là số nguyên tố”.

Bước 2 – Cụ thể hoá “kiểm tra n là số nguyên tố”:

Một số là nguyên tố nếu nó lớn hơn 1 và không có ước nào ngoài 1 và chính nó. Vậy ta cần kiểm tra: n có bị chia hết cho số nào từ 2 đến n − 1 không?

if n < 2:
    n KHÔNG phải số nguyên tố
else:
    <Kiểm tra xem n có ước nào trong khoảng từ 2 đến n - 1 không>
    Nếu không có ước nào → n là số nguyên tố
    Nếu tìm thấy ước → n không phải số nguyên tố

Phần cần làm mịn: cách kiểm tra ước trong khoảng.

Bước 3 – Cụ thể hoá “kiểm tra ước trong khoảng”:

Duyệt biến i từ 2 đến n − 1. Nếu tìm thấy n % i == 0 (n chia hết cho i) thì n không phải nguyên tố. Để tối ưu, ta chỉ cần duyệt đến căn bậc hai của n, vì nếu n có ước lớn hơn √n thì chắc chắn cũng có ước nhỏ hơn √n.

la_nguyen_to = True
for i in range(2, int(n**0.5) + 1):
    if n % i == 0:
        la_nguyen_to = False
        break

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

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

def KiemTraNguyenTo(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

n = int(input("Nhập số tự nhiên n: "))
if KiemTraNguyenTo(n):
    print("CÓ")
else:
    print("KHÔNG")

Giải thích: Hàm KiemTraNguyenTo(n) trả về True nếu n là nguyên tố, False nếu không. Trường hợp n < 2 loại ngay (0 và 1 không phải nguyên tố). Vòng for duyệt từ 2 đến √n: nếu tìm thấy ước thì trả False ngay (dùng return thay cho break để code gọn hơn). Nếu duyệt hết mà không tìm thấy ước nào thì n là nguyên tố.

Bài 4 (Vận dụng SGK). Với thuật toán sắp xếp chèn, chứng minh rằng nếu thay toàn bộ phần “Chèn A[i] vào vị trí đúng của dãy con A[0], A[1], …, A[i−1]” bằng các lệnh sau thì chương trình vẫn đúng:

j = i
while j > 0 and A[j] < A[j-1]:
    Đổi chỗ A[j] và A[j-1]
    j = j - 1

Lời giải:

Ta cần chứng minh đoạn code mới cũng thực hiện đúng việc “đưa A[i] về vị trí đúng trong dãy đã sắp xếp”.

Phân tích cách hoạt động:

Gọi phần tử cần chèn ban đầu nằm ở vị trí i. Biến j bắt đầu bằng i.

Vòng while kiểm tra: nếu A[j] < A[j-1] (phần tử hiện tại nhỏ hơn phần tử ngay bên trái) thì đổi chỗ hai phần tử này, rồi giảm j. Quá trình dừng khi j = 0 (đã đến đầu dãy) hoặc A[j] >= A[j-1] (phần tử đã nằm đúng chỗ).

So sánh với cách gốc:

Chứng minh tính đúng đắn:

Trước vòng while, dãy A[0], ..., A[i-1] đã được sắp xếp đúng (theo giả thiết quy nạp của thuật toán sắp xếp chèn).

Tại mỗi bước lặp, nếu A[j] < A[j-1] thì hai phần tử này sai thứ tự → đổi chỗ. Sau khi đổi, phần tử cần chèn đã “lùi” sang trái một vị trí (j giảm 1). Thao tác đổi chỗ không làm thay đổi thứ tự tương đối của các phần tử khác trong dãy con đã sắp xếp (vì ta chỉ đổi hai phần tử liền kề).

Vòng lặp dừng khi A[j] >= A[j-1], tức phần tử cần chèn đã nằm đúng vị trí: tất cả phần tử bên trái nó đều nhỏ hơn hoặc bằng, tất cả phần tử bên phải (đến vị trí i) đều lớn hơn hoặc bằng.

Kết quả cuối cùng: dãy A[0], ..., A[i] được sắp xếp đúng → chương trình vẫn đúng.

Minh hoạ nhanh với A = [3, 5, 7, 2, …], i = 3 (cần chèn A[3] = 2):

j = 3: A = [3, 5, 7, 2] → 2 < 7 → đổi chỗ → [3, 5, 2, 7], j = 2
j = 2: A = [3, 5, 2, 7] → 2 < 5 → đổi chỗ → [3, 2, 5, 7], j = 1
j = 1: A = [3, 2, 5, 7] → 2 < 3 → đổi chỗ → [2, 3, 5, 7], j = 0
j = 0: dừng (j = 0)

Kết quả: [2, 3, 5, 7] – đúng thứ tự tăng dần. ✓

III. Sơ đồ tư duy

                    ┌─ Bước 1: Tìm hiểu bài toán
                    │   (xác định đầu vào, đầu ra)
                    │
                    ├─ Bước 2: Ý tưởng tổng quan
    PHƯƠNG PHÁP     │   (mô tả bằng lời, chưa cần code)
    LÀM MỊN DẦN ───┤
                    ├─ Bước 3, 4, ...: Làm mịn từng thao tác
                    │   (chi tiết hoá dần thành câu lệnh)
                    │
                    └─ Bước cuối: Chương trình hoàn chỉnh
                        (ghép tất cả thành code Python)

    BA NGUYÊN TẮC:
    ┌───────────────────────────────────────────────┐
    │ 1. Thiết kế theo từng bước, lần lượt          │
    │ 2. Chia bước lớn thành bước nhỏ, độc lập      │
    │ 3. Từ tổng quan → chi tiết                    │
    └───────────────────────────────────────────────┘

    VÍ DỤ MINH HOẠ:
    ┌─ Sắp xếp chèn ──── 5 bước làm mịn
    │   Ý tưởng "duyệt & chèn" → code hoàn chỉnh
    │
    └─ Đếm cặp nghịch đảo ── 3 bước làm mịn
        Ý tưởng "duyệt cặp & kiểm tra" → code hoàn chỉnh

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