Bài 15.4: Bài tập thực hành đệ quy nâng cao trong C++

Chào mừng quay trở lại với chuỗi bài học C++ của chúng ta! Sau khi đã làm quen với các khái niệm cơ bản về đệ quy, giờ là lúc chúng ta cùng nhau chinh phục những thử thách khó nhằn hơn. Bài viết này sẽ tập trung vào các bài tập thực hành đệ quy nâng cao, giúp bạn rèn luyện tư duy phân tích vấn đề và áp dụng đệ quy một cách linh hoạt để giải quyết các bài toán phức tạp hơn.

Đệ quy không chỉ là gọi lại chính nó; nó là một cách tiếp cận mạnh mẽ để giải quyết các vấn đề có thể được chia nhỏ thành các bài toán con tương tự với bài toán gốc, nhưng ở quy mô nhỏ hơn. Khi bạn gặp một vấn đề có cấu trúc như vậy, đệ quy thường mang lại lời giải thanh lịch và dễ hiểu. Tuy nhiên, để thành thạo, chúng ta cần luyện tập với nhiều loại bài toán khác nhau.

Hãy cùng đi sâu vào một số bài tập điển hình nhé!

Bài Tập 1: Tháp Hà Nội (Tower of Hanoi)

Tháp Hà Nội là một trong những bài toán kinh điển nhất để minh họa sức mạnh của đệ quy.

Mô tả bài toán: Bạn có ba chiếc cọc (gọi là cọc A, B, C) và n đĩa có kích thước khác nhau được xếp chồng lên nhau theo thứ tự giảm dần kích thước trên cọc A (đĩa lớn nhất nằm dưới cùng). Mục tiêu là chuyển toàn bộ n đĩa từ cọc A sang cọc C, tuân thủ các quy tắc sau:
1. Chỉ được di chuyển một đĩa một lần.
2. Chỉ được di chuyển đĩa trên cùng của một cọc.
3. Không bao giờ được đặt đĩa lớn hơn lên trên đĩa nhỏ hơn.
Tư duy đệ quy: Làm thế nào để chuyển n đĩa từ A sang C?
- Điều kiện dừng (Base Case): Nếu chỉ có 1 đĩa (n=1), ta chỉ cần chuyển trực tiếp đĩa đó từ cọc nguồn sang cọc đích. Đây là trường hợp đơn giản nhất và có thể giải quyết trực tiếp.
- Bước đệ quy (Recursive Step): Để chuyển n đĩa từ A sang C dùng cọc B làm trung gian, ta thực hiện các bước sau:
  1. Chuyển n-1 đĩa từ cọc A sang cọc B, dùng cọc C làm trung gian. (Bài toán con, tương tự bài toán gốc nhưng quy mô nhỏ hơn).
  2. Chuyển đĩa thứ n (đĩa lớn nhất) từ cọc A sang cọc C. (Bước đơn giản).
  3. Chuyển n-1 đĩa từ cọc B sang cọc C, dùng cọc A làm trung gian. (Bài toán con, tương tự bài toán gốc nhưng quy mô nhỏ hơn).

Đây chính là cấu trúc đệ quy rõ ràng!

Code minh họa:

#include <iostream>
#include <string>

void hanoi(int n, char source, char auxiliary, char destination) {
    // Điều kiện dừng: Nếu chỉ có 1 đĩa
    if (n == 1) {
        cout << "Chuyen dia 1 tu coc " << source << " sang coc " << destination << endl;
        return;
    }

    // Bước đệ quy 1: Chuyen n-1 dia tu source sang auxiliary, dung destination lam trung gian
    hanoi(n - 1, source, destination, auxiliary);

    // Bước đệ quy 2: Chuyen dia thu n tu source sang destination
    cout << "Chuyen dia " << n << " tu coc " << source << " sang coc " << destination << endl;

    // Bước đệ quy 3: Chuyen n-1 dia tu auxiliary sang destination, dung source lam trung gian
    hanoi(n - 1, auxiliary, source, destination);
}

int main() {
    int num_disks = 3;
    cout << "Cac buoc giai bai toan Thap Ha Noi voi " << num_disks << " dia:" << endl;
    hanoi(num_disks, 'A', 'B', 'C');
    return 0;
}

