【アルゴリズム】トリボナッチ数列のアルゴリズム

トリボナッチ数列とは

- [tex: T{0} = 0] - [tex: T{1} = 0] - [tex: T{2} = 1] - T{N} = T{N-1} + T{N-2} + T_{N-3} (N = 3, 4...)

によって定義される数列のことであり、[0,0,1,1,2,4,7,13,24,44...] と値が続いていく数列です。フィボナッチ数列が前2つの数字を足した数列であるのに対して、トリボナッチ数列は前3つの数字を足した数列になります。以下で、フィボナッチ数列の第項 を計算するアルゴリズムを考えます。

上記に記載した通り、既にシンプルな漸化式が定義されているのでそれを用いて再帰関数を用いてまずアルゴリズムを表現してみます。

アルゴリズム実装(1) メモ化再帰

メモ化を利用しない単純な再帰関数の呼び出しでは、計算量は指数的に増大してしまいます(計算量の導出は省略)。なので、同じ引数によって実行されたtribonacci()の計算結果をmemo という配列に格納するように工夫し、仮に呼び出された再帰関数の引数に対応したmemoの値が存在したら単純にそれを返すようにします。

vector<long long> memo;

long long tribonacci(int i) {
  if (i == 0) return 0;
  else if (i == 1) return 0;
  else if (i == 2) return 1;

  if (memo[i] != -1) return memo[i];

  memo[i] = tribonacci(i-1) + tribonacci(i-2) + tribonacci(i-3);

  return memo[i];
}

int main(void) {
    int N;
    cin >> N;

    memo.assign(N + 1, -1);

    cout << tribonacci(N) << endl;
}

これはいわゆる一般的なキャッシュと同じ考え方であり、メモ化をしていないケースに比べると圧倒的に計算量を抑えることができますね。

アルゴリズム実装(2) 単純なfor反復

再帰関数の利用ではメモ化でのキャッシュ効率化はほぼ必須ですが、そもそも「前の３項を順々に足し合わせていく」という挙動は単純なfor反復でも実現可能です。この場合、計算量はそのループ数に依存するので計算量はとかなり抑えられます。

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector<long long> tribonacci;

    tribonacci.assign(N + 1, 0);

    for (int i = 0; i < N; i ++) {
      if (i == 0) tribonacci[i] = 0;
      else if (i == 1) tribonacci[i] = 0;
      else if (i == 2) tribonacci[i] = 1;
      else tribonacci[i] = tribonacci[i - 1] + tribonacci[i - 2] + tribonacci[i - 3];
    }

    cout << tribonacci[N - 1] << endl;
}