كمطور، من المحتمل أنك واجهت مهمة كتابة دالة لحساب القيم في تسلسل فيبوناتشي. غالبًا ما تظهر هذه المشكلة الكلاسيكية في مقابلات البرمجة، وعادةً ما تطلب تنفيذًا متكررًا. ومع ذلك، قد يطلب القائمون على المقابلات في بعض الأحيان أساليب محددة. في هذه المقالة، سنستكشف تطبيقات تسلسل فيبوناتشي الأكثر شيوعًا في JavaScript.

ما هو تسلسل فيبوناتشي؟

أولاً، دعونا نقوم بتحديث ذاكرتنا. تسلسل فيبوناتشي عبارة عن سلسلة من الأرقام حيث كل رقم هو مجموع الرقمين السابقين. يبدأ بـ 0 و 1:

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

نُهج التنفيذ المشتركة

1. النهج العودي

الطلب الأكثر تقليدية هو التنفيذ العودي:

function fibonacciRecursive(n) {
  if (n 



على الرغم من أن هذا النهج واضح ومباشر، إلا أنه لا يكون فعالاً بالنسبة للقيم الكبيرة لـ n. على جهاز MacBook Pro i9 المزود بذاكرة وصول عشوائي (RAM) سعة 16 جيجابايت، استغرق حساب رقم فيبوناتشي الأربعين حوالي 1.5 ثانية:


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

VM379:3 Recursive: 1521.569091796875 ms




تسببت محاولة حساب الرقم الخمسين في عدم استجابة علامة تبويب Chrome.

2. النهج العودي مع التخزين المؤقت (الحفظ)

الإصدار التالي من هذا السؤال هو تحسين الأداء عن طريق إضافة آلية تخزين مؤقت إلى تطبيقنا العودي:


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



يقدم هذا الأسلوب كائنًا مخبأً بقيم أولية لـ 0 و1. بالنسبة لأي رقم معين، نتحقق أولاً مما إذا كنا قد حسبنا قيمة فيبوناتشي الخاصة به بالفعل. إذا كان الأمر كذلك، فإننا نعيد النتيجة المخزنة مؤقتًا بدلاً من إعادة حسابها. بخلاف ذلك، فإننا نحسب تلك القيمة ونخزنها في ذاكرة التخزين المؤقت.

تحسن الأداء كبير (بسبب الذاكرة الإضافية المستخدمة بالطبع). استغرق حساب رقم فيبوناتشي الأربعين حوالي 0.02 مللي ثانية:


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

VM382:3 Recursive, with caching: 0.01806640625 ms




3. النهج التكراري مع حلقة for  

هناك اختلاف شائع آخر وهو تنفيذ تسلسل فيبوناتشي باستخدام حلقة for:


function fibonacciWithIteration(n) {
    if (n 



هذا الأسلوب أسرع بكثير من الطريقة العودية الأساسية (التي لا تحتوي على تخزين مؤقت):


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-th كمصفوفة. دعونا ننفذ هذا باستخدام كل من الأساليب العودية والتكرارية.

النهج العودي


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]




 تعمل هذه الوظيفة على النحو التالي:

بالنسبة إلى 0 و1، نعيد المصفوفات المشفرة.
للحالات الأخرى:

• نحصل على التسلسل للرقم السابق ونخزنه في arr.
• نحسب القيمة الحالية عن طريق جمع القيمتين الأخيرتين من arr.
• نقوم بدمج arr وcurrentValue في مصفوفة جديدة ونعيدها.

النهج التكراري

function fibonacciSequenceWithIteration(n) {
  if (n 



 تعمل هذه الوظيفة على النحو التالي:

إذا كان الإدخال 0، فإننا نعيد مصفوفة تحتوي على العنصر 0 فقط.
للحالات الأخرى:

• نقوم بتهيئة المتغيرات السابقة والتالية لتخزين القيم السابقة والتالية.
• نقوم بإنشاء arr بالقيم الأولية [0, 1].
• نقوم بالتكرار من 2 إلى n، مع دفع مجموع السابق والمجاور لـ arr في كل تكرار.
• نقوم بتحديث القيم السابقة والتالية ونستمر في التكرار التالي.

خاتمة

بينما تغطي هذه المقالة العديد من تطبيقات تسلسل فيبوناتشي الشائعة، إلا أنها ليست قائمة شاملة. إذا واجهت اختلافات أخرى في المقابلات أو في عملك، فيرجى مشاركتها في التعليقات!

ابق على اطلاع بأحدث أخبار جافا سكريبت وتطوير البرمجيات! انضم إلى قناتي على Telegram لمزيد من الأفكار والمناقشات: TechSavvy: Frontend & Backend.