C++で「3」と「4」だけを使った記数法のn番目の数を求める方法

この問題では、整数 N が与えられ、「3」と「4」の数字のみを使用する特殊な記数法における N番目の数 を求めます。

この記数法は、次のような数列で構成されています。

3, 4, 33, 34, 43, 44, 333, 334, 343, 344, …

入力例

N = 6

出力例

44

説明

この記数法の数列は「3, 4, 33, 34, 43, 44, …」の順に並んでいるため、6番目の数は 44 となります。

解法アプローチ

実は、この記数法は2進数と非常によく似た構造を持っています。違いは、2進数の「0」が「3」に、「1」が「4」に置き換えられている点だけです。ここでは、この変換後の表現を sBinary と呼ぶことにします。

つまり、N番目の数は「(N−1) の2進数表現の各桁に3を加えたもの」として求められます。

この性質を利用すれば、以下の手順で問題を簡単に解くことができます。

1. (N−1) を2進数に変換する。
2. 2進数の各桁の値（0または1）に3を加える（0→3、1→4）。
3. 得られた数字列を出力する。

10進数を2進数に変換する方法

10進数を2進数に変換するには、数値を2で割り続け、各段階での余りを記録します。余りを逆順に並べると、それが目的の2進数表現になります。今回のプログラムでは、再帰呼び出しを用いてこの処理を実現しています。

プログラム例

#include<iostream>
using namespace std;

void findNThTermNumberSystem(int N) {
    if(N == 1 || N == 2) {
        cout << (N - 1) + 3;
        return;
    }
    N -= 1;
    findNThTermNumberSystem(N / 2);
    cout << ((N % 2) + 3);
}

int main(){
    int N = 12;
    cout << N << "番目の数は ";
    findNThTermNumberSystem(N);
    return 0;
}

出力

12番目の数は 434

コードの解説

関数 findNThTermNumberSystem は、再帰的に (N−1) の2進数変換を行いながら、各桁に3を加えて出力します。

• ベースケース： N が1または2の場合、(N−1)+3 を出力して終了します（それぞれ「3」「4」に対応します）。
• 再帰ステップ： N を1減らした後、N÷2 に対して再帰呼び出しを行い上位の桁を先に出力させ、その後で (N mod 2)+3 によって現在の桁を出力します。

例えば N=12 の場合、N−1=11 は2進数で「1011」と表されるため、各桁に3を加えた「434」が出力されます。このように、2進数変換の仕組みをそのまま応用することで、非常にシンプルかつ効率的に答えを求められるのがポイントです。