## **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**
```cpp
#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
```python
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
NgoTranTheThinh
Created at
9 likes
ThanhDungxX
Created at
1 likes