مقابلة فيبوناتشي

يعد حساب سلسلة Fibonacci مهمة حسابية كلاسيكية ، لأنه غالبًا ما يتم تقديمه في المقابلات عندما يرغبون في التحقق من أن المرشح ، من حيث المبدأ ، قادر على الأقل بطريقة ما على الخوارزميات. افترض أنك نفس المرشح. لقد أعطيت لك المهمة: في JavaScript ، اكتب دالة fib(n) تُرجع رقم Fibonacci nth. نحن نعتبر أن رقم فيبوناتشي صفر هو صفر. التحقق من صحة الوسيطة غير مطلوب. ما هي الخيارات التي لديك؟

1. لتكون أسهل ، وسوف يصل الناس لك.

الحل الأبسط هو دورة عادية.

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; } 

مزحة. بالطبع ، لست بحاجة إلى الكتابة بهذا الشكل - إلا إذا لم تتم مقابلتك بالطبع لموقف التشويش المتفرغ.

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; } 

هل تنفد الكوبونات المتغيرة؟ cypok

حسنًا ، حسنًا ، لمزيد من سهولة القراءة ، دعنا نكتب هذا:

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; } 

هذا خيار كلاسيكي وبسيط وأنيق. ولكن ربما تريد إظهار معرفتك ببعض المفاهيم الأخرى؟ على سبيل المثال ...

2. لفهم العودية ، يجب أن تفهم العودية

على سبيل المثال ، نعم ، يمكنك إثبات أنه يمكنك القيام بالتكرار. على سبيل المثال ، مثل هذا:

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } 

تذكر هذا الخيار. هذا لا يستحق القيام به. لا ينبغي أن يكون. هذا مستحيل. أبدا. هذا أسوأ من ركل الجراء ، ويمكن مقارنته بمحرقة صغيرة.

قد تسأل لماذا. في هذه الحالة ، ما عليك سوى تشغيل هذا الرمز ومحاولة حساب رقم Fifty Fibonacci ، على سبيل المثال. أعتقد أنك سوف تشعر ببعض التأخير. مزحة. أعتقد أنه إذا قمت بتشغيل هذا الرمز وليس على جهاز كمبيوتر فائق ، فإنك ببساطة لن تنتظر النتيجة. على الرغم من أن الكود البسيط غير العودي من الأمثلة السابقة سوف يحسب العضو الخمسين في تسلسل فيبوناتشي بشكل أسرع مما لديك الوقت لقول كلمة "خمسين" أو أي مقطع لفظي.

يتم التعبير عن هذا الحل بلغة O (e ⁿ ) معبراً بلغة O-تدوين تقريبية. أي أن وقت تنفيذ هذه الوظيفة يزداد باطراد مع زيادة n. وهذا هو ، عندما يزيد n ، يزداد وقت التنفيذ. بمعنى تقريبي ، إذا كان يتعين على fib(45) الانتظار لمدة ساعة ، ثم fib(46) سوف تنتظر ساعتين ، و fib(47) - 4 ساعات ، وهكذا. لقد مضغت في مثل هذه التفاصيل أن كل قارئ ، حتى كاتب الطباعة الذي جرب يده أولاً في كتابة النصوص ، يمكنه أن يدرك رعب الوضع.

هذا صحيح ، ولكن وقحا للغاية. يمكنك الحصول على تقدير أكثر دقة لعدد المكالمات إلى الدالة ~ (1 + sqrt (5)) fib (n) والملاحظة الجميلة "لحساب رقم Fibonacci باستخدام طريقة تكرارية ساذجة ، فأنت بحاجة إلى مكالمات دالة 3.2 مرة أكثر من رقم Fibonacci نفسه." طاؤوس

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

إذا طُلب منك حل هذه المشكلة بشكل متكرر أثناء المقابلة ، فمن المحتمل أن يكون هذا فخًا. قد تبدو العودية "الصحيحة" التي تعمل في الوقت الخطي ، على سبيل المثال ، كما يلي:

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0]; 

لتلخيص: على الرغم من حقيقة أن أرقام فيبوناتشي هي مثال كلاسيكي ، كتابي عن العودية ، في الواقع ليست هذه هي الحالة الأكثر ملاءمة لتطبيق العودية. ولكن يمكنك محاولة إظهار بعض المعرفة.

3. وظيفة التذكارية

هناك طريقة سحرية تحول حلاً غير فعال بشكل رهيب من الفقرة الأخيرة إلى حل سريع للغاية (وإن لم يكن بدون مشاكل). اسمه هو تحفيظ. وإذا كنت تتحدث الروسية - نتذكر فقط نتائج المكالمات السابقة بدلاً من حسابها مرة أخرى.

في الأساس ، لا يمكننا حتى تغيير أي شيء داخل هذا الحل - فقط أضف وظيفة التفاف memoize . هنا ، من أجل الوضوح ، أستخدم نسختها المبسطة لوظيفة ذات وسيطة واحدة.

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

