Khóa học CTDL và GT

Bài 11.5. Bài tập tổng hợp về các thuật toán sinh

Xin chào các bạn độc giả yêu công nghệ và lập trình của FullhouseDev!

Chúng ta đã cùng nhau đi qua một hành trình thú vị tìm hiểu về các thuật toán sinh cơ bản: sinh cấu hình nhị phân, sinh hoán vị, và sinh tổ hợp. Các thuật toán này đóng vai trò quan trọng trong việc duyệt qua tất cả các trường hợp có thể của một bài toán, thường là cơ sở cho các phương pháp tìm kiếm vét cạn hoặc thuật toán quay lui.

Lý thuyết là nền tảng, nhưng thực hành mới là chìa khóa để nắm vững và áp dụng các thuật toán này. Trong bài viết này, chúng ta sẽ cùng nhau giải quyết một số bài tập tổng hợp, giúp củng cố kiến thức và rèn luyện kỹ năng code C++ của bạn. Hãy cùng bắt tay vào nào!

Bài tập 1: Sinh cấu hình nhị phân độ dài N

Đây là bài toán cơ bản nhất về sinh cấu hình, nhưng là viên gạch đầu tiên vững chắc.

Đề bài: Cho số nguyên dương N. Hãy liệt kê tất cả các dãy nhị phân có độ dài N.

Ví dụ: Với N = 3, các dãy nhị phân là: 000, 001, 010, 011, 100, 101, 110, 111.

Phân tích: Mỗi vị trí trong dãy nhị phân có 2 lựa chọn (0 hoặc 1). Chúng ta có thể dùng phương pháp đệ quy (backtracking) để xây dựng từng vị trí một.

Code C++:

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

using namespace std;

int N;
vector<int> current_config; // Lưu cấu hình hiện tại

// Hàm đệ quy sinh cấu hình nhị phân
void generate_binary_config(int index) {
    // Điều kiện dừng: Đã xây dựng xong dãy có độ dài N
    if (index == N) {
        // In cấu hình hiện tại
        for (int i = 0; i < N; ++i) {
            cout << current_config[i];
        }
        cout << endl;
        return;
    }

    // Thử giá trị 0 cho vị trí index
    current_config[index] = 0;
    generate_binary_config(index + 1); // Đệ quy sang vị trí tiếp theo

    // Thử giá trị 1 cho vị trí index
    current_config[index] = 1;
    generate_binary_config(index + 1); // Đệ quy sang vị trí tiếp theo
}

int main() {
    cout << "Nhap N: ";
    cin >> N;

    current_config.resize(N); // Khởi tạo vector kích thước N

    cout << "Cac cau hinh nhi phan do dai " << N << " la:" << endl;
    generate_binary_config(0); // Bat dau sinh tu vi tri 0

    return 0;
}

Giải thích code:

• Chúng ta dùng một vector<int> current_config để lưu dãy nhị phân đang được xây dựng. Kích thước của vector này là N.
• Hàm generate_binary_config(int index) là hàm đệ quy. index là vị trí hiện tại trong dãy mà chúng ta đang xét (từ 0 đến N-1).
• Base case: Nếu index == N, nghĩa là chúng ta đã chọn xong giá trị cho tất cả N vị trí. Lúc này, current_config chính là một dãy nhị phân hợp lệ, chúng ta in nó ra màn hình và trở về.
• Recursive step: Tại vị trí index, chúng ta có 2 lựa chọn:
  1. Gán current_config[index] = 0. Sau đó gọi đệ quy tới generate_binary_config(index + 1) để tiếp tục xây dựng phần còn lại của dãy.
  2. Gán current_config[index] = 1. Tương tự, gọi đệ quy tới generate_binary_config(index + 1).
• Trong hàm main, chúng ta đọc N, resize vector current_config, và gọi hàm đệ quy bắt đầu từ vị trí 0: generate_binary_config(0).

Bài tập 2: Sinh hoán vị của N phần tử

Hoán vị là một sắp xếp khác nhau của các phần tử. Đây cũng là một bài toán kinh điển.

Đề bài: Cho số nguyên dương N. Hãy liệt kê tất cả các hoán vị của tập hợp {1, 2, ..., N}.

Ví dụ: Với N = 3, các hoán vị là: 123, 132, 213, 231, 312, 321.

Phân tích: Một hoán vị là một dãy gồm N phần tử distinct. Chúng ta có thể nghĩ đến việc "đặt" từng phần tử vào các vị trí. Hoặc đơn giản hơn, trong C++, thư viện <algorithm> cung cấp một hàm rất tiện lợi là std::next_permutation.

