Melaksanakan Jujukan Fibonacci dalam JavaScript: Pendekatan dan Variasi Biasa

Sebagai pembangun, anda mungkin menghadapi tugas menulis fungsi untuk mengira nilai dalam jujukan Fibonacci. Masalah klasik ini sering muncul dalam temu bual pengekodan, biasanya meminta pelaksanaan rekursif. Walau bagaimanapun, penemuduga kadangkala boleh meminta pendekatan khusus. Dalam artikel ini, kami akan meneroka pelaksanaan jujukan Fibonacci yang paling biasa dalam JavaScript.

Apakah Jujukan Fibonacci?

Pertama, mari segarkan ingatan kita. Urutan Fibonacci ialah satu siri nombor di mana setiap nombor ialah hasil tambah dua nombor sebelumnya. Ia bermula dengan 0 dan 1:

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

Pendekatan Pelaksanaan Biasa

1. Pendekatan Rekursif

Permintaan paling tradisional adalah untuk pelaksanaan rekursif:

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

Walaupun mudah, pendekatan ini tidak berprestasi untuk nilai n yang besar. Pada MacBook Pro i9 dengan 16 GB RAM, pengiraan nombor Fibonacci ke-40 mengambil masa kira-kira 1.5 saat:

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

VM379:3 Recursive: 1521.569091796875 ms

Percubaan untuk mengira nombor ke-50 menyebabkan tab Chrome menjadi tidak bertindak balas.

2. Pendekatan Rekursif dengan Caching (Memoization)

Variasi seterusnya bagi soalan ini adalah untuk meningkatkan prestasi dengan menambahkan mekanisme caching pada pelaksanaan rekursif kami:

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];
}

Pendekatan ini memperkenalkan objek cache dengan nilai awal untuk 0 dan 1. Untuk sebarang nombor tertentu, kami mula-mula menyemak sama ada kami telah mengira nilai Fibonaccinya. Jika ya, kami mengembalikan hasil cache dan bukannya mengira semula. Jika tidak, kami mengira nilai itu dan menyimpannya dalam cache.

Peningkatan prestasi adalah ketara (disebabkan oleh memori tambahan yang digunakan, sudah tentu). Mengira nombor Fibonacci ke-40 mengambil masa ~0.02 ms:

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

VM382:3 Recursive, with caching: 0.01806640625 ms

3. Pendekatan Berulang dengan Gelung untuk

Satu lagi variasi biasa ialah melaksanakan jujukan Fibonacci menggunakan gelung 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;
}

Pendekatan ini jauh lebih pantas daripada kaedah rekursif asas (yang tanpa caching):

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

VM44:22 With iteration: 0.10107421875 ms

Pendekatan berulang boleh mengendalikan nilai input yang sangat besar dengan cekap:

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

Bonus: Mengembalikan Jujukan Fibonacci sebagai Array

Penemuduga juga mungkin meminta anda mengembalikan keseluruhan jujukan Fibonacci hingga ke nnombor ke-sebagai tatasusunan. Mari laksanakan ini menggunakan pendekatan rekursif dan berulang.

Pendekatan rekursif

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]

Fungsi ini berfungsi seperti berikut:

1. Untuk 0 dan 1, kami mengembalikan tatasusunan berkod keras.
2. Untuk kes lain:

• Kami mendapat urutan untuk nombor sebelumnya dan menyimpannya dalam arr.
• Kami mengira nilai semasa dengan menjumlahkan dua nilai terakhir arr.
• Kami menggabungkan arr dan currentValue dalam tatasusunan baharu dan mengembalikannya.

Pendekatan Berulang

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]

Fungsi ini berfungsi seperti berikut:

1. Jika input ialah 0, kami mengembalikan tatasusunan dengan hanya elemen 0.
2. Untuk kes lain:

• Kami memulakan pembolehubah sebelumnya dan seterusnya untuk menyimpan nilai sebelumnya dan seterusnya.
• Kami mencipta arr dengan nilai awal [0, 1].
• Kami beralih daripada 2 kepada n, menolak jumlah prev dan seterusnya arr dalam setiap lelaran.
• Kami mengemas kini nilai sebelum dan seterusnya dan meneruskan ke lelaran seterusnya.

Kesimpulan

Walaupun artikel ini merangkumi beberapa pelaksanaan jujukan Fibonacci yang biasa, ia bukanlah senarai yang lengkap. Jika anda pernah menemui variasi lain dalam temu bual atau kerja anda, sila kongsikannya dalam ulasan!

Kekal dikemas kini dengan JavaScript terkini dan berita pembangunan perisian! Sertai saluran Telegram saya untuk mendapatkan lebih banyak cerapan dan perbincangan: TechSavvy: Frontend & Backend.

Atas ialah kandungan terperinci Melaksanakan Jujukan Fibonacci dalam JavaScript: Pendekatan dan Variasi Biasa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!