C++でN番目のトリボナッチ数を計算する方法

ある値 n が与えられたとき、n番目のトリボナッチ数（Tribonacci number）を求めることを考えます。トリボナッチ数はフィボナッチ数とよく似た数列ですが、フィボナッチ数が直前の2項の和で次の項を作るのに対し、トリボナッチ数では直前の3項の和を使って新しい項を生成します。

T(n) を求める漸化式は以下のようになります。

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

数列の最初の3項は {0, 1, 1} から始まります。

アルゴリズム

この問題は、次のようなシンプルな反復処理で解くことができます。

• 初期値として first := 0、second := 1、third := 1 を設定する
• n - 3 回だけ以下を繰り返す
  • next := first + second + third を計算する
  • first := second、second := third、third := next と値をずらして更新する
• 最後に third の値を返す

この手法では、各ステップで「スライディングウィンドウ」のように3つの変数を更新していくため、配列を使わずにメモリ効率よく計算できます。計算量は O(n)、空間計算量は O(1) です。

C++での実装例

#include<iostream>
using namespace std;

long tribonacci_gen(int n){
    // n番目のトリボナッチ数を生成する関数
    int first = 0, second = 1, third = 1;
    for(int i = 0; i < n - 3; i++){
        int next = first + second + third;
        first = second;
        second = third;
        third = next;
    }
    return third;
}

int main(){
    cout << "15th Tribonacci Term: " << tribonacci_gen(15);
}

入力

15

出力

15th Tribonacci Term: 1705

このプログラムでは、n = 15 を渡すと15番目のトリボナッチ数である 1705 が出力されます。実際に数列を並べると 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, ... となり、各項が直前の3項の合計になっていることが確認できます。