C++でドラゴン曲線シーケンスのn番目の項を求める方法

この記事では、ドラゴン曲線(Dragon Curve)シーケンスのn番目の項を求めるC++プログラムを紹介します。ドラゴン曲線シーケンスとは、無限に続く二進列(0と1のみで構成される数列)のことで、「1」から始まり、各ステップで前の項の各要素に対して「1」と「0」を交互に追加していくことで次の項を形成していきます。

• 第1項: 1
• 第2項: 110
• 第3項: 1101100
• 第4項: 110110011100100

まず「1」から始め、前の項の各要素の後に「1」と「0」を交互に付け加えていきます。新しい項が得られたら、それを現在の項として同じ手順をn回繰り返すことで、目的の項を生成できます。

アルゴリズムの流れ

1. 初期項として文字列「1」を用意します。
2. 前の項の各文字を先頭から順に読み取り、新しい文字列にコピーします。
3. 1文字コピーするたびに、直前に追加した補助文字と逆の文字(「1」と「0」を交互に切り替え)を末尾に追加します。
4. この処理を第2項から第n項まで繰り返し、最終的な文字列を結果として返します。

C++での実装例

#include <iostream>
using namespace std;
string dragCurveTerm(int n) {
    string term = "1";
    for (int i = 2; i <= n; i++) {
        string temp = "1";
        char prev = '1', zero = '0', one = '1';
        for (int j = 0; j < term.length(); j++) {
            temp += term[j]; // 元の文字列から1文字取り出す
            if (prev == '0') {
                temp += one;
                prev = one;
            } else {
                temp += zero;
                prev = zero;
            }
        }
        term = temp;
    }
    return term;
}
int main() {
    cout << "ドラゴン曲線シーケンスの第4項: " << dragCurveTerm(4);
}

実行結果

ドラゴン曲線シーケンスの第4項: 110110011100100

計算量について

各ステップで項の長さはほぼ2倍に増加するため、第n項の長さは 2ⁿ − 1 文字になります。そのため、nが大きくなると文字列の生成コストが急激に増大する点に注意が必要です。小〜中程度のnに対しては、この単純なシミュレーション手法で十分に実用的です。