Bài 11.1: Sinh các cấu hình nhị phân

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của FullhouseDev! Hôm nay, chúng ta sẽ cùng nhau khám phá một bài toán cơ bản nhưng cực kỳ quan trọng trong lĩnh vực tổ hợp: sinh tất cả các cấu hình nhị phân độ dài n.

Cấu hình nhị phân độ dài n đơn giản là một chuỗi gồm n ký tự, mỗi ký tự chỉ có thể là '0' hoặc '1'. Ví dụ, với n = 3, các cấu hình nhị phân có thể là "000", "001", "010", "011", "100", "101", "110", "111".

Tại sao bài toán này lại quan trọng?

Nó là nền tảng cho nhiều bài toán tổ hợp khác (ví dụ: sinh tập con, sinh hoán vị có lặp...).
Nó minh họa rõ ràng hai kỹ thuật giải thuật phổ biến: lặp (iteration) và đệ quy/quay lui (recursion/backtracking).
Trong thực tế, cấu hình nhị phân có thể biểu diễn các tập hợp con, trạng thái bật/tắt của n công tắc, hoặc các lựa chọn nhị phân trong nhiều tình huống.

Với độ dài n, có chính xác $2^n$ cấu hình nhị phân khác nhau. Mục tiêu của chúng ta là liệt kê (sinh) ra tất cả các cấu hình này một cách hệ thống.

Chúng ta sẽ cùng nhau tìm hiểu hai cách tiếp cận chính để giải quyết bài toán này bằng C++.

Phương pháp 1: Sinh bằng cách duyệt số (Phương pháp lặp)

Ý tưởng của phương pháp này cực kỳ trực quan và dựa trên mối liên hệ giữa số nguyên không âm và biểu diễn nhị phân của chúng. Các số nguyên từ 0 đến $2^n - 1$ khi được biểu diễn dưới dạng nhị phân với đủ n chữ số (có thể thêm các chữ số '0' ở đầu) sẽ tạo ra chính xác tất cả $2^n$ cấu hình nhị phân độ dài n một cách duy nhất.

Ví dụ với n = 3:

Số 0 (hệ 10) -> 000 (hệ 2, đủ 3 chữ số)
Số 1 (hệ 10) -> 001 (hệ 2, đủ 3 chữ số)
Số 2 (hệ 10) -> 010 (hệ 2, đủ 3 chữ số)
Số 3 (hệ 10) -> 011 (hệ 2, đủ 3 chữ số)
Số 4 (hệ 10) -> 100 (hệ 2, đủ 3 chữ số)
Số 5 (hệ 10) -> 101 (hệ 2, đủ 3 chữ số)
Số 6 (hệ 10) -> 110 (hệ 2, đủ 3 chữ số)
Số 7 (hệ 10) -> 111 (hệ 2, đủ 3 chữ số)

Chúng ta thấy rằng việc sinh các cấu hình nhị phân độ dài n quy về việc duyệt các số nguyên từ 0 đến $2^n - 1$ và chuyển chúng sang dạng nhị phân đủ n bit.

Triển khai bằng C++

Chúng ta có thể dùng một vòng lặp đơn giản từ 0 đến $2^n - 1$. Bên trong vòng lặp, chúng ta cần một cách để chuyển số nguyên hiện tại sang chuỗi nhị phân độ dài n.

Dưới đây là cách triển khai sử dụng vòng lặp và thao tác bit để chuyển đổi số:

#include <iostream>
#include <vector>
#include <cmath>    // Để dùng hàm pow (mặc dù có thể thay bằng dịch bit)
#include <string>
#include <algorithm> // Để dùng hàm reverse

