Xin ý tưởng về sinh dãy tam phân không lặp

Anh1999 · October 20, 2020, 10:30am

Đề bài
Nhập số nguyên dương N. Hãy chỉ ra một dãy tam phân không lặp độ dài N sử dụng ít kí tự 2 nhất (Dãy tam phân chỉ có 0,1,2)

Em mong người giúp đỡ em ạ

nitro2 · October 18, 2020, 4:03am

Hỏi thầy xem thể nào là không lặp ? =]]
Ví dụ: 0001, 0101, 01101 có gọi là lặp không?

Anh1999 · October 18, 2020, 9:09am

Đây là thầy nói ạ:“Chuỗi tam phân không lặp là chuỗi tam phân mà không có hai chuỗi con liên tiếp giống nhau.”

nitro2 · October 18, 2020, 2:36pm

Nếu định nghĩa “chuỗi con” nhỏ nhất có chứa một chữ số thì bài này cũng dạng khó ăn đấy

Giải thuật đề xuất thế này:

a. Nếu số X thỏa điều kiện chuỗi không lặp thì quay lại bước 1
b. Nếu số X không thỏa điều kiện thì kiểm tra số tiếp theo.

Cụ thể:

1. Chọn 0 làm số thứ 1. Ta có `0` -> Kiểm tra ok.
2. Chọn 0 làm số thứ 2. Ta có `00` -> Kiểm tra backtrack số trước thấy giống -> Loại
3. Chọn 1 làm số thứ 2. Ta có `01` -> Kiểm tra backtrack số trước thấy khác -> OK
4. Chọn 0 làm số thứ 3. Ta có `010` -> Kiểm tra backtrack số trước thấy khác -> OK
5. Chọn 0 làm số thứ 4. Ta có `0100` -> Kiểm tra backtrack số trước thấy giống-> Loại
6. Chọn 1 làm số thứ 4. Ta có `0101` -> Kiểm tra backtrack số trước thấy khác -> Loại . 
Chỗ bước 6 này tại sao lại khác? Vì phải kiểm tra subtring có độ dài là 1, sau đó kiểm tra substring có độ dài là 2. Nghĩa là phải nhảy 2 pointer cùng lúc.

Như vậy tương tự ta sẽ có các case kiểm tra backtrack substring ngược có độ dài là 1, sau đó là 2, 3, 4, 5, … cho tới khi trỏ đến vị trí ban đầu của chuỗi.

Mà theo nhận định này thì max N sẽ là 0102010 chắc hiểu sai ý ông thầy rồi =))

Anh1999 · October 19, 2020, 8:02am

em cảm ơn ạ <3 <3 <3

Stanley00 · October 19, 2020, 8:43am

Thật ra hiểu vậy là đúng rồi, chỉ có điều khi đến 0102010 thì không thể thêm 0, 1, hay 2 vào cuối nữa thì lại cần backtrack thêm với 0102011 (loại) và 0102012 (ok)

nitro2 · October 19, 2020, 1:50pm

Toy đã đoán trước được tình hình rồi mà :#