Fibonacci Number
تبدأ أعداد فيبوناتشي بـ F(0) = 0 وF(1) = 1، وكل عدد لاحق هو مجموع العددين السابقين له: F(n) = F(n-1) + F(n-2). تبدأ المتتالية بـ 0، 1، 1، 2، 3، 5، 8، 13. تستقبل دالتك n وتُرجع F(n).
الدالة
- ninteger
- الموضع في متتالية فيبوناتشي، بدءًا من 0
- تُرجعinteger
- عدد فيبوناتشي F(n)
القيود
0 ≤ n ≤ 45- الإجابة تقع ضمن نطاق عدد صحيح موقّع من 32 بت:
F(45) = 1134903170.
أمثلة
- المدخلات
- n = 4
- المخرجات
- 3
- الشرح
- عُدّ تصاعديًا بدءًا من البداية:
F(2) = 1 + 0 = 1، وF(3) = 1 + 1 = 2، وF(4) = 2 + 1 = 3.
- المدخلات
- n = 10
- المخرجات
- 55
- الشرح
- تتتابع القيم بدءًا من الفهرس 0 على النحو التالي: 0، 1، 1، 2، 3، 5، 8، 13، 21، 34، 55. العدد عند الفهرس 10 هو
34 + 21 = 55.
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك حساب F(n) في زمن O(log n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
احسب
F(5)يدويًا باستخدام التعريف递ي. ما القيم التي ينتهي بك الأمر إلى حسابها أكثر من مرة؟كل عدد من أعداد فيبوناتشي يحتاج فقط إلى العددين اللذين يسبقانه. إذا حسبتها بترتيب تصاعدي، فستكون كل قيمة تحتاج إليها معروفة بالفعل عندما تحتاج إليها.
ابدأ من
0و1. كرّرn-1مرة: اجمع العددين اللذين تحتفظ بهما، ثم تخلّص من الأقدم واحتفظ بالمجموع.
الحل
التعريف هو بالفعل دالة递帰ية، وكتابته بهذه الصورة يعطي الإجابة الصحيحة. لكن الفخ يكمن في زمن التنفيذ: إذ تعيد الاستدعاءان递帰يان العمل نفسه، ويزداد عدد الاستدعاءات أُسّيًا مع n. تعالج البرمجة الديناميكية ذلك بحساب كل عدد من أعداد فيبوناتشي مرة واحدة، من الأسفل إلى الأعلى. ولا تحتفظ الخطوة الأخيرة إلا بالعددين اللذين يحتاج إليهما العدد التالي.
الاستدعاء الذاتي مباشرةً من التعريف
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ترجم التعريف حرفيًا. fib(0) هو 0، وfib(1) هو 1، وأي قيمة أكبر تُرجع fib(n-1) + fib(n-2). تنتهي كل سلسلة من الاستدعاءات بإحدى الحالتين الأساسيتين، لذا تكون الإجابة صحيحة.
والآن احسب عدد الاستدعاءات. يستدعي fib(5) كلًا من fib(4) وfib(3)، لكن fib(4) يستدعي fib(3) مرة أخرى. في النهاية، يُنفَّذ fib(3) مرتين، وfib(2) ثلاث مرات، وfib(1) خمس مرات، ويُجري fib(5) ما مجموعه 15 استدعاءً. تُعاد حساب القيم نفسها مرارًا وتكرارًا.
يتبع عدد الاستدعاءات أعداد فيبوناتشي نفسها: يستلزم حساب F(n) إجراء 2 × F(n+1) - 1 استدعاءً. عندما تكون n = 45، يصل ذلك إلى نحو 3.7 × 10^9 استدعاء، وهو عدد كبير جدًا لاجتياز حدّ الوقت. يُكتب الحد عادةً على الصورة O(2^n)؛ أما النمو الدقيق فيبلغ نحو 1.618^n. لا يتجاوز عمق الاستدعاء التكراري n مستويات، لذا تحتاج المكدسة إلى مساحة O(n).
الخوارزمية
- إذا كانت قيمة
nهي0أو1، فأعِدn. - وإلا، فاستدعِ الدالة على
n-1وعلىn-2. - أعِد مجموع النتيجتين.
def fib(n):
if n < 2:
return n # F(0) = 0, F(1) = 1
return fib(n - 1) + fib(n - 2)املأ جدولًا من الأسفل إلى الأعلى
الفكرة
إن التكرار بطيء فقط لأنه ينسى. إذا كتبت كل عدد من أعداد فيبوناتشي عند حسابه للمرة الأولى، فلن يتطلب حساب كل عدد سوى عملية جمع واحدة. أنشئ جدولًا f يحتوي على خانات للفهرس من 0 إلى n، واجعل f[0] = 0 وf[1] = 1، واملأ بقية الخانات من اليسار إلى اليمين باستخدام f[i] = f[i-1] + f[i-2].
ترتيب التعبئة من اليسار إلى اليمين هو ما يجعل ذلك ينجح: فعندما تصل إلى f[i]، يكون العددان اللذان يحتاج إليهما موجودين بالفعل في الجدول. عندما تكون n = 10، يمتلئ الجدول بالقيم 0، 1، 1، 2، 3، 5، 8، 13، 21، 34، 55، وتكون الإجابة في الخانة الأخيرة.
هذا هو البرمجة الديناميكية في أبسط صورها: علاقة عودية بالإضافة إلى جدول لإجابات الحالات الأصغر. هناك n-1 عملية جمع، ويكون الزمن O(n)، ويحتوي الجدول على n + 1 عددًا، فتكون المساحة O(n). يستغرق n = 45 الآن 44 عملية جمع بدلًا من مليارات الاستدعاءات.
الخوارزمية
- إذا كان
nيساوي0أو1، فأعِدn. - أنشئ جدولًا من
n + 1عددًا، بحيث يكونf[0] = 0وf[1] = 1. - لكل
iمن 2 إلىn، عيّنf[i] = f[i-1] + f[i-2]. - أعِد
f[n].
def fib(n):
if n < 2:
return n
f = [0] * (n + 1) # f[i] will hold F(i)
f[1] = 1
for i in range(2, n + 1):
f[i] = f[i - 1] + f[i - 2]
return f[n]احتفظ بالعددين الأخيرين فقط
الفكرة
انظر إلى ما تقرؤه حلقة الجدول. لملء f[i] تحتاج إلى f[i-1] وf[i-2] ولا تحتاج إلى أي قيمة أقدم، لذا فإن كل خانة سابقة لا فائدة منها. استخدم متغيرين بدلًا من جدول: يحتفظ prev بالعدد الذي يسبق بخطوتين، ويحتفظ curr بالعدد الذي يسبق بخطوة واحدة.
ابدأ بـ prev = 0 وcurr = 1، وهما F(0) وF(1). في كل خطوة، احسب next = prev + curr، ثم حرّك الزوج إلى الأمام: يأخذ prev قيمة curr القديمة، ويأخذ curr قيمة next. عندما تكون n = 4، ينتقل الزوج من (0, 1) إلى (1, 1)، ثم (1, 2)، ثم (2, 3)، وتكون curr = 3 هي الإجابة.
يبقى العمل كما هو: n-1 عملية جمع، بزمن O(n)، مع ثلاثة أعداد صحيحة في الذاكرة، ومساحة O(1). ترتيب التحديثات مهم: إذا استبدلت prev قبل جمعه، فسيستخدم المجموع القيمة الخاطئة.
الخوارزمية
- إذا كانت قيمة
nهي0أو1، فأعدn. - عيّن
prev = 0وcurr = 1. - كرّر
n-1مرة: احسبnext = prev + curr، ثم عيّنprev = currوcurr = next. - أعِد
curr.
def fib(n):
if n < 2:
return n
prev, curr = 0, 1 # F(0) and F(1)
for _ in range(n - 1):
prev, curr = curr, prev + curr
return curr
أخطاء شائعة وحالات حدّية
متتالية فيبوناتشي هي المسألة الكلاسيكية الأولى في البرمجة الديناميكية، وتأتي معظم الأخطاء من الاستدعاء التعاودي أو من أول قيمتين.
- تسليم الحل التعاودي الساذج. يجتاز الاختبارات الصغيرة، ثم يحتاج إلى مليارات الاستدعاءات عند
n = 45. خزّن النتائج في جدول أو في متغيرين. - البدء بقيم خاطئة. هنا
F(0) = 0وF(1) = 1، لذاF(2) = 1وF(10) = 55. البدء بالتتابع 1، 1 يزيح كل إجابة بمقدار فهرس واحد. - إنشاء الجدول من دون معالجة خاصة لقيم
nالصغيرة. عندما تكونn = 0، لا يحتوي جدول حجمهn + 1 = 1على خانة لـf[1]، وكتابتها يتجاوز حدود الجدول. أعدnفورًا عندما يكونn < 2. - تحديث الزوج بترتيب خاطئ. يؤدي
prev = currمتبوعًا بـcurr = prev + currإلى جمع قيمةprevالجديدة ومضاعفةcurr. احسب المجموع أولًا فيnext، أو استخدم إسنادًا متزامنًا إذا كانت اللغة تدعمه. - تنفيذ خطوة إضافية. الحلقة التي تحسب أيضًا
F(n+1)تصل عند الحد إلىF(46) = 1836311903، وهذا العدد لا يزال يتسع في 32 بت بمحض الصدفة. أماF(47)فلا يتسع.
أسئلة شائعة4
ما هو التعقيد الزمني لدالة فيبوناتشي التكرارية؟
يُجري الاستدعاء التعاودي الساذج 2 × F(n+1) - 1 استدعاءً، وهو عدد ينمو مثل 1.618^n ويُكتب عادةً O(2^n). عند n = 45، يبلغ العدد نحو 3.7 × 10^9 استدعاء. تخزين كل نتيجة مرة واحدة، في جدول أو في متغيرين، يخفضه إلى O(n).
كيف تحل مسألة فيبوناتشي باستخدام البرمجة الديناميكية؟
ابدأ من العلاقة التكرارية F(n) = F(n-1) + F(n-2) واحسب القيم بترتيب تصاعدي لـ n، مع تخزين كل قيمة. يمكنك ملء جدول من الأسفل إلى الأعلى، أو الإبقاء على الدالة التكرارية وتخزين نتائجها مؤقتًا، وهذا ما يُسمى بالحفظ المؤقت للنتائج (memoization). في كلتا الحالتين، تُحسب كل قيمة مرة واحدة، لذا يكون إجمالي العمل O(n).
هل يمكن حساب متتالية فيبوناتشي باستخدام مساحة O(1)؟
نعم. يعتمد كل رقم على الرقمين السابقين له فقط، لذا يكفي استخدام متغيرين. احتفظ بآخر قيمتين وحدّثهما في كل خطوة. وهذا يعطي زمنًا قدره O(n) ومساحة إضافية قدرها O(1).
هل توجد طريقة أسرع من O(n)؟
نعم. تحتوي المصفوفة [[1, 1], [1, 0]] المرفوعة إلى الأس n على F(n) في الزاوية العلوية اليمنى، ويحسب التربيع المتكرر تلك القوة باستخدام O(log n) عملية ضرب للمصفوفات. توجد أيضًا صيغة مغلقة تستخدم قوى النسبة الذهبية، لكنها تعمل بالأعداد ذات الفاصلة العائمة وتفقد الدقة كلما كبرت قيمة n، لذا تُفضَّل الطرق المعتمدة على الأعداد الصحيحة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def fib(n):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
n = 4
المتوقع
3