// Hàm chuyển số nguyên dec sang chuỗi nhị phân độ dài n
std::string decimalToBinaryString(int dec, int n) {
    if (n <= 0) return ""; // n phải là số dương

    std::string binary = "";
    // Lặp n lần để lấy chính xác n bit, từ bit LSB đến MSB
    for (int i = 0; i < n; ++i) {
        // dec >> i dịch bit thứ i của dec về vị trí cuối cùng
        // & 1 kiểm tra bit cuối cùng đó là 0 hay 1
        if ((dec >> i) & 1) {
            binary += '1';
        } else {
            binary += '0';
        }
    }
    // Các bit được thêm vào theo thứ tự ngược (LSB trước). Cần đảo ngược chuỗi.
    std::reverse(binary.begin(), binary.end());
    return binary;
}

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

    if (n <= 0) {
        std::cerr << "n phai la so duong." << std::endl;
        return 1;
    }

    // Tính số lượng cấu hình: 2^n. Dùng 1 << n hiệu quả hơn pow(2, n)
    // Cần cẩn thận với tràn số nếu n quá lớn (với int, giới hạn khoảng 31-32)
    int num_configs = 1 << n;
    // Nếu n lớn, có thể dùng long long và cẩn thận với 1LL << n

    std::cout << "--- Phuong phap lap (duyet so) ---" << std::endl;
    for (int i = 0; i < num_configs; ++i) {
        // Chuyển số i sang chuỗi nhị phân độ dài n và in ra
        std::cout << decimalToBinaryString(i, n) << std::endl;
    }

    // Ví dụ với n = 3:
    // i = 0 -> decimalToBinaryString(0, 3) -> "000"
    // i = 1 -> decimalToBinaryString(1, 3) -> "001"
    // ...
    // i = 7 -> decimalToBinaryString(7, 3) -> "111"

    return 0;
}

Giải thích code phương pháp lặp:

#include: Chúng ta cần <iostream> cho nhập/xuất, <vector> (không dùng trực tiếp ở đây nhưng thường hữu ích), <cmath> cho pow (hoặc dùng dịch bit), <string> cho làm việc với chuỗi, và <algorithm> cho hàm std::reverse.
decimalToBinaryString(int dec, int n): Hàm này nhận một số nguyên dec và độ dài n mong muốn.
- Nó tạo một chuỗi rỗng binary.
- Vòng lặp for (int i = 0; i < n; ++i) lặp n lần để trích xuất n bit từ số dec.
- dec >> i dịch bit thứ i (tính từ phải sang, bắt đầu từ 0) của dec về vị trí cuối cùng (bit LSB).
- & 1 thực hiện phép AND với 1. Kết quả là 1 nếu bit cuối cùng là 1, và 0 nếu bit cuối cùng là 0. Đây là cách kiểm tra giá trị của một bit cụ thể.
- Dựa vào kết quả, chúng ta thêm '1' hoặc '0' vào chuỗi binary.
- Quan trọng: Cách này lấy các bit từ LSB đến MSB, nên chuỗi binary ban đầu sẽ bị ngược so với thứ tự thông thường. Ví dụ, số 3 (nhị phân 011) với n=3 sẽ tạo ra chuỗi "110". Do đó, cần dùng std::reverse(binary.begin(), binary.end()) để đảo ngược chuỗi về đúng thứ tự MSB...LSB.
main():
- Đọc giá trị n từ người dùng.
- Tính num_configs = 1 << n. Phép dịch bit 1 << n tương đương với $2^n$ nhưng hiệu quả hơn. Lưu ý về giới hạn của kiểu int (khoảng 31-32 cho n).
- Vòng lặp for (int i = 0; i < num_configs; ++i) duyệt qua tất cả các số nguyên từ 0 đến $2^n - 1$.
- Trong mỗi lần lặp, gọi decimalToBinaryString(i, n) để lấy chuỗi nhị phân tương ứng và in ra.

Phương pháp lặp này đơn giản để hiểu và triển khai trực tiếp. Tuy nhiên, nó có thể ít linh hoạt hơn khi chúng ta muốn thêm các ràng buộc hoặc điều kiện phức tạp vào quá trình sinh cấu hình (ví dụ: chỉ sinh các cấu hình có k bit 1). Đó là lúc phương pháp thứ hai trở nên hữu ích hơn.

Phương pháp 2: Sinh bằng Đệ quy (Phương pháp Quay lui - Backtracking)

Phương pháp đệ quy, cụ thể là kỹ thuật quay lui, tiếp cận bài toán theo hướng xây dựng từng phần tử của cấu hình. Chúng ta sẽ xây dựng cấu hình từ vị trí đầu tiên đến vị trí cuối cùng. Tại mỗi vị trí, chúng ta có các lựa chọn (ở đây là '0' hoặc '1').

Ý tưởng chính:

Chúng ta cần một hàm đệ quy nhận vào vị trí hiện tại (k) mà chúng ta đang xem xét để điền ký tự.
Hàm này sẽ thử đặt '0' vào vị trí k, sau đó gọi đệ quy để xử lý vị trí tiếp theo (k+1).
Sau khi nhánh đệ quy với '0' kết thúc (tức là đã hoàn thành tất cả các cấu hình bắt đầu bằng lựa chọn đó), chúng ta "quay lui" và thử đặt '1' vào vị trí k, rồi lại gọi đệ quy cho vị trí k+1.
Trường hợp cơ sở (base case) của đệ quy là khi chúng ta đã điền hết tất cả n vị trí. Khi đó, chúng ta có một cấu hình hoàn chỉnh và in nó ra.

Triển khai bằng C++

Chúng ta sẽ dùng một mảng (hoặc std::vector) để lưu trữ cấu hình nhị phân đang được xây dựng.

#include <iostream>
#include <vector>
#include <string> // Để in chuỗi

// Sử dụng vector để lưu cấu hình hiện tại. Các phần tử là 0 hoặc 1.
std::vector<int> current_config;
int N; // Độ dài mong muốn của cấu hình

// Hàm đệ quy để sinh cấu hình tại vị trí k (từ 0 đến N-1)
void generateBinaryRecursive(int k) {
    // Trường hợp cơ sở: Đã điền xong N vị trí (k đạt đến N)
    if (k == N) {
        // In cấu hình hiện tại ra màn hình
        for (int i = 0; i < N; ++i) {
            std::cout << current_config[i];
        }
        std::cout << std::endl;
        return; // Kết thúc nhánh đệ quy này
    }

    // Bước đệ quy: Tại vị trí k, thử các lựa chọn

    // Lựa chọn 1: Đặt '0' vào vị trí k
    current_config[k] = 0;
    generateBinaryRecursive(k + 1); // Đệ quy để điền vị trí tiếp theo (k+1)

    // Lựa chọn 2: Đặt '1' vào vị trí k
    current_config[k] = 1;
    generateBinaryRecursive(k + 1); // Đệ quy để điền vị trí tiếp theo (k+1)

    // Lưu ý: Trong bài toán sinh cấu hình nhị phân đơn giản này, chúng ta không cần
    // "undo" (quay lui) giá trị của current_config[k] sau khi gọi đệ quy,
    // vì giá trị này sẽ bị ghi đè ở bước thử lựa chọn tiếp theo (hoặc khi quay về
    // bước đệ quy cha). Tuy nhiên, trong các bài toán quay lui phức tạp hơn,
    // việc "undo" là rất quan trọng để trạng thái được phục hồi đúng.
}

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

    if (N <= 0) {
        std::cerr << "n phai la so duong." << std::endl;
        return 1;
    }

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

    std::cout << "--- Phuong phap de quy (Quay lui) ---" << std::endl;
    // Bắt đầu quá trình sinh từ vị trí đầu tiên (chỉ số 0)
    generateBinaryRecursive(0);

    // Ví dụ với n = 3:
    // generateBinaryRecursive(0)
    //  -> current_config[0] = 0; generateBinaryRecursive(1)
    //     -> current_config[1] = 0; generateBinaryRecursive(2)
    //        -> current_config[2] = 0; generateBinaryRecursive(3) -> Base case, print "000"
    //        -> current_config[2] = 1; generateBinaryRecursive(3) -> Base case, print "001"
    //     -> current_config[1] = 1; generateBinaryRecursive(2)
    //        -> current_config[2] = 0; generateBinaryRecursive(3) -> Base case, print "010"
    //        -> current_config[2] = 1; generateBinaryRecursive(3) -> Base case, print "011"
    //  -> current_config[0] = 1; generateBinaryRecursive(1)
    //     -> ... (tương tự cho các cấu hình bắt đầu bằng 1)
    //        -> ... print "100", "101", "110", "111"

    return 0;
}

Giải thích code phương pháp đệ quy:

std::vector<int> current_config; và int N;: Biến toàn cục (hoặc có thể truyền qua tham số) để lưu trữ cấu hình đang được xây dựng (current_config) và độ dài mong muốn (N).
generateBinaryRecursive(int k): Hàm đệ quy chính.
- k: Chỉ số của vị trí hiện tại trong cấu hình mà chúng ta đang xem xét (từ 0 đến N-1).
- if (k == N): Đây là trường hợp cơ sở. Khi k bằng N, điều đó có nghĩa là chúng ta đã thành công trong việc điền giá trị vào các vị trí từ 0 đến N-1. Cấu hình trong current_config đã hoàn chỉnh. Chúng ta duyệt qua vector và in nó ra, sau đó return để kết thúc nhánh đệ quy này và quay về bước trước đó.
- current_config[k] = 0; generateBinaryRecursive(k + 1);: Đây là bước đệ quy đầu tiên. Chúng ta thử đặt giá trị 0 vào vị trí k của cấu hình, sau đó gọi đệ quy cho vị trí tiếp theo k + 1. Lệnh gọi này sẽ tiếp tục quá trình điền các vị trí còn lại.
- current_config[k] = 1; generateBinaryRecursive(k + 1);: Sau khi tất cả các cấu hình có tiền tố giống nhau và bit thứ k là 0 đã được sinh ra (khi generateBinaryRecursive(k + 1) trả về), chúng ta thử lựa chọn thứ hai: đặt giá trị 1 vào vị trí k và lại gọi đệ quy cho k + 1.
- Khái niệm Quay lui: Mặc dù không có lệnh "undo" rõ ràng (current_config[k] = ...), việc ghi đè giá trị tại current_config[k] cho lựa chọn tiếp theo (từ 0 sang 1) và việc các hàm đệ quy riêng biệt xử lý các nhánh khác nhau của cây quyết định chính là bản chất của quay lui. Chúng ta thử một lựa chọn, khám phá hết mọi khả năng từ lựa chọn đó, sau đó "quay lại" điểm quyết định và thử lựa chọn khác.
main():
- Đọc N.
- current_config.resize(N): Cấp phát bộ nhớ cho vector để lưu trữ N phần tử.
- generateBinaryRecursive(0): Bắt đầu quá trình đệ quy từ vị trí đầu tiên (chỉ số 0).

Phương pháp đệ quy (quay lui) này minh họa kỹ thuật giải quyết vấn đề bằng cách chia nhỏ nó thành các bài toán con tương tự (sinh phần còn lại của cấu hình) và khám phá các không gian trạng thái (cây quyết định của các lựa chọn tại mỗi vị trí). Nó mạnh mẽ hơn khi cần thêm các ràng buộc, vì bạn chỉ cần thêm các điều kiện kiểm tra trước khi thực hiện lựa chọn hoặc trước khi đi vào bước đệ quy tiếp theo.

So sánh hai phương pháp

Phương pháp lặp (Duyệt số):
- Ưu điểm: Đơn giản, dễ hiểu, không tốn bộ nhớ cho stack call đệ quy (ít nguy cơ Stack Overflow cho n lớn trong giới hạn kiểu dữ liệu số nguyên).
- Nhược điểm: Khó mở rộng cho các bài toán có ràng buộc phức tạp hơn. Việc chuyển đổi số sang nhị phân có thể không phải là thao tác bit đơn giản nếu cần thêm điều kiện.
Phương pháp đệ quy (Quay lui):
- Ưu điểm: Minh họa rõ ràng tư duy quay lui, rất dễ mở rộng để thêm các điều kiện hoặc biến thể khác của bài toán (ví dụ: chỉ sinh cấu hình có k bit 1, cấu hình không có hai bit 1 liên tiếp...). Mã thường cảm giác tự nhiên hơn khi mô tả quá trình xây dựng đối tượng.
- Nhược điểm: Tốn bộ nhớ cho stack call đệ quy, có thể gây Stack Overflow nếu n quá lớn.

Bài tập ví dụ:

[DSA-ThuatToanSinh].Tập quân sự.

Tại Chương Mỹ Resort, vào nửa đêm, cả trung đội nhận lệnh tập trung ở sân. Mỗi chiến sỹ được đánh số từ 1 đến N (1< N <40). Giám thị yêu cầu chọn ra một dãy K chiến sỹ để tập đội ngũ và cứ lần lượt duyệt hết tất cả các khả năng chọn K người như vậy từ nhỏ đến lớn (theo số thứ tự). Bài toán đặt ra là cho một nhóm K chiến sỹ hiện đang phải tập đội ngũ, hãy tính xem trong lượt chọn K người tiếp theo thì mấy người trong nhóm cũ sẽ được tạm nghỉ. Nếu đã là nhóm cuối cùng thì tất cả đều sẽ được nghỉ.