Giải thích code:
- Hàm hanoi(n, source, auxiliary, destination) nhận vào số đĩa (n) và tên của ba cọc.
- Điều kiện dừng (if (n == 1)): Khi chỉ cần di chuyển đĩa 1, ta in ra bước di chuyển cuối cùng và kết thúc lời gọi đệ quy.
- Bước đệ quy:
  - hanoi(n - 1, source, destination, auxiliary);: Lời gọi này giải quyết bài toán con: chuyển n-1 đĩa từ cọc source sang cọc auxiliary, sử dụng cọc destination làm cọc tạm.
  - cout << ...: Sau khi n-1 đĩa đã được di chuyển, đĩa lớn nhất (n) ở cọc source giờ đã lộ ra, ta di chuyển nó sang cọc destination.
  - hanoi(n - 1, auxiliary, source, destination);: Cuối cùng, ta giải quyết bài toán con còn lại: chuyển n-1 đĩa từ cọc auxiliary sang cọc destination, sử dụng cọc source làm cọc tạm.

Bài Tập 2: Phát Sinh Tất Cả Tổ Hợp (Generate Combinations)

Bài toán này thuộc nhóm các bài toán "sinh" (generating) hoặc "liệt kê" (enumerating), nơi đệ quy thường được sử dụng kết hợp với kỹ thuật backtracking.

Mô tả bài toán: Cho một tập hợp các phần tử phân biệt và một số nguyên k. Hãy viết hàm đệ quy để liệt kê tất cả các tập con có k phần tử của tập hợp ban đầu (các tổ hợp chập k).
Tư duy đệ quy (sử dụng Backtracking): Ta có thể xây dựng từng tổ hợp một cách đệ quy. Tại mỗi bước, ta quyết định có chọn phần tử hiện tại vào tổ hợp đang xây dựng hay không. Xét các phần tử từ trái sang phải. Tại phần tử thứ i:
- Trường hợp 1: Không chọn phần tử thứ i. Ta bỏ qua phần tử này và tiếp tục xem xét phần tử thứ i+1 để tìm đủ k phần tử từ các phần tử còn lại.
- Trường hợp 2: Chọn phần tử thứ i. Ta thêm phần tử này vào tổ hợp hiện tại, giảm số lượng phần tử cần tìm đi 1 (k-1), và tiếp tục xem xét phần tử thứ i+1 để tìm đủ k-1 phần tử còn lại. Sau khi đã thử tất cả các khả năng từ đây (các lời gọi đệ quy con đã hoàn thành), ta quay lui (backtrack) bằng cách loại bỏ phần tử thứ i khỏi tổ hợp hiện tại để khám phá các khả năng khác mà không chọn phần tử này.
Điều kiện dừng (Base Case):
- Nếu số lượng phần tử đã chọn bằng k, ta đã tìm được một tổ hợp hợp lệ. In hoặc lưu tổ hợp này lại.
- Nếu đã duyệt hết tất cả các phần tử trong tập hợp ban đầu mà vẫn chưa đủ k phần tử, nhánh tìm kiếm này không thành công, dừng lại.
Code minh họa:

#include <iostream>
#include <vector>
#include <string>

void generateCombinationsHelper(const vector<int>& elements, int k, int start_index,
                                vector<int>& current_combination) {
    // Điều kiện dừng 1: Nếu đã đủ k phần tử trong tổ hợp hiện tại
    if (current_combination.size() == k) {
        cout << "{ ";
        for (size_t i = 0; i < current_combination.size(); ++i) {
            cout << current_combination[i] << (i == current_combination.size() - 1 ? "" : ", ");
        }
        cout << " }" << endl;
        return; // Đã tìm thấy 1 tổ hợp, dừng nhánh này
    }

    // Điều kiện dừng 2: Nếu đã duyệt hết các phần tử còn lại nhưng chưa đủ k
    // Hoặc nếu số phần tử còn lại không đủ để hoàn thành tổ hợp (optimization)
    if (start_index >= elements.size() || elements.size() - start_index < k - current_combination.size()) {
        return;
    }

    // Bước đệ quy:
    // Trường hợp 1: Chọn phần tử tại start_index
    current_combination.push_back(elements[start_index]);
    generateCombinationsHelper(elements, k, start_index + 1, current_combination);

    // Bước đệ quy: Backtrack - Bỏ chọn phần tử tại start_index để khám phá khả năng khác
    current_combination.pop_back();

    // Trường hợp 2: Không chọn phần tử tại start_index
    generateCombinationsHelper(elements, k, start_index + 1, current_combination);
}

