C++에서 사전순으로 'A'와 'B'의 문자열로 숫자를 인쇄하십시오.

이 문제에서 우리는 숫자 N을 받습니다. 우리의 임무는 사전순으로 'A'와 'B'의 문자열로 숫자를 인쇄하는 프로그램을 만드는 것입니다.

모든 숫자를 'A'와 'B'의 문자열로 표현하면

1 =A
2 =나
3 =AA
4 =AB
5 =학사
6 =BB
7 =AAA
8 =AAB

문제를 이해하기 위해 예를 들어 보겠습니다.

입력: N =12

출력: BAB

해결 방법

'A'와 'B'의 문자열은 이진수와 유사합니다. 문자열을 찾기 위해 먼저 길이 1의 숫자 2개(크기 2까지), 길이 2의 숫자 4개(크기 6까지), 길이 3의 숫자 8개(크기까지)가 있다는 사실을 사용하여 문자열의 길이를 찾습니다. 14). 길이를 찾은 후 문자열의 문자를 찾아야 합니다. 문자열에 숫자를 추가할 때 남은 길이를 반복적으로 업데이트합니다. 문자는 N을 (2^(남은 길이))와 비교하여 결정되며, N이 현재 문자보다 작으면 'B' 그렇지 않으면 'A'입니다. 각 반복 후에 길이를 1씩 줄이고 문자가 'B'이면 N을 업데이트하고 num만큼 줄입니다.

우리 솔루션의 작동을 설명하는 프로그램,

예

#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;
}

출력

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