Trong bài toán này, chúng ta được cho một số dương là 1. Nhiệm vụ của chúng ta là tìm chuỗi nhị phân thứ N theo thứ tự đã sắp xếp.
Chúng ta cần tìm chuỗi thứ N trong danh sách vô hạn các chuỗi được tạo chỉ bằng hai ký hiệu a và b được sắp xếp theo thứ tự từ vựng.
Danh sách là -
a, b, aa, ab, ba, bb, aaa, aab, aba,…
Hãy lấy một ví dụ để hiểu vấn đề,
Input : N = 8 Output : aab
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng các vòng lặp để tạo ra tất cả n chuỗi. Và sau đó trả về chuỗi thứ N. Giải pháp này thực hiện được công việc nhưng không thể cung cấp giải pháp hiệu quả trong trường hợp giá trị lớn của N.
Vì vậy, chúng ta sẽ thấy một giải pháp khác có thể cung cấp giải pháp trong thời gian ngắn hơn.
Một cách tiếp cận khác để giải quyết vấn đề là sử dụng một chỉ mục tương đối cho chuỗi. Sử dụng thực tế rằng số chuỗi có độ dài N có thể được tạo ra bằng cách sử dụng 2 ký hiệu là 2N. Chỉ mục tương đối có thể được sử dụng để tìm dạng nhị phân chuỗi.
Chỉ số tương đối =N + 1 - 2 (tầng (log (N + 1)))
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
string findBinString(ll n){
ll len = (int)log2(n + 1);
int ri = n + 1 - pow(2, len);
ll i = 0;
string binString = "";
for (i = 0; i < len; i++) {
binString += 'a';
}
i = 0;
while (ri > 0) {
if (ri % 2 == 1)
binString[i] = 'b';
ri /= 2;
i++;
}
reverse(binString.begin(), binString.end());
return binString;
}
int main(){
ll n = 245;
cout<<"The "<<n<<"-th binary string in sorted order is "<<findBinString(n);
return 0;
} Đầu ra
The 245-th binary string in sorted order is bbbabba