Bài 15.5: Bài tập thực hành kết hợp Vector và đệ quy trong C++

Chào mừng các bạn quay trở lại với chuỗi bài học C++ của FullhouseDev! Sau khi đã làm quen với vector - một container động mạnh mẽ và kỹ thuật đệ quy (recursion) - một công cụ giải thuật thanh lịch, hôm nay chúng ta sẽ cùng khám phá sự kết hợp đầy uy lực của cả hai.

Tại sao lại kết hợp vector và đệ quy? Đệ quy thường được sử dụng để giải quyết các vấn đề có cấu trúc lặp lại hoặc phân nhánh. Rất nhiều bài toán dạng này yêu cầu chúng ta xây dựng, lưu trữ, hoặc xử lý các tập hợp dữ liệu thay đổi qua mỗi bước đệ quy. vector chính là sự lựa chọn hoàn hảo cho việc này bởi tính linh hoạt trong kích thước và khả năng lưu trữ các chuỗi dữ liệu động.

Trong bài viết này, chúng ta sẽ đi sâu vào một số ví dụ thực tế để thấy cách vector và đệ quy cùng nhau tạo nên những giải pháp elegant cho các vấn đề tưởng chừng phức tạp.

Khi nào sự kết hợp này toả sáng?

Sự kết hợp giữa vector và đệ quy thường hữu ích trong các tình huống sau:

  1. Tạo và lưu trữ các kết quả trung gian hoặc cuối cùng: Đệ quy khám phá các khả năng, và mỗi khả năng được xây dựng (ví dụ: một tập con, một đường đi, một hoán vị) có thể được lưu trữ trong một vector.
  2. Duyệt hoặc xử lý các cấu trúc dữ liệu dạng cây/đồ thị (ẩn): Nhiều bài toán tổ hợp (như tạo tập con, hoán vị) có thể hình dung như việc duyệt một cây quyết định. vector có thể được dùng để lưu trữ "đường đi" hiện tại trong cây này.
  3. Quản lý trạng thái: Trong các bài toán quay lui (backtracking), vector thường được dùng để lưu trữ trạng thái hiện tại của giải pháp đang được xây dựng. Khi quay lui, chúng ta thao tác với vector để khôi phục trạng thái trước đó.

Hãy cùng xem qua một vài ví dụ cụ thể.

Ví dụ 1: Tạo tất cả Tập con (Subsets)

Bài toán: Cho một tập hợp các số nguyên khác nhau, hãy tạo ra tất cả các tập con của tập hợp đó.

Đây là một bài toán kinh điển có thể giải quyết bằng đệ quy và kỹ thuật quay lui. Chúng ta có thể hình dung quá trình tạo tập con như việc đi qua từng phần tử của tập đầu vào và đưa ra quyết định: bao gồm phần tử này trong tập con hiện tại hay không bao gồm.

Chúng ta sẽ sử dụng một vector để lưu trữ tập con đang được xây dựng (currentSubset) và một vector các vector để lưu trữ tất cả các tập con tìm được (result).

#include <iostream>
#include <vector>

using namespace std;

void timTapCon(int i, vector<int>& tapCon, vector<vector<int>>& kq, const vector<int>& a) {
    if (i == a.size()) {
        kq.push_back(tapCon);
        return;
    }

    timTapCon(i + 1, tapCon, kq, a); // Không bao gồm a[i]

    tapCon.push_back(a[i]); // Bao gồm a[i]
    timTapCon(i + 1, tapCon, kq, a);
    tapCon.pop_back(); // Quay lui
}

