# **Giải bài "Xâu ABC" bằng Đệ Quy**
## **1. Tư duy giải thuật**
Chúng ta cần liệt kê tất cả các xâu có độ dài \( n \), chỉ chứa ba ký tự `'A'`, `'B'`, `'C'` và không có hai ký tự giống nhau đứng cạnh nhau.
### **Phân tích cách tạo xâu hợp lệ:**
- Nếu xâu hiện tại đang kết thúc bằng `'A'`, ta có thể thêm `'B'` hoặc `'C'`.
- Nếu xâu hiện tại đang kết thúc bằng `'B'`, ta có thể thêm `'A'` hoặc `'C'`.
- Nếu xâu hiện tại đang kết thúc bằng `'C'`, ta có thể thêm `'A'` hoặc `'B'`.
- Nếu xâu rỗng, ta có thể bắt đầu với bất kỳ ký tự nào trong `'A'`, `'B'`, `'C'`.
Chúng ta tiếp tục quá trình này đến khi xâu đạt độ dài \( n \), sau đó in ra kết quả.
---
## **2. Xây dựng hàm giải quyết bài toán**
Ta sẽ sử dụng **đệ quy** để xây dựng dần dần các xâu hợp lệ.
```cpp
#include <bits/stdc++.h>
using namespace std;
void generateStrings(int n, string s = "") {
if (s.size() == n) { // Điều kiện dừng: nếu xâu đạt độ dài n, in ra
cout << s << endl;
return;
}
for (char x : {'A', 'B', 'C'}) { // Duyệt qua 3 ký tự có thể thêm
if (s.empty() || s.back() != x) { // Đảm bảo không có 2 ký tự liên tiếp giống nhau
generateStrings(n, s + x); // Gọi đệ quy để tạo tiếp xâu mới
}
}
}
int main() {
int n;
cin >> n;
generateStrings(n);
return 0;
}
```
---
## **3. Giải thích hàm `generateStrings`**
Hàm `generateStrings(int n, string s)` hoạt động như sau:
1. **Điều kiện dừng:**
- Khi độ dài của `s` đạt `n`, ta in ra `s` và dừng đệ quy.
2. **Duyệt các ký tự `'A'`, `'B'`, `'C'`**:
- Nếu `s` đang rỗng, có thể chọn bất kỳ ký tự nào.
- Nếu không, chỉ chọn những ký tự khác với ký tự cuối cùng của `s`.
3. **Gọi đệ quy:**
- Nếu điều kiện hợp lệ, ta tiếp tục thêm ký tự vào `s` và gọi lại hàm để mở rộng xâu.
---
## **4. Ví dụ chạy chương trình**
### **Input:**
```
2
```
### **Quá trình tạo xâu:**
```
"A" → "AB", "AC"
"B" → "BA", "BC"
"C" → "CA", "CB"
```
### **Output:**
```
AB
AC
BA
BC
CA
CB
```
---
## **5. Kết luận**
Bài toán được giải quyết hiệu quả bằng **đệ quy**. Tư duy chính là:
- Xác định ký tự cuối cùng của xâu.
- Chỉ thêm các ký tự hợp lệ tiếp theo.
- Dừng lại khi xâu đạt độ dài yêu cầu.
🚀 **Chúc bạn thành công!** 🚀
# Ý TƯỞNG
Với yêu cầu của đề bài: **`in ra những xâu độ dài n chỉ gồm ba loại kí tự A, B, và C và không có hai kí tự cạnh nhau nào được giống nhau`**.
Ta có thể sử dụng đệ quy để giải quyết yêu cầu của bài. Nếu bạn chưa biết, chúng ta cũng có thể xem
`void()` là một dạng đệ quy, miễn sao nó đảm bảo tính chất *gọi lại chính nó*.
Trong hàm Strings:
Có **trường hợp cơ sở** là nếu `current` có độ lớn bằng n *`(đã tạo đủ các kí tự)`* thì sẽ `cout << current`.
Còn **trường hợp đệ quy** sẽ là vòng `for (char c)`. Vòng for này hoạt động dựa trên nguyên tắc:
**duyệt lần lượt qua 3 kí tự *`(char)`* trong mảng `{'A', 'B', 'C'}` và trong khi duyệt:** Nếu kí tự cuối cùng của `current`
khác `c` *`(current.back() != c)`* thì ta nhận `c` vào cuối `current`. Cuối cùng gọi lại chính hàm
Strings để tiếp tục xây dựng xâu `current`.
## Thành Phần
- Strings : Hàm đệ quy.
- current : xâu có độ lớn = n thỏa mãn yêu cầu đề bài.
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define NAME "test"
#define C ".c"
void Strings(string current, int n)
{
if (current.length() == n)
{
cout << current << "\n";
return;
}
for (char c : {'A', 'B', 'C'})
{
if (current.empty() || current.back() != c) Strings(current + c, n);
}
}
signed main()
{
if(fopen(NAME".inp"C, "r"))
{
freopen(NAME".inp"C,"r",stdin);
freopen(NAME".out"C,"w",stdout);
}
int n;
cin >> n;
Strings("", n);
// from member of Tran Bien Highschool
}
```
NgoTranTheThinh
Created at
6 likes
Temrater
Created at
3 likes