Code C++ (Sử dụng std::next_permutation):

#include <iostream>
#include <vector>
#include <numeric> // Cho std::iota
#include <algorithm> // Cho std::sort va std::next_permutation

using namespace std;

int main() {
    int N;
    cout << "Nhap N: ";
    cin >> N;

    // Tao vector chua cac phan tu tu 1 den N
    vector<int> p(N);
    iota(p.begin(), p.end(), 1); // Dien cac gia tri 1, 2, ..., N vao vector p

    cout << "Cac hoan vi cua tap {1, ..., " << N << "} la:" << endl;

    // Sap xep de co hoan vi dau tien (lexicographically smallest)
    sort(p.begin(), p.end());

    // Sinh va in cac hoan vi tiep theo
    do {
        for (int i = 0; i < N; ++i) {
            cout << p[i];
        }
        cout << endl;
    } while (next_permutation(p.begin(), p.end())); // next_permutation tra ve false khi khong con hoan vi nao

    return 0;
}

Giải thích code:

• Chúng ta sử dụng một vector<int> p để lưu hoán vị hiện tại. Ban đầu, chúng ta dùng std::iota để điền các giá trị từ 1 đến N vào vector này, tạo ra hoán vị ban đầu {1, 2, ..., N}.
• Hàm std::sort(p.begin(), p.end()) đảm bảo rằng chúng ta bắt đầu từ hoán vị nhỏ nhất theo thứ tự từ điển (lexicographical order), đó là {1, 2, ..., N}.
• Vòng lặp do...while(next_permutation(p.begin(), p.end())) là cách hiệu quả để duyệt qua tất cả các hoán vị của dãy p.
  • next_permutation(p.begin(), p.end()) cố gắng biến đổi dãy p thành hoán vị kế tiếp nó theo thứ tự từ điển.
  • Nếu tìm thấy hoán vị kế tiếp, nó biến đổi p tại chỗ và trả về true.
  • Nếu p đã là hoán vị cuối cùng (lớn nhất theo từ điển, tức là {N, N-1, ..., 1}), nó biến đổi p thành hoán vị nhỏ nhất ({1, 2, ..., N}) và trả về false, kết thúc vòng lặp.
• Bên trong vòng do...while, chúng ta chỉ việc in ra hoán vị p hiện tại.

Lưu ý: Bạn cũng có thể tự cài đặt sinh hoán vị bằng đệ quy (backtracking), nhưng sử dụng std::next_permutation là cách chuẩn và hiệu quả trong C++ cho bài toán này.

Bài tập 3: Sinh tổ hợp chập K của N phần tử

Bài toán này yêu cầu chọn ra một tập con gồm K phần tử từ một tập N phần tử mà không quan tâm đến thứ tự.

Đề bài: Cho hai số nguyên dương N và K (với 1 ≤ K ≤ N). Hãy liệt kê tất cả các tổ hợp chập K của N phần tử từ tập {1, 2, ..., N}.

Ví dụ: Với N = 4, K = 2, các tổ hợp là: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

Phân tích: Chúng ta cần chọn ra K phần tử. Để tránh các tổ hợp lặp lại (ví dụ {1, 2} và {2, 1} là một tổ hợp), chúng ta có thể quy ước luôn chọn các phần tử theo thứ tự tăng dần. Tức là, nếu chọn a[0], a[1], ..., a[K-1], thì luôn đảm bảo 1 <= a[0] < a[1] < ... < a[K-1] <= N.

Code C++ (Sử dụng đệ quy):

#include <iostream>
#include <vector>

using namespace std;

int N, K;
vector<int> current_combination; // Lưu tổ hợp hiện tại

// Hàm đệ quy sinh tổ hợp
// index: vị trí hiện tại trong tổ hợp đang xây dựng (từ 0 đến K-1)
// start_value: giá trị nhỏ nhất có thể chọn cho vị trí index
void generate_combinations(int index, int start_value) {
    // Điều kiện dừng: Đã chọn đủ K phần tử cho tổ hợp
    if (index == K) {
        // In tổ hợp hiện tại
        cout << "{";
        for (int i = 0; i < K; ++i) {
            cout << current_combination[i] << (i == K - 1 ? "" : ", ");
        }
        cout << "}" << endl;
        return;
    }

    // Thử các giá trị từ start_value đến N
    // Chu y: gia tri lon nhat co the chon tai vi tri index phai dam bao con du cho cac vi tri sau
    // Cac vi tri sau (index+1 den K-1) can (K-1 - index) phan tu nua
    // Phan tu nho nhat co the chon cho vi tri index+1 la current_combination[index] + 1
    // De co du (K-1 - index) phan tu sau, phan tu cuoi cung (o vi tri K-1) phai <= N
    // Vi the, gia tri o vi tri index chi co the toi da la N - (K - 1 - index)
    for (int value = start_value; value <= N - (K - 1 - index); ++value) {
        current_combination[index] = value;
        // De dam bao thu tu tang dan, phan tu tiep theo (o index + 1) phai >= value + 1
        generate_combinations(index + 1, value + 1);
    }
}

