C++でテトラナッチ数列を生成する方法

この記事では、C++を使ってテトラナッチ(Tetranacci)数を生成する方法を解説します。テトラナッチ数はフィボナッチ数によく似た数列ですが、フィボナッチ数が直前の2つの項の和で次の項を求めるのに対し、テトラナッチ数では直前の4つの項をすべて足し合わせて新しい項を生成する点が特徴です。

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

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

数列の出発点となる最初の4つの初期値は {0, 1, 1, 2} です。これ以降の項は、直前の4項の和として順次決まっていきます。

アルゴリズム

テトラナッチ数列を効率よく生成するには、常に直近の4つの値だけを保持しながら、変数をスライドさせていく手法が有効です。

tetranacci(n):
Begin
    first := 0, second := 1, third := 1, fourth := 2
    print first, second, third, fourth
    for i in range n − 4, do
        next := first + second + third + fourth
        print next
        first := second
        second := third
        third := fourth
        fourth := next
    done
End

まず初期値の4つを出力し、その後ループ内で「next」に直前4項の合計を代入しては出力します。そして各変数を1つずつ前にずらすことで、配列を使わずに済みます。この方法なら時間計算量は O(n)、必要な記憶領域は O(1) で非常に効率的です。

C++での実装例

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

実行結果

0 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872

コードの解説

関数 tetranacci_gen() は、引数 n で指定された個数のテトラナッチ数を標準出力に表示します。

• 初期化: 変数 first〜fourth に初期値 0, 1, 1, 2 を設定し、そのまま出力します。
• ループ処理: 残りの n−4 項について、next に直前4項の合計を格納して出力します。
• 変数の更新: first〜fourth を順にシフトさせ、常に最新の4項のみをメモリ上に保持します。

なお、テトラナッチ数は増加が非常に速いため、大きな n を扱う場合はオーバーフローに注意してください。int の代わりに long long や多倍長整数型を使用すると、より大きな項まで正確に計算できます。