void generateCombinations(const vector<int>& elements, int k) {
    vector<int> current_combination;
    generateCombinationsHelper(elements, k, 0, current_combination);
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    int k_size = 2;

    cout << "Cac to hop chap " << k_size << " tu tap {1, 2, 3, 4}:" << endl;
    generateCombinations(nums, k_size);

    k_size = 3;
    cout << "\nCac to hop chap " << k_size << " tu tap {1, 2, 3, 4}:" << endl;
    generateCombinations(nums, k_size);

    return 0;
}

Giải thích code:
- Hàm generateCombinations là hàm bao bọc. Hàm chính là generateCombinationsHelper.
- generateCombinationsHelper nhận tập hợp gốc (elements), kích thước k cần tìm, chỉ số bắt đầu start_index (để biết đang xét từ phần tử nào trở đi), và current_combination (vector lưu trữ tổ hợp đang được xây dựng).
- Điều kiện dừng 1: Nếu current_combination.size() bằng k, ta đã xây dựng xong một tổ hợp, in nó ra và trở về.
- Điều kiện dừng 2: Nếu start_index vượt quá kích thước mảng hoặc số phần tử còn lại (elements.size() - start_index) không đủ để đạt được k phần tử (so với số phần tử đã có trong current_combination), thì nhánh này không thể tạo thành tổ hợp hợp lệ, ta dừng lại.
- Bước đệ quy:
  - current_combination.push_back(elements[start_index]);: Tạm thời thêm phần tử hiện tại vào tổ hợp.
  - generateCombinationsHelper(elements, k, start_index + 1, current_combination);: Gọi đệ quy để tìm các phần tử còn lại từ vị trí kế tiếp (start_index + 1).
  - current_combination.pop_back();: Backtrack! Xóa phần tử vừa thêm. Điều này là cần thiết để hàm có thể khám phá khả năng không chọn phần tử tại start_index.
  - generateCombinationsHelper(elements, k, start_index + 1, current_combination);: Gọi đệ quy một lần nữa, lần này là để tìm các tổ hợp mà không chứa phần tử tại start_index. Ta vẫn bắt đầu tìm từ start_index + 1.
Cần lưu ý rằng cách triển khai này có một chút khác biệt so với tư duy "chọn/không chọn" đơn thuần. Nó hiệu quả hơn vì chỉ số start_index đảm bảo chúng ta luôn chọn các phần tử có chỉ số lớn hơn phần tử đã chọn trước đó, tự động loại bỏ các hoán vị của cùng một tổ hợp và tránh lặp lại. (Cách code trên thực tế chỉ cần gọi đệ quy 1 lần sau khi pop_back nếu tư duy là "đã thử chọn phần tử này rồi, giờ thử không chọn nó bằng cách đi tiếp").

Một cách tiếp cận phổ biến khác cho Combinations là: Tại bước start_index, ta chọn một phần tử elements[i] với i >= start_index. Sau đó gọi đệ quy để tìm k-1 phần tử còn lại từ vị trí i+1. Cách này rõ ràng hơn với tư duy "chọn" từ các phần tử còn lại. Hãy xem xét cách này:

#include <iostream>
#include <vector>
#include <string>

void generateCombinationsHelper_v2(const vector<int>& elements, int k, int start_index,
                                   vector<int>& current_combination) {
    // Điều kiện dừng: Nếu đã đủ k phần tử trong tổ hợp hiện tại
    if (current_combination.size() == k) {
        cout << "{ ";
        for (size_t i = 0; i < current_combination.size(); ++i) {
            cout << current_combination[i] << (i == current_combination.size() - 1 ? "" : ", ");
        }
        cout << " }" << endl;
        return;
    }

    // Bước đệ quy: Chọn phần tử tiếp theo từ start_index trở đi
    // Duyệt qua tất cả các phần tử có thể chọn làm phần tử tiếp theo
    for (int i = start_index; i < elements.size(); ++i) {
        // Chọn phần tử elements[i]
        current_combination.push_back(elements[i]);

        // Gọi đệ quy để tìm k-1 phần tử còn lại, bắt đầu từ chỉ số i + 1
        generateCombinationsHelper_v2(elements, k, i + 1, current_combination);

        // Backtrack: Bỏ phần tử elements[i] để thử các lựa chọn khác
        current_combination.pop_back();
    }
}

void generateCombinations_v2(const vector<int>& elements, int k) {
    vector<int> current_combination;
    generateCombinationsHelper_v2(elements, k, 0, current_combination);
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    int k_size = 2;

    cout << "Cac to hop chap " << k_size << " tu tap {1, 2, 3, 4} (using v2):" << endl;
    generateCombinations_v2(nums, k_size);

    k_size = 3;
    cout << "\nCac to hop chap " << k_size << " tu tap {1, 2, 3, 4} (using v2):" << endl;
    generateCombinations_v2(nums, k_size);

    return 0;
}