int main() {
    cout << "Nhap N: ";
    cin >> N;
    cout << "Nhap K: ";
    cin >> K;

    if (K < 0 || K > N) {
        cout << "K phai nam trong khoang [0, N]." << endl;
        return 1;
    }
    if (K == 0) {
         cout << "{}" << endl; // Chi co mot to hop rong
         return 0;
    }

    current_combination.resize(K); // Khởi tạo vector kích thước K

    cout << "Cac to hop chap " << K << " cua tap {1, ..., " << N << "} la:" << endl;
    generate_combinations(0, 1); // Bat dau chon phan tu cho vi tri 0, gia tri co the chon tu 1

    return 0;
}

Giải thích code:

• current_combination lưu tổ hợp K phần tử đang được xây dựng.
• Hàm generate_combinations(int index, int start_value):
  • index: Vị trí hiện tại trong tổ hợp (từ 0 đến K-1).
  • start_value: Giá trị nhỏ nhất mà phần tử ở vị trí index có thể nhận. Việc này đảm bảo các phần tử được chọn theo thứ tự tăng dần và tránh lặp lại tổ hợp.
• Base case: Nếu index == K, nghĩa là chúng ta đã chọn đủ K phần tử, in tổ hợp ra và trở về.
• Recursive step: Chúng ta dùng vòng lặp để thử gán các giá trị cho current_combination[index].
  • Giá trị bắt đầu là start_value.
  • Giá trị kết thúc là N - (K - 1 - index). Tại sao lại là giá trị này? Vì chúng ta cần đảm bảo rằng vẫn còn đủ các giá trị lớn hơn để điền vào các vị trí còn lại (từ index + 1 đến K - 1). Có K - 1 - index vị trí còn lại. Giá trị nhỏ nhất có thể điền vào vị trí index + 1 là value + 1, vị trí index + 2 là value + 2, ..., vị trí K - 1 là value + (K - 1 - index). Để giá trị cuối cùng không vượt quá N, ta cần value + (K - 1 - index) <= N, suy ra value <= N - (K - 1 - index).
  • Sau khi chọn một value cho current_combination[index], chúng ta gọi đệ quy generate_combinations(index + 1, value + 1). Tham số value + 1 cho lần gọi đệ quy tiếp theo đảm bảo phần tử ở vị trí index + 1 sẽ lớn hơn phần tử ở vị trí index, duy trì thứ tự tăng dần.

Bài tập 4: Sinh cấu hình tổng quát từ tập {1, ..., K}

Đây là mở rộng của bài toán sinh cấu hình nhị phân, nơi mỗi vị trí có nhiều hơn 2 lựa chọn.

Đề bài: Cho hai số nguyên dương N và K. Hãy liệt kê tất cả các dãy có độ dài N, trong đó mỗi phần tử của dãy là một số nguyên thuộc tập {1, 2, ..., K}.

Ví dụ: Với N = 2, K = 3, các dãy là: 11, 12, 13, 21, 22, 23, 31, 32, 33.

Phân tích: Tương tự như sinh cấu hình nhị phân, chúng ta xây dựng dãy theo từng vị trí bằng đệ quy. Điểm khác biệt là mỗi vị trí có K lựa chọn thay vì chỉ 2.

Code C++:

#include <iostream>
#include <vector>

using namespace std;

int N, K;
vector<int> current_general_config; // Lưu cấu hình tổng quát hiện tại

// Hàm đệ quy sinh cấu hình tổng quát
void generate_general_config(int index) {
    // Điều kiện dừng: Đã xây dựng xong dãy có độ dài N
    if (index == N) {
        // In cấu hình hiện tại
        for (int i = 0; i < N; ++i) {
            cout << current_general_config[i];
        }
        cout << endl;
        return;
    }

    // Thử các giá trị từ 1 đến K cho vị trí index
    for (int value = 1; value <= K; ++value) {
        current_general_config[index] = value;
        // Đệ quy sang vị trí tiếp theo
        generate_general_config(index + 1);
    }
}

