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

この問題では、数値 N が与えられ、それを「A」と「B」のみで構成される文字列として辞書式順序（lexicographic order）で出力するプログラムを作成します。

「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個（N=2まで）、長さ2の文字列は4個（N=6まで）、長さ3の文字列は8個（N=14まで）存在するというものです。

長さが判明したら、次に文字列の各文字を決定していきます。基準値 num = 2^(残りの長さ) と現在の番号 stringNumber を比較し、num の方が小さければ現在の文字は「B」となり、stringNumber から num を差し引いて更新します。そうでなければ「A」を出力します。各反復処理のたびに残りの長さを1減らし、これを繰り返すことで目的の文字列が完成します。

動作の解説（N = 47 の場合）

findStringLength(47) により文字列の長さは5と求まります。続いて stringNumber = 47 − (2^5 − 2) = 17 となります。最初の比較では num = 16 < 17 であるため「B」を出力し、stringNumber は1に更新されます。以降の反復では num = 8, 4, 2, 1 のいずれも stringNumber = 1 を下回らないため「A」が出力され、最終的に「BAAAA」が得られます。

ソリューションの動作を示すプログラム

例

#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<<"辞書式順序で「A」と「B」の文字列として表した数値は ";
    printNumString(N);
    return 0;
}

出力

辞書式順序で「A」と「B」の文字列として表した数値は BAAAA