C++でトリボナッチ語（Tribonacci Word）を生成する方法を解説

トリボナッチ語（Tribonacci Word）とは、数字の並びから構成される文字列のことです。フィボナッチ語（Fibonacci Word）によく似た概念ですが、トリボナッチ語は直前の3つの文字列を順に連結していく点が大きな特徴です。

トリボナッチ語の定義

トリボナッチ語は、次の漸化式によって定義されます。

T(n) = T(n - 1) + T(n - 2) + T(n - 3)

最初の3つの文字列は {1, 12, 1213} です。したがって、4番目の文字列は「1213 + 12 + 1」を連結した 1213121 となります。

アルゴリズム

トリボナッチ語を生成する基本的な手順は以下の通りです。

tribonacci_word(n):
開始
    first := 1, second := 12, third := 1213
    first, second, third を出力する
    i が 3 から n まで繰り返す:
        temp := third
        third := third + second + first
        third を出力する
        first := second
        second := temp
    繰り返し終了
終了

C++での実装例

上記のアルゴリズムをC++で実装すると、次のようになります。

#include<iostream>
using namespace std;
long tribonacci_word_gen(int n){
    // n番目までのトリボナッチ語を生成する関数
    string first = "1";
    string second = "12";
    string third = "1213";
    cout << first << "\n" << second << "\n" << third << "\n";
    string tmp;
    for (int i = 3; i <= n; i++) {
        tmp = third;
        third += (second + first);
        cout << third << endl;
        first = second;
        second = tmp;
    }
}
main(){
    tribonacci_word_gen(6);
}

プログラムの処理の流れ

• まず、初期文字列である「1」「12」「1213」をそれぞれ出力します。
• ループ内では、変数 tmp に現在の third の値を退避させます。
• third に second と first を連結した新しい文字列を代入し、画面に出力します。
• 最後に first と second を一つずつずらし、次の反復に備えます。

出力結果

このプログラムを実行すると、6番目までのトリボナッチ語が以下のように表示されます。

1
12
1213
1213121
1213121121312
121312112131212131211213
12131211213121213121121312131211213121213121

注意点

トリボナッチ語の文字列長は、反復ごとに急速に増加していきます。そのため、大きな n を扱う場合は、文字列が消費するメモリ量に十分注意してください。必要に応じて、生成する項数を制限するなどの対策が有効です。