فويلا! الآن وظيفة fib لديه حق الوصول إلى كائن cache خلال الإغلاق. إذا تم استدعاؤه بوسيطة لم تتم مواجهتها من قبل ، يتم تخزين القيمة المحسوبة في cache . مع استدعاءات الدوال الجديدة ذات الوسيطة نفسها ، لا يلزم إعادة حساب القيمة ، بل ستؤخذ ببساطة من ذاكرة التخزين المؤقت. كانت المشكلة الرئيسية في الدالة fib القديمة "السيئة" هي إعادة حساب القيم نفسها فيه عدة مرات. على سبيل المثال ، لحساب fib(45) ، كان من الضروري حساب f(44) مرة واحدة ، مرتين f(43) ، ثلاث مرات f(42) ، خمس مرات f(41) ، وما إلى ذلك.


لذلك ، سيتم الآن حساب القيم السابقة مرة واحدة ، وعندما يتم إعادة طلبها - فقط مأخوذة من ذاكرة التخزين المؤقت. هل يمكنك أن تتخيل مدى سرعة حساب عدد فيبوناتشي الخامس والأربعين؟ على محمل الجد ، في أي وقت تعتقد؟

في الواقع - أبطأ قليلا. لقد ارتكبت خطأً كلاسيكيًا عن عمد ، وغالبًا ما ارتكبت عند حفظ الوظائف العودية. عندما fib(45) استدعاء fib(45) "أسفل الغطاء" ، يتم oldFib(45) ، والذي يستدعي oldFib(44) و oldFib(43) لتلبية احتياجاته ... هل تشعر بالصيد؟ فيما يلي ، هناك بالفعل مكالمات إلى وظيفة عادية غير مذكّرة. بالطبع ، عند استدعاء fib(45) مرة أخرى ، نحصل على الفور على النتيجة من ذاكرة التخزين المؤقت - ومع ذلك ، فإن المكالمة الأولى لم تتسارع على الإطلاق. لإصلاح ذلك ، لا يزال يتعين عليك الحصول على oldFib أسفل زر مفتاح الربط:

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

! رائع الآن fib(45) أول مكالمة إلى fib(45) بسرعة مماثلة للإصدار مع حلقة. والتحديات الأخرى ستعمل بشكل عام في وقت ثابت ... عفوًا! خدع مرة أخرى. يعد الحصول على قيمة خاصية الكائن حسب المفتاح عملية سريعة ، ولكن لا يزال O (1) في المتوسط ​​فقط ، وفي أسوأ الحالات يمكن أن يتحلل إلى O (n). لجعلها جيدة جدًا ، في حالتنا ، يمكننا تغيير نوع cache من كائن إلى صفيف.

بالطبع ، لا ينبغي لأحد أن ينسى أن الحفظ يتطلب ذاكرة. وبينما نقوم بتقليل التعقيد الزمني ، يزداد تعقيد الذاكرة من O (1) إلى O (n).

كيف يمكن أن نتباهى؟ على سبيل المثال ، إظهار معرفتك العميقة بالرياضيات

4. السيد بينيت

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

$$

$$F_n = \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n - \ left (\ frac {1 - \ sqrt5} {2} \ right) ^ n} {\ sqrt5}$$

ومع ذلك ، فهي لغة رياضية تمامًا ، نكتبها في JavaScript:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; } 

دعنا نقود على الأرقام القليلة الأولى. عظيم ، يبدو أن كل شيء يعمل. هنا 13 ، هنا 21 ، هنا 34 ، هنا ... 54.9999999999999999؟

نعم ، بالطبع ، هذه النتيجة منطقية. صيغة Binet دقيقة رياضيا ، لكن الكمبيوتر يعمل بكسور من الدقة المحدودة ، ويمكن أن يتراكم خطأ أثناء العمليات معهم ، وهو ما حدث في هذه الحالة. ومع ذلك ، يمكننا إصلاحه. مع العلم أن الطرح في البسط سيكون دائمًا صغير الحجم ، يمكننا تبسيط الصيغة إلى الحالة التالية:

$$

$$F_n = \ left \ lfloor \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n} {\ sqrt5} \ right \ rceil$$

هنا الأقواس المربعة الغريبة التي لم تكتمل تعني أقرب عدد صحيح ، أي هو التقريب. أعد كتابة الكود:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); } 

نعم ، هذا أفضل بكثير. يمكننا أن نرى كلا من 55 و 89 ، وحتى رقم Fibonacci المفضل هو 144 (الذي أحبه لأنه يساوي 12 مربعًا). كل شيء سيكون على ما يرام حتى الرقم 76. الذي يجب أن يكون مساوياً 3416454622906707 ، وستحسب وظيفتنا 3416454622906706. نظرًا لأن مشكلة الدقة المحدودة للأرقام الكسرية لم تختف ، فقد دفعناها أعمق وأملنا ألا تأتي. كما يوضح هذا المثال ، كانوا يأملون عبثا.

