JavaScriptでフィボナッチ風の数列のn番目の項を求める方法

この記事では、次のように定義される数列を扱います。

連続する2項 t1 と t2 が与えられたとき、3番目の項は以下の式で求められます。

t3 = t1 + (t2 * t2)

フィボナッチ数列と同様に、この数列の最初の2項は常に 0 と 1 です。

ここで求められているのは、数値 n を引数として受け取り、上記のルールに従う数列の n 番目の項を計算して返すJavaScript関数を作成することです。

たとえば、n = 6 の場合、結果は次のようになります。

t6 = 27

これは、数列が次のように展開されるためです。

0 1 1 2 5 27

各項の計算過程を見てみましょう。

• t1 = 0、t2 = 1(固定の初期値)
• t3 = 0 + (1 × 1) = 1
• t4 = 1 + (1 × 1) = 2
• t5 = 1 + (2 × 2) = 5
• t6 = 2 + (5 × 5) = 27

実装例

この問題を解くコードは次のようになります。

const num = 6;
const findSequenceTerm = (num = 1) => {
    const arr = [0, 1];
    while (num > arr.length) {
        const last = arr[arr.length - 1];
        const secondLast = arr[arr.length - 2];
        arr.push(secondLast + (last * last));
    };
    return arr[num - 1];
};
console.log(findSequenceTerm(num));

アルゴリズムの解説

この関数の動作を順を追って説明します。

1. 初期値として 0 と 1 を格納した配列 arr を用意します。
2. 配列の長さが n に達するまで while ループを回します。
3. ループ内では、直前の項(last)とその前の項(secondLast)を取得し、「前の項 + 直前の項の2乗」というルールに従って新しい項を配列に追加します。
4. 最後に arr[num - 1] を返せば、目的の n 番目の項が得られます。

このアプローチの時間計算量は O(n)、空間計算量も O(n) です。なお、数列全体を保持する必要がない場合は、直前の2つの値だけを変数で管理することで、空間計算量を O(1) に抑えることも可能です。

出力

コンソールには次のように表示されます。

27