Thuật toán sinh nhị phân

C++:

#include <iostream>

using namespace std;

void generateBinaryStrings(int binaryArray[], int index, int n) {
    if (index == n) {
        for (int i = 0; i < n; i++) {
            cout << binaryArray[i];
        }
        cout << endl;
        return;
    }

    for (int bit = 0; bit <= 1; bit++) {
        binaryArray[index] = bit;
        generateBinaryStrings(binaryArray, index + 1, n);
    }
}

int main() {
    int n = 3; // Chiều dài của dãy nhị phân
    int binaryArray[3]; // Mảng tĩnh để lưu trữ dãy nhị phân

    generateBinaryStrings(binaryArray, 0, n);

    return 0;
}

Giải thích mã nguồn:

1. Hàm generateBinaryStrings:

   • Chức năng: Sinh tất cả các dãy nhị phân có chiều dài n sử dụng phương pháp quay lui.
   • Tham số:
     • binaryArray: Mảng tĩnh lưu trữ dãy nhị phân hiện tại.
     • index: Vị trí hiện tại trong dãy nhị phân.
     • n: Chiều dài của dãy nhị phân.
   • Mô tả:
     • Nếu index bằng n, nghĩa là đã tạo được một dãy nhị phân hoàn chỉnh, in ra dãy đó.
     • Nếu không, duyệt qua hai giá trị có thể (0 và 1).
     • Gán giá trị bit vào binaryArray tại vị trí index.
     • Gọi đệ quy để tiếp tục tạo dãy nhị phân cho vị trí tiếp theo (index + 1).

2. Hàm main:

   • Chức năng: Điểm bắt đầu của chương trình.
   • Mô tả:
     • Khởi tạo chiều dài của dãy nhị phân n là 3.
     • Khởi tạo mảng tĩnh binaryArray với kích thước n.
     • Gọi hàm generateBinaryStrings để sinh và in ra tất cả các dãy nhị phân có chiều dài n.