Giải thích code v2:

generateCombinationsHelper_v2: Tương tự, đây là hàm đệ quy chính.
Điều kiện dừng: Vẫn là khi current_combination.size() đạt k.
Bước đệ quy: Vòng lặp for (int i = start_index; i < elements.size(); ++i) là điểm khác biệt. Vòng lặp này duyệt qua tất cả các phần tử có thể bắt đầu cho phần còn lại của tổ hợp (từ start_index đến hết mảng).
- current_combination.push_back(elements[i]);: Chọn elements[i] làm phần tử tiếp theo trong tổ hợp.
- generateCombinationsHelper_v2(elements, k, i + 1, current_combination);: Gọi đệ quy để tìm k-1 phần tử còn lại, nhưng chỉ xét từ các phần tử sau elements[i] (tại chỉ số i+1) để tránh lặp lại tổ hợp.
- current_combination.pop_back();: Backtrack! Loại bỏ elements[i] để vòng lặp có thể thử chọn phần tử khác (elements[i+1], elements[i+2],...) làm phần tử tiếp theo.

Cả hai cách tiếp cận đều sử dụng đệ quy và backtracking, nhưng cách thứ hai (v2) với vòng lặp for thường được xem là trực quan hơn khi tư duy về việc "chọn" các phần tử từ tập còn lại.

Bài Tập 3: Phát Sinh Tất Cả Hoán Vị (Generate Permutations)

Tương tự như tổ hợp, bài toán phát sinh hoán vị cũng rất phù hợp với đệ quy và backtracking, nhưng có một chút khác biệt về cách tiếp cận.

Mô tả bài toán: Cho một tập hợp các phần tử phân biệt. Hãy viết hàm đệ quy để liệt kê tất cả các cách sắp xếp (hoán vị) của các phần tử đó.
Tư duy đệ quy (sử dụng Backtracking/Swapping): Ta có thể xây dựng hoán vị bằng cách lần lượt cố định từng vị trí. Để tạo hoán vị cho một dãy từ vị trí start_index đến hết:
- Điều kiện dừng (Base Case): Nếu start_index đã bằng kích thước của dãy, tức là tất cả các vị trí đã được cố định, ta đã tạo xong một hoán vị. In hoặc lưu hoán vị này lại.
- Bước đệ quy (Recursive Step): Duyệt qua tất cả các phần tử từ vị trí start_index đến cuối dãy. Đối với mỗi phần tử tại vị trí i:
  1. Hoán đổi phần tử tại start_index với phần tử tại i. Điều này có nghĩa là ta cố định phần tử tại i vào vị trí start_index.
  2. Gọi đệ quy để phát sinh hoán vị cho phần còn lại của dãy, bắt đầu từ vị trí start_index + 1.
  3. Quay lui (Backtrack): Hoán đổi lại phần tử tại start_index với phần tử tại i. Thao tác này là cần thiết để trả dãy về trạng thái ban đầu, cho phép vòng lặp thử cố định các phần tử khác vào vị trí start_index.
Code minh họa:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Cho swap

void generatePermutationsHelper(vector<int>& elements, int start_index) {
    // Điều kiện dừng: Nếu start_index đã bằng kích thước mảng
    if (start_index == elements.size()) {
        cout << "[ ";
        for (size_t i = 0; i < elements.size(); ++i) {
            cout << elements[i] << (i == elements.size() - 1 ? "" : ", ");
        }
        cout << " ]" << endl;
        return; // Đã tìm thấy 1 hoán vị, dừng nhánh này
    }

    // Bước đệ quy: Duyệt qua các phần tử từ start_index đến hết
    for (int i = start_index; i < elements.size(); ++i) {
        // 1. Chọn elements[i] để đặt vào vị trí start_index (bằng cách swap)
        swap(elements[start_index], elements[i]);

        // 2. Gọi đệ quy để phát sinh hoán vị cho phần còn lại (từ start_index + 1)
        generatePermutationsHelper(elements, start_index + 1);

        // 3. Backtrack: Hoàn trả mảng về trạng thái trước khi swap để thử các lựa chọn khác
        swap(elements[start_index], elements[i]);
    }
}

void generatePermutations(vector<int>& elements) {
    generatePermutationsHelper(elements, 0); // Bắt đầu từ vị trí 0
}