int main() {
    cout << "Nhap N: ";
    cin >> N;
    cout << "Nhap K: ";
    cin >> K;

    if (K <= 0) {
        cout << "K phai la so duong." << endl;
        return 1;
    }

    current_general_config.resize(N); // Khởi tạo vector kích thước N

    cout << "Cac cau hinh do dai " << N << " tu tap {1, ..., " << K << "} la:" << endl;
    generate_general_config(0); // Bat dau sinh tu vi tri 0

    return 0;
}

Giải thích code:

• current_general_config lưu dãy đang được xây dựng.
• Hàm generate_general_config(int index):
  • index: Vị trí hiện tại (từ 0 đến N-1).
• Base case: Nếu index == N, dãy đã hoàn thành, in ra và trở về.
• Recursive step: Sử dụng vòng lặp để thử tất cả các giá trị từ 1 đến K cho vị trí index. Sau khi gán current_general_config[index] = value, gọi đệ quy generate_general_config(index + 1) để tiếp tục điền giá trị cho vị trí kế tiếp. Quá trình này lặp lại cho mọi giá trị value từ 1 đến K, đảm bảo duyệt qua mọi khả năng.

Bài tập ví dụ:

[DSA-ThuatToanSinh].Mã Gray 3.

Số nhị phân được xem là cách mặc định biểu diễn các số. Tuy nhiên, trong nhiều ứng dụng của điện tử và truyền thông lại dùng một biến thể của mã nhị phân đó là mã Gray. Mã Gray độ dài n có mã đầu tiên là n số 0, mã kế tiếp của nó là một xâu nhị phân độ dài n khác biệt với xâu trước đó một bít. Ví dụ với n=3 ta có 23 mã Gray như sau: 000, 001, 011, 010, 110, 111, 101, 100. Hãy viết chương trình chuyển đổi một xâu mã Gray X có độ dài n thành một xâu mã nhị phân.

Input Format

Dòng đầu tiên là số lượng test T. T dòng kế tiếp ghi lại mỗi dòng một test. Mỗi test là một xâu mã Gray độ dài n. T, n thỏa mãn ràng buộc: 1≤T, n≤10.

Constraints

.

Output Format

Đưa ra kết quả mỗi test theo từng dòng.

Ví dụ:

Dữ liệu vào

2
01001
01110

Dữ liệu ra

01110
01011

Để chuyển đổi một xâu mã Gray sang xâu mã nhị phân tương ứng, ta áp dụng công thức chuyển đổi từng bit từ trái sang phải:

1. Bit đầu tiên (bit trái nhất): Bit đầu tiên của mã nhị phân (B) giống hệt bit đầu tiên của mã Gray (G). Tức là B[0] = G[0].
2. Các bit tiếp theo: Mỗi bit thứ i (với i > 0) của mã nhị phân được tính bằng phép XOR (hoặc phép cộng modulo 2) giữa bit thứ i-1 của mã nhị phân đã tính được và bit thứ i của mã Gray. Tức là B[i] = B[i-1] XOR G[i].

Cách thực hiện trong C++:

1. Đọc số lượng test T.
2. Dùng vòng lặp T lần.
3. Trong mỗi lần lặp:
   • Đọc xâu mã Gray đầu vào (ví dụ: grayString).
   • Tạo một xâu rỗng hoặc một xâu có cùng độ dài để lưu kết quả mã nhị phân (ví dụ: binaryString).
   • Gán ký tự đầu tiên của binaryString bằng ký tự đầu tiên của grayString.
   • Dùng vòng lặp đi từ ký tự thứ hai (chỉ số 1) đến hết xâu grayString.
   • Trong vòng lặp, tại chỉ số i:
     • Lấy giá trị số của bit nhị phân trước đó (binaryString[i-1]) và bit Gray hiện tại (grayString[i]). Chuyển '0' thành 0, '1' thành 1.
     • Thực hiện phép XOR giữa hai giá trị số này.
     • Chuyển kết quả 0 hoặc 1 trở lại thành ký tự '0' hoặc '1'.
     • Thêm ký tự kết quả này vào cuối xâu binaryString.
   • In xâu binaryString ra màn hình, theo sau là xuống dòng.

Lưu ý: Khi thực hiện phép XOR với ký tự '0' và '1', bạn cần chuyển chúng sang giá trị số (0 hoặc 1) trước khi XOR, sau đó chuyển kết quả ngược lại thành ký tự. Ví dụ: ('1' - '0') ^ ('0' - '0') sẽ cho kết quả 1. Sau đó chuyển 1 thành '1'.

Làm thêm nhiều bài tập miễn phí tại đây