Input Format

Dữ liệu vào: Dòng đầu ghi số bộ test, không quá 20. Mỗi bộ test viết trên hai dòng Dòng 1: hai số nguyên dương N và K (K Dòng 2 ghi K số thứ tự của các chiến sỹ đang phải tập đội ngũ (viết từ nhỏ đến lớn)

Constraints

Output Format

Với mỗi bộ dữ liệu in ra số lượng chiến sỹ được tạm nghỉ.

Ví dụ:

Dữ liệu vào

Dữ liệu ra

1
2
4

Okay, đây là hướng dẫn giải bài "Tập quân sự" (DSA-ThuatToanSinh) bằng C++ một cách ngắn gọn, không đưa code hoàn chỉnh:

Hiểu bài toán: Cho một tổ hợp K chiến sỹ hiện tại (đã được sắp xếp tăng dần). Cần tìm tổ hợp K chiến sỹ tiếp theo trong thứ tự từ điển, và đếm xem có bao nhiêu chiến sỹ trong tổ hợp hiện tại không có mặt trong tổ hợp tiếp theo. Nếu tổ hợp hiện tại là cuối cùng, tất cả chiến sỹ hiện tại được nghỉ.
Phương pháp chính:
- Sử dụng thuật toán sinh tổ hợp kế tiếp theo thứ tự từ điển.
- So sánh tổ hợp hiện tại và tổ hợp kế tiếp để đếm số chiến sỹ "được nghỉ".
Các bước thực hiện:
- Đọc N, K và K số thứ tự của K chiến sỹ hiện tại (lưu vào một mảng/vector, gọi là current_comb).
- Tạo một bản sao của current_comb để thực hiện việc sinh tổ hợp kế tiếp (gọi là next_comb).
- Sinh tổ hợp kế tiếp (next_comb):
  - Tìm vị trí i lớn nhất (từ K-1 về 0) sao cho phần tử tại vị trí i (next_comb[i]) nhỏ hơn giá trị tối đa có thể có tại vị trí đó. Giá trị tối đa tại vị trí i là N - (K - 1 - i).
  - Nếu không tìm thấy vị trí i nào như vậy (tức là next_comb[i] == N - (K - 1 - i) cho mọi i từ K-1 về 0), thì current_comb là tổ hợp cuối cùng. Số chiến sỹ được nghỉ là K. In ra K và kết thúc cho bộ test này.
  - Nếu tìm thấy vị trí i:
    - Tăng giá trị tại next_comb[i] lên 1.
    - Đặt các phần tử từ vị trí i+1 đến K-1 thành các giá trị liên tiếp tăng dần bắt đầu từ next_comb[i] + 1. Tức là next_comb[j] = next_comb[i] + (j - i) cho j từ i+1 đến K-1.
- Tính số lượng chiến sỹ được nghỉ: (Áp dụng khi không phải là tổ hợp cuối cùng)
  - Số chiến sỹ được nghỉ = K - (Số lượng chiến sỹ chung giữa current_comb và next_comb).
  - Để đếm số chiến sỹ chung giữa hai mảng/vector đã sắp xếp (current_comb và next_comb), dùng phương pháp hai con trỏ.
  - Khởi tạo hai con trỏ p1 = 0 (cho current_comb) và p2 = 0 (cho next_comb) và biến đếm common_count = 0.
  - Trong khi p1 < K và p2 < K:
    - Nếu current_comb[p1] == next_comb[p2]: Tăng common_count, tăng p1, tăng p2.
    - Nếu current_comb[p1] < next_comb[p2]: Tăng p1.
    - Nếu current_comb[p1] > next_comb[p2]: Tăng p2.
  - Kết quả là K - common_count. In ra kết quả này.
Lưu ý: Kích thước N và K nhỏ (N < 40) nên việc lưu trữ mảng/vector và các thao tác cơ bản đều hiệu quả. Thuật toán sinh tổ hợp kế tiếp là trọng tâm của bài toán. Việc đếm phần tử chung giữa hai tập hợp có thể làm hiệu quả bằng cách lợi dụng tính chất đã sắp xếp của chúng.

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

Comments

There are no comments at the moment.