int main() {
    vector<int> nums = {1, 2, 3};

    cout << "Cac hoan vi cua tap {1, 2, 3}:" << endl;
    generatePermutations(nums);

    vector<int> letters = {'A', 'B', 'C', 'D'};
     cout << "\nCac hoan vi cua tap {'A', 'B', 'C', 'D'}:" << endl;
    // Chú ý: Để in char, ta có thể đổi kiểu vector hoặc ép kiểu khi in
    // Ở đây giữ vector<int> cho đơn giản, in ra mã ASCII hoặc giá trị số.
    // Nếu muốn in ký tự, cần vector<char>
    vector<char> char_letters = {'A', 'B', 'C', 'D'};
    void generatePermutationsHelper_char(vector<char>& elements, int start_index); // Forward declaration
    auto generatePermutations_char = [&](vector<char>& elements) {
        generatePermutationsHelper_char(elements, 0);
    };
    generatePermutations_char(char_letters);


    return 0;
}

// Implement helper for char vector
void generatePermutationsHelper_char(vector<char>& elements, int start_index) {
    if (start_index == elements.size()) {
        cout << "[ ";
        for (size_t i = 0; i < elements.size(); ++i) {
            cout << elements[i] << (i == elements.size() - 1 ? "" : ", ");
        }
        cout << " ]" << endl;
        return;
    }

    for (int i = start_index; i < elements.size(); ++i) {
        swap(elements[start_index], elements[i]);
        generatePermutationsHelper_char(elements, start_index + 1);
        swap(elements[start_index], elements[i]); // Backtrack
    }
}

Giải thích code:
- Hàm generatePermutationsHelper nhận vector các phần tử (elements) và chỉ số bắt đầu (start_index) của phần dãy cần hoán vị.
- Điều kiện dừng: Khi start_index bằng kích thước của vector, nghĩa là tất cả các vị trí đã được cố định, ta in ra hoán vị hiện tại và trở về.
- Bước đệ quy:
  - Vòng lặp for (int i = start_index; i < elements.size(); ++i): Duyệt qua các phần tử từ start_index đến cuối mảng.
  - swap(elements[start_index], elements[i]);: Hoán đổi phần tử ở vị trí start_index với phần tử ở vị trí i. Thao tác này đưa elements[i] lên vị trí hiện tại đang xét.
  - generatePermutationsHelper(elements, start_index + 1);: Gọi đệ quy để xử lý phần còn lại của mảng (từ start_index + 1), nơi các phần tử chưa được cố định vị trí.
  - swap(elements[start_index], elements[i]);: Backtrack! Hoán đổi lại để khôi phục mảng về trạng thái trước khi cố định elements[i] vào vị trí start_index. Điều này cho phép vòng lặp tiếp tục và thử cố định các phần tử khác vào vị trí start_index.

Kỹ thuật swap và backtrack này rất hiệu quả để tạo ra tất cả các hoán vị mà không cần sử dụng mảng boolean visited như một số cách tiếp cận khác.

Một Vài Lưu Ý Khi Sử Dụng Đệ Quy Nâng Cao:

Ngăn xếp (Stack Overflow): Đệ quy sử dụng ngăn xếp bộ nhớ để lưu trữ các lời gọi hàm. Với các bài toán có chiều sâu đệ quy lớn, bạn có thể gặp lỗi tràn ngăn xếp (Stack Overflow). Hãy cẩn trọng với dữ liệu đầu vào có kích thước quá lớn.
Hiệu quả: Đôi khi, giải pháp đệ quy tuy thanh lịch nhưng có thể kém hiệu quả hơn so với giải pháp lặp (iterative), đặc biệt nếu cùng một bài toán con được giải nhiều lần (như trong tính Fibonacci cơ bản mà không có ghi nhớ - memoization). Các ví dụ trên đã được chọn lọc để đệ quy thể hiện rõ sức mạnh của nó.
Tư duy: Quan trọng nhất là rèn luyện khả năng nhìn nhận một vấn đề lớn có thể được phân rã thành các vấn đề con tương tự chính nó. Đây là chìa khóa để áp dụng đệ quy thành công.

Thử Thách Thêm:

Để thực sự thành thạo, hãy thử áp dụng đệ quy cho các bài toán khác như:

Tìm kiếm đường đi trong mê cung (có vật cản, đích, sử dụng backtracking).
Bài toán N-Queens (đặt N quân hậu trên bàn cờ N x N sao cho không quân hậu nào ăn nhau).
Tính giá trị của một biểu thức toán học dạng cây.
Duyệt cây nhị phân (Inorder, Preorder, Postorder Traversal).

Comments

There are no comments at the moment.