Ôn thi HSG Tin học THPT – Bài 9: Duyệt nhiều vòng lặp (Brute-force)

1. Mục tiêu

Nắm vững và vận dụng phương pháp duyệt toàn bộ (brute-force) để giải quyết các bài toán bằng cách sử dụng các vòng lặp for lồng nhau.
Hiểu rõ cách các biến lặp thay đổi và tương tác trong các vòng lặp lồng nhau thông qua công cụ gỡ lỗi (debug) của Thonny.
Phân tích được độ phức tạp thời gian của các giải thuật duyệt và nhận biết giới hạn áp dụng của phương pháp này.

2. Bài toán dẫn nhập

Cho một danh sách các số nguyên A và một số nguyên mục tiêu K. Hãy tìm hai chỉ số i và j khác nhau trong danh sách sao cho tổng của hai phần tử tương ứng A[i] + A[j] = K. Nếu có nhiều cặp thỏa mãn, chỉ cần tìm một cặp đầu tiên.

Ví dụ:

Đầu vào: A = [2, 7, 11, 15], K = 9
Đầu ra: i = 0, j = 1 (vì A[0] + A[1] = 2 + 7 = 9)

3. Nguyên lý thuật toán

3.1. Ý tưởng cốt lõi

Thuật toán duyệt toàn bộ, thường được biết đến với tên gọi “Brute-force” hay “vét cạn”, là một phương pháp giải quyết bài toán bằng cách thử mọi trường hợp có thể xảy ra một cách hệ thống và kiểm tra xem trường hợp nào thỏa mãn điều kiện của bài toán.

Đối với bài toán dẫn nhập, ý tưởng là xét mọi cặp phần tử có thể có trong danh sách A. Để thực hiện điều này, ta có thể dùng hai vòng lặp lồng nhau.

Vòng lặp ngoài cùng chọn phần tử thứ nhất, gọi là A[i].
Vòng lặp bên trong chọn phần tử thứ hai, gọi là A[j].

Với mỗi cặp (A[i], A[j]) được tạo ra, ta kiểm tra xem tổng của chúng có bằng K hay không. Để đảm bảo hai chỉ số i và j là khác nhau, ta cần có điều kiện i != j.

3.2. Minh họa các bước thực thi

Xét ví dụ A = [2, 7, 11, 15] và K = 9.

Vòng lặp ngoài (biến i) bắt đầu từ 0. A[0] là 2.
- Vòng lặp trong (biến j) bắt đầu từ 0.
  - j = 0: i bằng j, bỏ qua.
  - j = 1: A[1] là 7. Kiểm tra A[0] + A[1] == 9? 2 + 7 = 9. Đúng. Tìm thấy lời giải tại i=0, j=1. Kết thúc.

Nếu K = 18, quá trình sẽ diễn ra như sau:

i = 0 (A = 2):
- j = 1 (A = 7): 2 + 7 = 9 != 18.
- j = 2 (A = 11): 2 + 11 = 13 != 18.
- j = 3 (A = 15): 2 + 15 = 17 != 18.
i = 1 (A = 7):
- j = 0 (A = 2): 7 + 2 = 9 != 18.
- j = 2 (A = 11): 7 + 11 = 18. Đúng. Tìm thấy lời giải tại i=1, j=2. Kết thúc.

4. Cài đặt thuật toán

Dưới đây là đoạn mã Python cài đặt thuật toán cho bài toán dẫn nhập.

def find_pair_sum(A, K):
    """
    Tìm một cặp chỉ số (i, j) sao cho A[i] + A[j] = K bằng phương pháp duyệt toàn bộ.
    """
    n = len(A)
    # Vòng lặp ngoài để chọn phần tử thứ nhất A[i]
    for i in range(n):
        # Vòng lặp trong để chọn phần tử thứ hai A[j]
        for j in range(n):
            # Đảm bảo hai chỉ số khác nhau
            if i != j:
                # Kiểm tra điều kiện của bài toán
                if A[i] + A[j] == K:
                    print(f"Tìm thấy cặp chỉ số: i = {i}, j = {j}")
                    return # Kết thúc hàm ngay khi tìm thấy cặp đầu tiên

    print("Không tìm thấy cặp nào thỏa mãn.")

# Dữ liệu đầu vào mẫu
A = [2, 7, 11, 15]
K = 9
find_pair_sum(A, K)

5. Trực quan hóa và gỡ lỗi với Thonny

Việc sử dụng công cụ gỡ lỗi (debugger) là cực kỳ hữu ích để hiểu rõ cách các vòng lặp lồng nhau hoạt động.

Các bước thực hiện trên Thonny:

Dán đoạn mã nguồn trên vào trình soạn thảo của Thonny.
Đặt một điểm dừng (breakpoint) tại dòng for i in range(n): bằng cách nhấp chuột vào lề trái của dòng đó. Một chấm đỏ sẽ xuất hiện.
Chạy chương trình ở chế độ gỡ lỗi bằng cách nhấn phím Ctrl+F5 hoặc chọn Run -> Debug current script.
Chương trình sẽ dừng lại tại điểm dừng. Cửa sổ Variables sẽ hiển thị các biến hiện có.
Sử dụng nút Step over (F6) hoặc Step into (F7) để đi qua từng dòng lệnh. Quan sát sự thay đổi giá trị của các biến i và j trong cửa sổ Variables. Điều này sẽ cho thấy một cách trực quan cách máy tính duyệt qua tất cả các cặp (i, j).

