C++で辞書式順序で「A」と「B」の文字列として数値を出力します

この問題では、数字Nが与えられます。私たちのタスクは、辞書式順序で「A」と「B」の文字列として数字を印刷するプログラムを作成することです。

「A」と「B」の文字列としてのすべての数値の表現は

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

問題を理解するために例を見てみましょう。

入力： N =12

出力： BAB

ソリューションアプローチ

「A」と「B」の文字列は2進数に似ています。文字列を見つけるには、まず、長さ1（サイズ2まで）の数字が2つ、長さ2（サイズ6まで）の数字が4つ、長さ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