JavaScript
 Computer >> コンピューター >  >> プログラミング >> JavaScript

JavaScriptでリュカ数列のn番目の要素を求める方法

リュカ数（Lucas Numbers）とは

リュカ数は、以下のように定義される数列のことです。フィボナッチ数列と似た構造を持ちますが、初期値が異なる点が特徴です。

L(0) = 2
L(1) = 1
L(n) = L(n-1) + L(n-2)

つまり、3番目以降の項は「直前の2つの項の和」として計算されます。実際に並べると 2, 1, 3, 4, 7, 11, 18, 29, ... のような数列になります。

問題

数値 n を引数として受け取り、n番目のリュカ数を返すJavaScript関数を作成する必要があります。

解決策：再帰による実装

定義通りに再帰処理を使うことで、シンプルに実装できます。以下がそのコードです。

const num = 21;

const lucas = (num = 1) => {
    if (num === 0)
        return 2;
    if (num === 1)
        return 1;
    return lucas(num - 1) + lucas(num - 2);
};

console.log(lucas(num));

出力結果

24476

この例では num に 21 を指定しているため、21番目のリュカ数である 24476 が出力されます。

補足：パフォーマンスに関する注意点

上記の再帰実装は定義をそのまま表していて理解しやすい反面、同じ値を何度も再計算するため、n が大きくなると計算量が指数的に増加します。実用的な用途では、メモ化（計算結果のキャッシュ）や、ループで順に計算する反復処理を使うことで、効率を大幅に改善できます。

  1. 【JavaScript入門】配列内で最初の非連続な数値を見つける方法

    はじめに本記事では、JavaScriptを使って「数値の配列の中から、直前の要素と連続していない最初の数値」を見つける方法を解説します。アルゴリズムの練習やコーディング面接の対策としても役立つ基本的な問題です。 問題の定義数値の配列を受け取るJavaScript関数を作成する必要があります。この関数は、直前の要素に対して +1 となっていない（連続していない）最初の要素を返さなければなりません。 言い換えると、隣り合う要素同士の差が1以外になる箇所が現れたとき、その箇所の後ろ側の要素を返すという処理です。なお、そのような要素が必ず配列内に1つ以上存在するものとします。 サンプルコード以下は、実

  2. JavaScriptで昇順配列の中から並び順を壊している唯一の要素を見つける方法

    この記事では、昇順（増加順）にソートされた数値の配列の中に、ただひとつだけ並び順を乱している要素がある場合に、その要素を特定して返すJavaScript関数の実装方法を解説します。 問題の定義 扱う配列は基本的に昇順でソートされていますが、その中の要素がひとつだけ順序から外れています。関数の目的は、その「異常な要素」を見つけ出して返すことです。 たとえば、次のような配列を考えます。 const arr = [1, 2, 3, 4, 17, 5, 6, 7, 8]; この配列から「17」を取り除けば残りは完全な昇順になるため、求める答えは「17」です。 解決のアプローチ 昇順の配列では、隣り合う