Xâu ABC

Nguồn: CLUE OJ – Chương 20: Quay lui (Backtracking) Độ khó: Dễ Quay lui Cắt nhánh

Đề bài

Hãy 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.

Ví dụ xâu ABBC là không thỏa mãn do có hai ký tự B đứng cạnh nhau.

Input: một dòng gồm một số nguyên $n$.

Output: in ra toàn bộ những xâu thỏa mãn theo thứ tự từ điển tăng dần, mỗi xâu trên một dòng.

Điều kiện: $1 \le n \le 10$.

Ví dụ – input

2

Ví dụ – output

AB
AC
BA
BC
CA
CB

Lời mở đầu

Đây là bài "khởi động" cực hay cho chương Quay lui: ta điền từng ký tự từ trái sang phải, mỗi vị trí thử lần lượt A, B, C; điền xong vị trí này thì gọi đệ quy điền vị trí tiếp theo. Mình sẽ đi 2 cách: sinh hết rồi mới lọc và cắt nhánh ngay khi vừa sai – để các bạn thấy cắt nhánh làm cây quay lui nhỏ đi bao nhiêu.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test10 testÝ tưởngcây quay luiCách 1sinh 3^n rồi lọcCách 2cắt nhánh

Bộ testBộ test chính thức có gì?

Bộ test có 10 test, mỗi giá trị $n$ từ 1 tới 10 xuất hiện đúng một lần (test 1 là test mẫu $n = 2$):

Test	1	2	3	4	5	6	7	8	9	10
n	2	1	3	4	5	6	7	8	9	10
Số dòng in ra	6	3	12	24	48	96	192	384	768	1.536

Số dòng in ra luôn đúng bằng $3 \cdot 2^{n-1}$: ký tự đầu có 3 lựa chọn, mỗi ký tự sau chỉ còn 2 lựa chọn (khác ký tự ngay trước nó). Với $n = 10$ chỉ có $1536$ xâu, nên bài không chia subtask – cả 2 cách bên dưới đều qua hết, khác nhau ở chỗ cây quay lui to hay nhỏ.

Ý tưởngĐiền từng vị trí, sai thì cắt nhánh

Gọi Try(i) là hàm "điền ký tự cho vị trí $i$" (các vị trí $1..i-1$ đã điền xong):

Khung quay lui

Với mỗi ký tự $c$ lần lượt là A, B, C: nếu $c$ trùng ký tự ở vị trí $i-1$ thì bỏ qua (cắt nhánh); ngược lại đặt $x_i = c$, rồi: nếu $i = n$ thì in xâu, còn không thì gọi Try(i + 1).

Vì ta thử A trước B trước C ở mọi vị trí, các xâu được sinh ra tự động theo đúng thứ tự từ điển – không cần sắp xếp gì cả. Khi Try(i + 1) chạy xong và quay về, vòng lặp ở Try(i) chạy tiếp sang ký tự kế tiếp: ký tự cũ ở vị trí $i$ bị ghi đè – đó chính là bước quay lui.

Em nhập $n$ (tối đa 3) rồi bấm Tiếp để xem máy đi trên cây quay lui. Nút đỏ có dấu ✗ là nhánh bị cắt vì trùng ký tự đứng trước:

n =

Ví dụ nhanh:

Cách 1Sinh đủ $3^n$ xâu rồi kiểm tra

Cách "thật thà" nhất: không cắt nhánh gì cả, mỗi vị trí thử đủ 3 ký tự, sinh ra đủ $3^n$ xâu. Khi đủ $n$ ký tự thì gọi hàm hopLe() kiểm tra xem có 2 ký tự kề nhau nào trùng không, hợp lệ mới in.

C++▶ Chạy tay từng dòng codeCách 1: sinh đủ 3^n xâu, đến lá mới gọi hopLe() kiểm tra.

Dữ liệu vào (stdin) – sửa thoải mái2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mảng x khai báo toàn cục nên mọi phần tử ban đầu là '\0'. Vì vậy x[n + 1] = '\0' và lệnh cout << x + 1 in đúng chuỗi ký tự từ x[1] tới x[n] (dừng ở ký tự '\0').
• Ở vị trí $i$, sau khi Try(i + 1) chạy xong, vòng for tăng c và ghi đè x[i]: không cần "xoá" gì cả.

Không gian$O(n)$

Thời gian$O(3^n \cdot n)$

Kết quả chạy thật: C++: đúng 10/10 test, test chậm nhất chạy 0.003 giây. Bản Python: Python: đúng 10/10 test, test chậm nhất chạy 0.069 giây.

$3^{10} = 59049$ xâu là quá nhỏ với máy, nhưng cách này lãng phí: với $n = 10$ có tới $59049$ lá trên cây mà chỉ $1536$ lá được in (khoảng 2,6%).

Cách 2Quay lui có cắt nhánh

Thay vì đợi đủ $n$ ký tự mới kiểm tra, ta kiểm tra ngay lúc đặt: ký tự $c$ trùng với x[i - 1] thì continue luôn, không đi xuống nhánh đó nữa. Mọi xâu đi tới lá đều hợp lệ nên không cần hàm hopLe().

C++▶ Chạy tay từng dòng codeCách 2: cắt nhánh ngay khi ký tự trùng ký tự đứng trước.

Dữ liệu vào (stdin) – sửa thoải mái2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Với $i = 1$, ta so với x[0] = '\0' – không bằng ký tự nào trong A, B, C, nên vị trí đầu tiên được thử đủ 3 ký tự mà không cần viết if riêng.
• Số lá của cây giảm từ $3^n$ xuống đúng $3 \cdot 2^{n-1}$ – mỗi lá là một dòng kết quả, không có công thừa.

Không gian$O(n)$

Thời gian$O(3 \cdot 2^{n-1} \cdot n)$

Kết quả chạy thật: C++: đúng 10/10 test, test chậm nhất chạy 0.002 giây. Bản Python: Python: đúng 10/10 test, test chậm nhất chạy 0.020 giây.

Ghi chú của mình: cả 2 cách (C++ lẫn Python) đều đạt 10/10 test trên bộ test của CLUE OJ. Bài này nhỏ nên vét cạn vẫn qua, nhưng thói quen cắt nhánh càng sớm càng tốt sẽ cứu các bạn ở những bài quay lui lớn hơn phía sau (n quân hậu, tổng tập con...).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