C++でトリボナッチ数を生成する方法を解説

トリボナッチ数とは

トリボナッチ数(Tribonacci数)は、有名なフィボナッチ数とよく似た数列ですが、フィボナッチ数が直前の2項を足して次の項を求めるのに対し、トリボナッチ数は直前の3つの項を加算して新しい項を生成する点が異なります。

n番目の項 T(n) を求める漸化式は以下の通りです。

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

数列の最初の3項は {0, 1, 1} から始まります。したがって、数列は「0, 1, 1, 2, 4, 7, 13, ...」と続いていきます。

アルゴリズム

トリボナッチ数を生成する基本的なアルゴリズムは以下のようになります。初期値3つを保持しながら、ループごとに値をずらして更新していくのがポイントです。

tribonacci(n):
Begin
    first := 0, second := 1, third := 1
    print first, second, third
    for i in range n – 3, do
        next := first + second + third
        print next
        first := second
        second := third
        third := next
    done
End

C++での実装例

以下は、指定された個数分のトリボナッチ数を出力するC++プログラムの例です。

#include<iostream>
using namespace std;
long tribonacci_gen(int n){
    // n個のトリボナッチ数を生成する関数
    int first = 0, second = 1, third = 1;
    cout << first << " " << second << " " << third << " ";
    for(int i = 0; i < n - 3; i++){
        int next = first + second + third;
        cout << next << " ";
        first = second;
        second = third;
        third = next;
    }
}
main(){
    tribonacci_gen(15);
}

実行結果

このプログラムを実行すると、15個のトリボナッチ数が出力されます。

0 1 1 2 4 7 13 24 44 81 149 274 504 927 1705

処理の流れとポイント

• 変数 first、second、third の3つで直前の項を管理します。
• 各ループで next = first + second + third を計算し、出力します。
• その後、3つの変数の値を1つずつ後ろにシフト(first ← second ← third ← next)することで、常に直近3項を保持できます。

この手法により、再帰呼び出しを使わない反復的な実装となっているため、計算量は O(n) で効率的に動作します。なお、項の値は急激に大きくなるため、より多くの項を扱う場合は int ではなく long long 型を使用することをおすすめします。