6. Bài tập vận dụng

6.1. Đề bài

Cho hai số nguyên dương N và M. Đếm số lượng cặp số nguyên (a, b) thỏa mãn đồng thời hai điều kiện sau:

1 ≤ a ≤ N
1 ≤ b ≤ M
Tổng a + b chia hết cho 5.

Ví dụ:

Đầu vào: N = 3, M = 4
Đầu ra: 2
Giải thích: Các cặp (a, b) thỏa mãn là (1, 4) và (3, 2).

6.2. Lời giải và phân tích

Phân tích:
Bài toán yêu cầu đếm số cặp (a, b) thỏa mãn các điều kiện cho trước. Ta có thể áp dụng phương pháp duyệt toàn bộ bằng cách thử tất cả các giá trị có thể có của a và b.

a có thể nhận các giá trị từ 1 đến N.
b có thể nhận các giá trị từ 1 đến M.

Ta sẽ dùng một biến đếm, khởi tạo bằng 0. Dùng hai vòng lặp lồng nhau, một vòng cho a và một vòng cho b. Bên trong vòng lặp, ta kiểm tra điều kiện (a + b) % 5 == 0. Nếu điều kiện đúng, tăng biến đếm lên 1.

Cài đặt:

def count_divisible_pairs(N, M):
    """
    Đếm số cặp (a, b) thỏa mãn 1 <= a <= N, 1 <= b <= M và (a + b) chia hết cho 5.
    """
    count = 0 # Biến đếm số lượng cặp thỏa mãn

    # Vòng lặp duyệt qua tất cả các giá trị của a từ 1 đến N
    for a in range(1, N + 1):
        # Vòng lặp duyệt qua tất cả các giá trị của b từ 1 đến M
        for b in range(1, M + 1):
            # Kiểm tra điều kiện tổng chia hết cho 5
            if (a + b) % 5 == 0:
                count += 1 # Tăng biến đếm

    return count

# Dữ liệu đầu vào
N = 3
M = 4

# Gọi hàm và in kết quả
result = count_divisible_pairs(N, M)
print(f"Số lượng cặp thỏa mãn là: {result}")

7. Đánh giá thuật toán và mở rộng

7.1. Phân tích độ phức tạp

Độ phức tạp thời gian của một thuật toán duyệt toàn bộ phụ thuộc vào số lượng các vòng lặp lồng nhau và phạm vi của mỗi vòng lặp.

Trong bài toán tìm cặp có tổng bằng K, ta có hai vòng lặp, mỗi vòng chạy n lần. Do đó, số phép toán xấp xỉ n * n = n^2. Độ phức tạp thời gian là O(n²).
Trong bài tập vận dụng, vòng lặp ngoài chạy N lần và vòng lặp trong chạy M lần. Độ phức tạp thời gian là O(N * M).
Nếu một bài toán yêu cầu tìm bộ ba số, ta có thể cần đến ba vòng lặp lồng nhau, dẫn đến độ phức tạp là O(n³).

Phương pháp duyệt toàn bộ rất dễ cài đặt nhưng thường không hiệu quả về mặt thời gian khi dữ liệu đầu vào lớn (ví dụ n > 5000 đối với O(n²)).

7.2. Các trường hợp đặc biệt và biến thể

Duyệt các cặp không có thứ tự: Trong bài toán tìm cặp A[i] + A[j] = K, cặp (i, j) và (j, i) được coi là như nhau. Để tránh kiểm tra trùng lặp và cải thiện hiệu suất một chút, ta có thể thiết lập vòng lặp trong bắt đầu từ i + 1. Điều này đảm bảo rằng mỗi cặp chỉ được xét một lần (j > i).

for i in range(n):
    for j in range(i + 1, n): # j luôn lớn hơn i
        if A[i] + A[j] == K:
            # ...

Duyệt với nhiều hơn hai vòng lặp: Các bài toán phức tạp hơn có thể yêu cầu tìm bộ ba, bộ bốn, v.v. Ví dụ, tìm ba chỉ số i, j, k khác nhau sao cho A[i] + A[j] + A[k] = K sẽ cần ba vòng lặp lồng nhau.

8. Tổng kết

Duyệt toàn bộ (Brute-force) là một kỹ thuật nền tảng, giải quyết bài toán bằng cách thử tất cả các trường hợp có thể.
Kỹ thuật này thường được cài đặt bằng cách sử dụng các vòng lặp for lồng nhau.
Ưu điểm lớn nhất của phương pháp này là tính đơn giản, dễ hình dung và cài đặt.
Nhược điểm chính là hiệu suất thấp, với độ phức tạp thời gian thường là đa thức bậc cao (O(n²), O(n³),…), chỉ phù hợp với các bài toán có giới hạn dữ liệu nhỏ.
Việc sử dụng công cụ gỡ lỗi là một phương pháp hiệu quả để theo dõi và hiểu rõ quá trình thực thi của các vòng lặp lồng nhau.