In một số dưới dạng chuỗi 'A' và 'B' theo thứ tự từ vựng trong C ++

Trong bài toán này, chúng ta được cung cấp một số N. Nhiệm vụ của chúng ta là tạo một chương trình để In một số dưới dạng chuỗi 'A' và 'B' theo thứ tự từ vựng.

Biểu diễn của tất cả các số dưới dạng chuỗi ‘A’ và ‘B’ là

1 =A
2 =B
3 =AA
4 =AB
5 =BA
6 =BB
7 =AAA
8 =AAB

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: N =12

Đầu ra: BAB

Phương pháp tiếp cận giải pháp

Chuỗi ‘A’ và ‘B’ tương tự như một số nhị phân. Để tìm chuỗi, trước tiên chúng ta sẽ tìm độ dài của chuỗi, sử dụng thực tế là có 2 số độ dài 1 (đến cỡ 2), 4 số độ dài 2 (cho đến cỡ 6), 8 số độ dài 3 (cho đến cỡ 14). Sau khi tìm được độ dài ta cần tìm các ký tự của chuỗi. Bằng cách cập nhật lặp đi lặp lại độ dài còn lại khi chúng tôi thêm số vào chuỗi. Ký tự được quyết định dựa trên việc so sánh N với (2 ^ (độ dài còn lại)), nếu N nhỏ hơn ký tự hiện tại là ‘B’, ngược lại là ‘A’ của nó. Sau mỗi lần lặp, chúng tôi sẽ giảm độ dài đi 1 và nếu ký tự là ‘B’ sẽ cập nhật N và giảm nó xuống số.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <iostream>
#include<math.h>
using namespace std;

int findStringLength(int M) {

   int stringLen = 1;
   while((pow(2, stringLen + 1) - 2) < M) {
      stringLen++;
   }
   return stringLen;
}

void printNumString(int N) {
   
   int stringLen, num, stringNumber;
   stringLen = findStringLength(N);
   stringNumber = N - (pow(2, stringLen) - 2);
   while (stringLen) {
      num = pow(2, stringLen - 1);

      if (num < stringNumber) {
         cout<<"B";
         stringNumber -= num; }
      else {
         cout<<"A";
      }
      stringLen--;
   }
}

int main() {
   int N = 47;
   cout<<"The number as sting of 'A' and 'B' in lexicographic order is ";
   printNumString(N);
   return 0;
}

Đầu ra

The number as sting of 'A' and 'B' in lexicographic order is BAAAA