C++でn回の変換後のバイナリ文字列におけるi番目の文字を求める方法

2進文字列 bin があるとします。この文字列に対して n 回の変換を繰り返し適用します。各変換では、文字「0」は「01」に、「1」は「10」に置き換えられます。そして、n 回の変換が完了した後の文字列における i 番目の文字を求めるのが、この問題の目的です。

具体例を見てみましょう。2進文字列が「101」、n = 2、i = 3 の場合、1回目の変換後は「100110」になり、2回目の変換後は「100101101001」になります。したがって、i 番目（インデックス3）の文字は「1」ということになります。

解法のアプローチ

この問題は、以下の手順に従って解くことができます。

• 外側のループを n 回実行し、各反復内で文字列に対して内側のループを実行します。
  • 2進文字列の各文字を順に調べ、「0」であれば「01」を、「1」であれば「10」を別の一時文字列に追加していきます。
  • 内側のループが完了したら、一時文字列を元の2進文字列に代入し、次の反復に備えます。
• すべての反復が終了したら、i 番目の文字を返します。

実装例

#include<iostream>
using namespace std;
char getCharacter(string bin_str, int n, int i) {
    string temp = "";
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < bin_str.length(); y++) {
            if (bin_str[y] == '1')
                temp += "10";
            else
                temp += "01";
        }
        bin_str = temp;
        temp = "";
    }
    return bin_str[i];
}
int main() {
    int n = 2;
    string bin = "101";
    cout << 3 << "rd character is: "<< getCharacter(bin, n, 3)<<endl;
    cout << 9 << "th character is: "<< getCharacter(bin, n, 9);
}

出力結果

3rd character is: 1
9th character is: 0

計算量に関する注意点

この手法では、変換を1回適用するごとに文字列の長さが2倍になるため、n 回の反復後の文字列の長さは初期長の 2ⁿ 倍になります。そのため、n が大きくなるとメモリ消費量と処理時間が急激に増加する点に注意が必要です。小規模な n であれば、この単純なシミュレーションによる実装で十分実用的ですが、大きな n を扱う場合は、文字列の再帰的な構造（各半分が互いに補完関係にある性質）を利用して、実際の文字列を生成せずに i 番目の文字を直接求める、より効率的なアルゴリズムを検討するとよいでしょう。