Solutions of ABC string - MarisaOJ: Marisa Online Judge

Solutions of ABC string

Select solution language

Write solution here.


NgoTranTheThinh    Created at    7 likes

# **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 nn, chỉ chứa ba ký tự A'A', B'B', C'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'A', ta có thể thêm B'B' hoặc C'C'. - Nếu xâu hiện tại đang kết thúc bằng B'B', ta có thể thêm A'A' hoặc C'C'. - Nếu xâu hiện tại đang kết thúc bằng C'C', ta có thể thêm A'A' hoặc B'B'. - Nếu xâu rỗng, ta có thể bắt đầu với bất kỳ ký tự nào trong A'A', B'B', C'C'. Chúng ta tiếp tục quá trình này đến khi xâu đạt độ dài nn, 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#clude<bitsstdc++.h>usingnamespacestd;vorateStrgs(n,strgs=){if(s.size()==n){/Điukindng:nếuxâuđtđdàin,racoutsendl;return;}for(charx:{A,B,C}){/Duytqua3kýtcóththêmif(s.empty()s.back()x){/Đmbokhôngcó2kýtliêntiếpgingnhaurateStrgs(n,s+x);/Giđquyđtotiếpxâumi}}}ma(){n;cn;rateStrgs(n);return0;}cpp#clude<bitsstdc++.h>usingnamespacestd;vorateStrgs(n,strgs=){if(s.size()==n){/Điukindng:nếuxâuđtđdàin,racoutsendl;return;}for(charx:{'A','B','C'}){/Duytqua3kýtcóththêmif(s.empty()s.back()x){/Đmbokhôngcó2kýtliêntiếpgingnhaurateStrgs(n,s+x);/Giđquyđtotiếpxâumi}}}ma(){n;cn;rateStrgs(n);return0;} --- ## **3. Giải thích hàm rateStrgsrateStrgs** Hàm rateStrgs(n,strgs)rateStrgs(n,strgs) hoạt động như sau: 1. **Điều kiện dừng:** - Khi độ dài của ss đạt nn, ta in ra ss và dừng đệ quy. 2. **Duyệt các ký tự A'A', B'B', C'C'**: - Nếu ss đ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 ss. 3. **Gọi đệ quy:** - Nếu điều kiện hợp lệ, ta tiếp tục thêm ký tự vào ss và gọi lại hàm để mở rộng xâu. --- ## **4. Ví dụ chạy chương trình** ### **Input:** 22 ### **Quá trình tạo xâu:** AAB,ACBBA,BCCCA,CBAAB,ACBBA,BCCCA,CB ### **Output:** ABACBABCCACBABACBABCCACB --- ## **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!** 🚀

User Avatar Temrater    Created at    3 likes

# Ý TƯỞNG Với yêu cầu của đề bài: **ranhngxâuđdàinchgmbaloikítA,B,vàCvàkhôngcóhaikítcnhnhaunàođưcgingnhauranhngxâuđdàinchgmbaloikítA,B,vàCvàkhôngcóhaikítcnhnhaunàođưcgingnhau**. 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 vovo 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 currentcurrent có độ lớn bằng n *(đãtođcáckít)(đãtođcáckít)* thì sẽ coutcurrentcoutcurrent. Còn **trường hợp đệ quy** sẽ là vòng for(charc)for(charc). 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)(char)* trong mảng {A,B,C}{'A','B','C'} và trong khi duyệt:** Nếu kí tự cuối cùng của currentcurrent khác cc *(current.back()c)(current.back()c)* thì ta nhận cc vào cuối currentcurrent. Cuối cùng gọi lại chính hàm Strings để tiếp tục xây dựng xâu currentcurrent. ## 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#clude<bitsstdc++.h>usingnamespacestd;#defelonglong#defeNAMEtest#defeC.cvotrgs(strgcurrent,n){if(current.n>h()==n){coutcurrent\n;return;}for(charc:{A,B,C}){if(current.empty()current.back()c)Strgs(current+c,n);}}sigdma(){if(fopen(NAME.inpC,r)){eopen(NAME.inpC,r,std);eopen(NAME.outC,w,stdout);}n;cn;Strgs(,n);/ommemberofTranBienHighschl}cpp#clude<bitsstdc++.h>usingnamespacestd;#defelonglong#defeNAMEtest#defeC.cvotrgs(strgcurrent,n){if(current.n>h()==n){coutcurrent\n;return;}for(charc:{'A','B','C'}){if(current.empty()current.back()c)Strgs(current+c,n);}}sigdma(){if(fopen(NAME.inpC,r)){eopen(NAME.inpC,r,std);eopen(NAME.outC,w,stdout);}n;cn;Strgs(,n);/ommemberofTranBienHighschl}