int main() {
    vector<int> a = {1, 2, 3};
    vector<vector<int>> tatCaTapCon;
    vector<int> tapConHienTai;

    timTapCon(0, tapConHienTai, tatCaTapCon, a);

    cout << "Tat ca tap con cua {1, 2, 3} la:" << endl;
    for (const auto& tc : tatCaTapCon) {
        cout << "[ ";
        for (int so : tc) {
            cout << so << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

Giải thích:

  • Hàm timTapCon nhận vào chỉ mục i đang xét, tapCon (vector đang xây dựng), kq (vector chứa kết quả cuối cùng), và a (vector gốc).
  • Base Case: Khi i == a.size(), tức là chúng ta đã duyệt qua hết các phần tử của a, tapCon lúc này là một tập con hoàn chỉnh, ta thêm nó vào kq.
  • Recursive Step: Tại mỗi i, có hai khả năng:
    • Gọi đệ quy với i + 1 mà không thêm a[i] vào tapCon.
    • Gọi đệ quy với i + 1 sau khi thêm a[i] vào tapCon.
  • Backtrack: Sau khi thực hiện nhánh "bao gồm", chúng ta dùng tapCon.pop_back() để loại bỏ a[i]. Điều này rất quan trọng để đảm bảo tapCon trở lại trạng thái ban đầu trước khi khám phá các nhánh đệ quy khác (ví dụ: không bao gồm a[i]). vector ở đây được dùng để lưu trữ trạng thái đường đi hiện tại trong cây quyết định.

Kết quả của đoạn code trên sẽ là:

Tat ca tap con cua {1, 2, 3} la:
[ ]
[ 3 ]
[ 2 ]
[ 2 3 ]
[ 1 ]
[ 1 3 ]
[ 1 2 ]
[ 1 2 3 ]

(Thứ tự có thể khác tùy cách duyệt, nhưng đủ 8 tập con).

Ví dụ 2: Tạo tất cả Hoán vị (Permutations)

Bài toán: Cho một tập hợp các số nguyên khác nhau, hãy tạo ra tất cả các hoán vị có thể có của tập hợp đó.

Tương tự như tập con, bài toán hoán vị cũng có thể giải quyết bằng đệ quy và quay lui. Sự khác biệt là thay vì quyết định có hoặc không có một phần tử, chúng ta quyết định phần tử nào sẽ đặt vào vị trí hiện tại trong hoán vị đang xây dựng.

Chúng ta cần một vector để lưu trữ hoán vị đang được xây dựng (currentPermutation) và một vector boolean (hoặc cách khác) để đánh dấu các phần tử đã sử dụng trong tập gốc.

#include <iostream>
#include <vector>

using namespace std;

void timHoanVi(vector<int>& hv, vector<bool>& sd, vector<vector<int>>& kq, const vector<int>& a) {
    if (hv.size() == a.size()) {
        kq.push_back(hv);
        return;
    }

    for (int i = 0; i < a.size(); ++i) {
        if (!sd[i]) {
            sd[i] = true;
            hv.push_back(a[i]);

            timHoanVi(hv, sd, kq, a);

            hv.pop_back(); // Quay lui
            sd[i] = false; // Quay lui
        }
    }
}

int main() {
    vector<int> a = {1, 2, 3};
    vector<vector<int>> tatCaHoanVi;
    vector<int> hvHienTai;
    vector<bool> daSuDung(a.size(), false);

    timHoanVi(hvHienTai, daSuDung, tatCaHoanVi, a);

    cout << "Tat ca hoan vi cua {1, 2, 3} la:" << endl;
    for (const auto& hv : tatCaHoanVi) {
        cout << "[ ";
        for (int so : hv) {
            cout << so << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

Giải thích:

  • Hàm timHoanVi sử dụng hv (vector đang xây dựng hoán vị) và sd (vector boolean theo dõi các phần tử từ a đã được thêm vào hv).
  • Base Case: Khi kích thước của hv bằng kích thước của a, một hoán vị hoàn chỉnh đã được tạo ra, thêm nó vào kq.
  • Recursive Step: Vòng lặp for duyệt qua tất cả các phần tử trong a. Nếu một phần tử chưa được sử dụng (!sd[i]), chúng ta chọn nó cho vị trí hiện tại trong hoán vị.
  • Sau khi chọn, chúng ta đánh dấu sd[i] = true, thêm a[i] vào hv, và gọi đệ quy.
  • Backtrack: Quan trọng không kém! Sau khi gọi đệ quy trở về, chúng ta hoàn tác việc chọn: loại bỏ phần tử vừa thêm khỏi hv (pop_back()) và đánh dấu nó là chưa sử dụng lại (sd[i] = false). Điều này cho phép các nhánh đệ quy khác chọn các phần tử khác cho vị trí đó. vector hv lưu trữ trạng thái của hoán vị đang được xây dựng.

Kết quả sẽ in ra tất cả 6 hoán vị của {1, 2, 3}:

Tat ca hoan vi cua {1, 2, 3} la:
[ 1 2 3 ]
[ 1 3 2 ]
[ 2 1 3 ]
[ 2 3 1 ]
[ 3 1 2 ]
[ 3 2 1 ]

Ví dụ 3: Tìm tất cả Đường đi từ gốc đến lá trong Cây nhị phân (Sử dụng Vector lưu đường đi)

Mặc dù bản thân cây nhị phân không phải là vector, nhưng nhiều bài toán trên cây sử dụng đệ quy để duyệt và thường cần lưu trữ thông tin liên quan đến đường đi hoặc kết quả thu thập được trong quá trình duyệt. vector là lựa chọn tự nhiên để lưu trữ đường đi hiện tại.

Bài toán: Cho gốc của một cây nhị phân, tìm tất cả các đường đi từ gốc đến các nút lá. Lưu mỗi đường đi dưới dạng một vector các giá trị nút.

Chúng ta sẽ định nghĩa một cấu trúc TreeNode đơn giản và sử dụng đệ quy để duyệt cây, đồng thời dùng một vector để lưu trữ đường đi từ gốc đến nút hiện tại.

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

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

void timDuong(TreeNode* n, vector<int>& duong, vector<vector<int>>& kq) {
    if (!n) {
        return;
    }

    duong.push_back(n->val);

    if (!n->left && !n->right) { // Là nút lá
        kq.push_back(duong);
    } else {
        timDuong(n->left, duong, kq);
        timDuong(n->right, duong, kq);
    }

    duong.pop_back(); // Quay lui
}

int main() {
    TreeNode* goc = new TreeNode(1);
    goc->left = new TreeNode(2);
    goc->right = new TreeNode(3);
    goc->left->right = new TreeNode(5);

    vector<vector<int>> tatCaDuongDi;
    vector<int> duongDiHienTai;

    timDuong(goc, duongDiHienTai, tatCaDuongDi);

    cout << "Tat ca duong di tu goc den la la:" << endl;
    for (const auto& d : tatCaDuongDi) {
        cout << "[ ";
        for (int i = 0; i < d.size(); ++i) {
            cout << d[i] << (i == d.size() - 1 ? "" : " -> ");
        }
        cout << "]" << endl;
    }

    // Dọn dẹp bộ nhớ
    delete goc->left->right;
    delete goc->left;
    delete goc->right;
    delete goc;

    return 0;
}

Giải thích:

  • Hàm timDuong nhận vào nút hiện tại (n), duong (vector lưu đường đi từ gốc đến n) và kq.
  • Base Case: Nếu n là nullptr, ta dừng.
  • Add to Path: Giá trị của n hiện tại được thêm vào duong.
  • Leaf Check: Nếu n là lá, duong đại diện cho một đường đi hoàn chỉnh và được thêm vào kq.
  • Recursive Step: Nếu không phải lá, ta gọi đệ quy cho con trái và con phải.
  • Backtrack: Trước khi hàm kết thúc, giá trị của n hiện tại được xóa khỏi duong. Điều này đảm bảo khi nhánh đệ quy kia được gọi (ví dụ: từ con phải sau khi con trái hoàn thành), duong chỉ chứa các nút trên đường đi từ gốc đến cha của nút hiện tại, sẵn sàng để thêm nút tiếp theo của nhánh đó. vector duong đóng vai trò như một stack lưu trữ đường đi đang khám phá.

Kết quả của đoạn code sẽ là:

``` Tat ca duong di tu goc den la la: [ 1 -> 2 -> 5 ] [ 1 -> 3 ]

Comments

There are no comments at the moment.