JavaScript でのフィボナッチ数列の実装: 一般的なアプローチとバリエーション

開発者であれば、フィボナッチ数列の値を計算する関数を作成するというタスクに遭遇したことがあるでしょう。この古典的な問題はコーディングの面接でよく登場し、通常は再帰的な実装を求められます。ただし、面接官が特定のアプローチを要求する場合があります。この記事では、JavaScript での最も一般的なフィボナッチ数列の実装について説明します。

フィボナッチ数列とは何ですか?

まず、記憶を更新しましょう。フィボナッチ数列は、各数値が前の 2 つの数値の合計である一連の数値です。 0 と 1 から始まります:

0、1、1、2、3、5、8、13、21、34、55、…

一般的な実装アプローチ

1.再帰的アプローチ

最も伝統的なリクエストは再帰的実装です:

function fibonacciRecursive(n) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

このアプローチは単純ではありますが、n の値が大きい場合にはパフォーマンスが悪くなります。 16 GB RAM を搭載した MacBook Pro i9 では、40 番目のフィボナッチ数の計算に約 1.5 秒かかりました。

console.time('Recursive');
fibonacciRecursive(40);
console.timeEnd('Recursive');

VM379:3 Recursive: 1521.569091796875 ms

50 番目の数値を計算しようとすると、Chrome タブが応答しなくなりました。

2.キャッシュによる再帰的アプローチ (メモ化)

この質問の次のバリエーションは、再帰的実装にキャッシュ メカニズムを追加することでパフォーマンスを向上させることです。

function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  if (cached[n]) {
    return cached[n];
  }

  cached[n] = 
    fibonacciCached(n - 1, cached) + fibonacciCached(n - 2, cached);

  return cached[n];
}

このアプローチでは、0 と 1 の初期値を持つキャッシュされたオブジェクトが導入されます。任意の数値について、最初にそのフィボナッチ値がすでに計算されているかどうかを確認します。その場合、再計算する代わりに、キャッシュされた結果を返します。それ以外の場合は、その値を計算してキャッシュに保存します。

パフォーマンスが大幅に向上しました (もちろん追加のメモリが使用されるため)。 40 番目のフィボナッチ数の計算には約 0.02 ミリ秒かかりました:

console.time('Recursive, with caching');
fibonacciCached(40);
console.timeEnd('Recursive, with caching');

VM382:3 Recursive, with caching: 0.01806640625 ms

3. for ループを使用した反復アプローチ

もう 1 つの一般的なバリエーションは、for ループを使用してフィボナッチ数列を実装することです。

function fibonacciWithIteration(n) {
    if (n <= 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }

    let prev = 0;
    let next = 1;
    let result = 1;

    for (let i = 2; i <= n; i++) {
        result = prev + next;
        [prev, next] = [next, prev + next];
    }
    return result;
}

このアプローチは、基本的な再帰的方法 (キャッシュを使用しない方法) よりもはるかに高速です。

console.time('With iteration');
fibonacciWithIteration(40);
console.timeEnd('With iteration');

VM44:22 With iteration: 0.10107421875 ms

反復アプローチにより、非常に大きな入力値を効率的に処理できます。

console.time('With iteration');
const result = fibonacciWithIteration(1400);
console.log(result);
console.timeEnd('With iteration');

VM325:22 1.7108476902340223e+292
VM325:23 With iteration: 0.5830078125 ms

ボーナス: フィボナッチ数列を配列として返す

面接官は、n 番目の数値までのフィボナッチ数列全体を配列として返すように要求する場合もあります。再帰的アプローチと反復的アプローチの両方を使用してこれを実装しましょう。

再帰的アプローチ

function fibonacciSequence(n) {
  if (n === 0) {
      return [0];
  }
  if (n === 1) {
      return [0, 1];
  }

  const arr = fibonacciSequence(n - 1);
  const currentValue = arr[n - 1] + arr[n - 2];

  return [...arr, currentValue];
}

console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]

この関数は次のように動作します:

1. 0 と 1 の場合、ハードコードされた配列を返します。
2. その他の場合:

• 前の番号のシーケンスを取得し、arr に保存します。
• arr の最後の 2 つの値を合計することで currentValue を計算します。
• arr と currentValue を新しい配列に結合して返します。

反復的アプローチ

function fibonacciSequenceWithIteration(n) {
  if (n < 1) {
    return [0];
  }

  let prev = 0;
  let next = 1;
  const arr = [prev, next];

  for (let i = 2; i <= n; i++) {
    arr.push(prev + next);
    [prev, next] = [next, prev + next];
  }
  return arr;
}

console.log(fibonacciSequenceWithIteration(5)); // [0, 1, 1, 2, 3, 5]

この関数は次のように動作します:

1. 入力が 0 の場合、要素 0 のみを含む配列を返します。
2. その他の場合:

• prev 変数と next 変数を初期化して、前と次の値を保存します。
• 初期値 [0, 1] で arr を作成します。
• 2 から n まで反復し、各反復で prev と next の合計を arr にプッシュします。
• 前の値と次の値を更新し、次の反復に進みます。

結論

この記事ではいくつかの一般的なフィボナッチ数列の実装について説明しますが、すべてを網羅したリストではありません。インタビューやあなたの作品で他のバリエーションを見つけた場合は、コメントで共有してください!

JavaScript とソフトウェア開発の最新ニュースを常に入手してください!私の Telegram チャンネルに参加して、さらなる洞察やディスカッションをお楽しみください: TechSavvy: フロントエンドとバックエンド。

以上がJavaScript でのフィボナッチ数列の実装: 一般的なアプローチとバリエーションの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。