Các bước tư duy thuật để “lụm” bài dãy nhị phân

1. Phân tích bài toán

Chúng ta cần liệt kê tất cả các xâu nhị phân có độ dài ( n ).
Mỗi xâu nhị phân gồm các ký tự 0 và 1.

Ví dụ: ( n = 3 )

• Với số đầu tiên, ta có 2 lựa chọn: 0 hoặc 1

  0
  1

• Với số thứ hai, mỗi xâu trước đó lại có 2 lựa chọn nữa:

  00
  01
  10
  11

• Với số thứ ba, ta tiếp tục mở rộng:

  000
  001
  010
  011
  100
  101
  110
  111

Nhận xét:

• Mỗi bước, số lượng xâu tăng gấp đôi.
• Tổng số xâu nhị phân có độ dài ( n ) là ( 2^n ).
• Cấu trúc này phù hợp với thuật toán đệ quy (recursion).

2. Ý tưởng xây dựng thuật toán

• Bắt đầu với một chuỗi rỗng.
• Ở mỗi bước, ta có hai lựa chọn:
  1. Thêm ‘0’ vào chuỗi hiện tại.
  2. Thêm ‘1’ vào chuỗi hiện tại.
• Nếu độ dài chuỗi đạt ( n ) → In kết quả.
• Nếu chưa, ta tiếp tục gọi đệ quy để mở rộng.

3. Xây dựng hàm

#include <bits/stdc++.h>
using namespace std;

void Xau_nhi_phan(int n, string s = "") {
    if (s.size() == n) {
        cout << s << endl;
        return;
    }
    
    // Goi de quy voi 2 nhanh
    Xau_nhi_phan(n, s + "0");
    Xau_nhi_phan(n, s + "1");
}

int main() {
    int n; cin >> n;
    Xau_nhi_phan(n); //Goi ham
    return 0;
}

4. Giải thích thuật toán

Hàm Xau_nhi_phan(n, s)

• Điều kiện dừng: Nếu s.size() == n, in ra s (xâu đã hoàn thành).
• Bước đệ quy: Nếu s.size() < n, ta tiếp tục mở rộng:
  • Thử thêm ‘0’ vào s và gọi đệ quy (Xau_nhi_phan(n, s + "0")).
  • Thử thêm ‘1’ vào s và gọi đệ quy (Xau_nhi_phan(n, s + "1")).

Cây đệ quy cho n = 3

          ""  
 /                   \  
                      "0"                    "1"  
                     /      \            /          \  
                 "00"      "01"        "10"        "11"  
                /   \     /     \     /     \     /     \  
            "000" "001" "010" "011" "100" "101" "110" "111"

• Khi đến tầng cuối (các xâu có độ dài ( n )), ta in kết quả!! (Xin lỗi quý vị nhưng mà tôi vẽ cây xấu quá)

5. Độ phức tạp của thuật toán

• Ở mỗi bước, ta có hai lựa chọn (0 hoặc 1).
• Vì có tổng cộng n bước, số xâu nhị phân sinh ra là ( 2^n ).
• Độ phức tạp thời gian: ( O(2^n) ) (mỗi xâu được tạo và in ra đúng một lần).

6. Tổng kết

✅ Sử dụng đệ quy giúp bài toán đơn giản và dễ hiểu.
✅ Cấu trúc cây nhị phân thể hiện rõ cách sinh xâu.
✅ Giải thuật có thể mở rộng để áp dụng vào các bài toán tương tự.

💡 Có thể tối ưu nếu chỉ cần đếm số lượng xâu thay vì in ra chúng.
💡 Nếu ( n ) quá lớn (ví dụ ( n > 20 )), cần cân nhắc tối ưu hoặc sử dụng phương pháp khác do giới hạn thời gian.

Cảm ơn quý độc giả đã theo dõi

Đề bài

Cho một số nguyên n, yêu cầu in ra tất cả các xâu nhị phân có độ dài n. Xâu nhị phân chỉ bao gồm các ký tự '0' và '1'.

Ý tưởng giải quyết

Để sinh ra tất cả các xâu nhị phân có độ dài n, ta có thể sử dụng phương pháp đệ quy. Mỗi lần đệ quy, ta sẽ nối thêm ký tự '0' hoặc '1' vào xâu hiện tại và tiếp tục gọi đệ quy cho đến khi xâu đạt độ dài n.

Phân tích

1. Điều kiện dừng: Khi xâu đã đủ độ dài n, ta sẽ in ra xâu đó và dừng lại.
2. Đệ quy: Từ mỗi xâu hiện tại, ta có thể tiếp tục sinh ra hai xâu con: một với ký tự '0' và một với ký tự '1'.

Mã nguồn

def xaunhiphan(n, xau=""):
    if len(xau) == n:  # Nếu độ dài xâu đã đạt n
        print(xau)
        return
    for i in ["0", "1"]:  #chọn kí tự '0' hoặc '1' để bắt đầu hàm hoặc thêm vào xâu
        xaunhiphan(n, xau + i)  # Gọi đệ quy với xâu hiện tại cộng thêm '0' hoặc '1'

n = int(input())
xaunhiphan(n)  # bắt đầu hàm