في الواقع ، يمكننا أن نفعل شيئا آخر لحفظ هذه الطريقة. ولكن المزيد عن ذلك أدناه. في هذه الأثناء - النكات جانبا. دعونا نتحدث عن الطريقة القاسية والمتشددة والوحشية.

5. اتبع الأرنب الأبيض.

يقولون أنه إذا كانت لديك مشكلة وفكرة حدثت لك ، يمكنك حلها باستخدام تعبيرات منتظمة ، والآن لديك مشكلتان. المصفوفات هي تعبيرات منتظمة على العكس. العديد من المشاكل ، إذا تمت إعادة صياغتها بلغة المصفوفات ، يتم حلها بمفردها.

بالنسبة إلى أرقام فيبوناتشي ، بالنسبة لهم بلغة المصفوفة ، يمكنك كتابة هذه الهوية الواضحة:

$$

$$\ تبدأ {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} \ تبدأ {pmatrix} F_ {n - 1} \\ F_n \ end {pmatrix} = \ تبدأ {pmatrix} F_n \\ F_ {n +1} \ end {pmatrix}$$

وهذا هو ، إذا أخذنا زوجًا من أرقام فيبوناتشي المتتالية وضربناها بمصفوفة مباشرة ، فسوف نحصل على الزوج التالي. والنتيجة المنطقية تأتي من هذا: إذا أخذنا زوجًا من صفر وأرقام فيبوناتشي الأولى ، أي صفر وواحد ، وضربناهما في هذه المصفوفة على قوة nth ، فسنحصل على زوج من n و en بالإضافة إلى أول Fibonacci. وهذا هو ، يتحدث إنسانيا:

$$

$$\ start {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n \ start {pmatrix} 0 \\ 1 \ end {pmatrix} = \ start {pmatrix} F_n \\ F_ {n + 1} \ end {pmatrix}$$

يمكنك تبسيط هذا أكثر قليلاً عن طريق التخلي عن المتجهات. في الواقع ، يتم تضمين جميع القيم اللازمة في المصفوفة نفسها:

$$

$$\ تبدأ {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ start {pmatrix} F_ {n-1} & F_ {n} \\ F_ {n} & F_ {n + 1 } \ end {pmatrix}$$

عظيم ، أليس كذلك؟ يبقى أن نفهم ، ماذا عن وئام الحمار ، إذا لم يكن أوركسترا. يعني - لماذا هذه الصعوبات من اللون الأزرق. والجواب بسيط - التجديد السريع.

كم عدد عمليات الضرب الأولية التي يتطلبها حساب 2 ¹⁰ ؟ والشخص العادي يقول تسعة. مرتين - أربعة. مرتين أربعة - ثمانية. ثمانية هو ستة عشر. و هكذا. سوف يقول شخص ماكر أن أربعة.

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

سيقول المبرمج. أنه يتذكر هذا الرقم عن ظهر قلب ، وليس هناك حاجة إلى ضرب. ومع ذلك ، ناقشنا قضايا المذكرة أعلاه.

لذلك ، يمكن تطبيق التسوية السريعة أيضًا على المصفوفات ، وبالتالي يسمح لنا بتقليل التعقيد الزمني غير المقيد لوظيفتنا من O (n) إلى O (log n). وهذا رائع جدًا - ما لم يكن هذا التعقيد أمرًا مهمًا للغاية بالنسبة لنا بالطبع. دعنا نكتب الكود:

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; } 

لذلك حصلنا على أسرع الخوارزميات في الغرب المتوحش. وخلافا لمعظم السابقات ، يمكن إظهاره بطريقة غير مفارقة في مقابلة. وفي بعض الأماكن الرياضية الفسيحة ، يتوقع منك ذلك.

PS

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

والأكثر إثارة للاهتمام: إذا نظرت بعناية إلى الأرقام التي سيتم الحصول عليها في هذه العملية ، وما هي العمليات التي سيتم إجراؤها ، فسيصبح من الواضح أن هذه الطريقة هي نفس ضرب المصفوفة ، فقط تحت واجهة مختلفة. الفرق الوحيد هو ما إذا كنا نقوم بتخزين الأرقام في صفيفات ثنائية الأبعاد أو في حقول كائن من فئة خاصة.

هذا كل شيء. إذا كنت تعتقد أنني فاتني بعض الطرق الأخرى المثيرة للاهتمام للعثور على أرقام لا يحتاج إليها أحد ، فتأكد من الكتابة عنها في التعليقات.

هناك أيضا طريقة مثل مضاعفة سريع . إنه يعمل مثل ضرب المصفوفة في O (log) ، ولكن مع ثابت أصغر في التقارب (وفي الممارسة). باختصار ، يتم استخدام صيغتين هناك ، بالاعتماد على أحدهما يمكن أن يتراجع بسرعة إلى مرتين أقل من المؤشرات بشكل متكرر:

F _2n = F _n * (2 * F _{n + 1} - F _n )
F _{2n + 1} = F _n ² + F _{n + 1} ²

التنفيذ ، بالمناسبة ، مضغوط للغاية.

مقارنة سرعة الأساليب المختلفة

just_maksim