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.
Ta cần tìm chuỗi thứ N trong danh sách vô hạn các chuỗi chỉ dùng hai ký hiệu a và b sắp xếp theo thứ tự từ điển.
Danh sách là −
a, b, aa, ab, ba, bb, aaa, aab, aba, …
Hãy xem ví dụ sau để hiểu bài toán:
Input : N = 8 Output : aab
Phương pháp giải
Một giải pháp đơn giản là dùng vòng lặp để tạo tất cả n chuỗi. Sau đó trả về chuỗi thứ N. Giải pháp này hoạt động nhưng không hiệu quả với N lớn.
Vì vậy, ta sẽ xem giải pháp khác cho thời gian ít hơn.
Một phương pháp khác là sử dụng chỉ số tương đối cho chuỗi. Sử dụng thực tế rằng số chuỗi độ dài N tạo được từ 2 ký hiệu là 2N. Chỉ số tương đối có thể dùng để tìm chuỗi dạng nhị phân.
Relative index = N + 1 - 2( floor(log(N+1)) )
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
The 245-th binary string in sorted order is bbbabba