أرقام فيبوناتشيهي سلسلة من الأرقام كل رقم تالٍ فيها يساوي مجموع الرقمين السابقين: 1، 1، 2، 3، 5، 8، 13، .... في بعض الأحيان تبدأ السلسلة من الصفر: 0، 1، 1، 2، 3، 5، ... . في في هذه الحالةسوف نلتزم بالخيار الأول.

صيغة:

ف 1 = 1
ف 2 = 1
الجبهة الوطنية = الجبهة الوطنية-1 + الجبهة الوطنية-2

مثال الحساب:

ف 3 = ف 2 + ف 1 = 1 + 1 = 2
ف 4 = ف 3 + ف 2 = 2 + 1 = 3
ف 5 = ف 4 + ف 3 = 3 + 2 = 5
ف 6 = ف 5 + ف 4 = 5 + 3 = 8
...

حساب العدد n من سلسلة فيبوناتشي باستخدام حلقة while

1. قم بتعيين المتغيرين fib1 و fib2 بقيم العنصرين الأولين في السلسلة، أي قم بتعيين المتغيرات.
2. اطلب من المستخدم رقم العنصر الذي يريد الحصول على قيمته. قم بتعيين رقم للمتغير n.
3. بكمل الخطوات التاليةن - مرتين، حيث تم أخذ العنصرين الأولين في الاعتبار بالفعل:
   1. أضف fib1 وfib2، وقم بتعيين النتيجة إلى متغير تخزين مؤقت، على سبيل المثال fib_sum.
   2. اضبط المتغير fib1 على fib2 .
   3. اضبط المتغير fib2 على fib_sum .
4. عرض قيمة fib2 .

ملحوظة.إذا أدخل المستخدم 1 أو 2، فلن يتم تنفيذ نص الحلقة أبدًا وستتم طباعة القيمة الأصلية لـ fib2 على الشاشة.

fib1 = 1 fib2 = 1 n = input() n = int(n) i = 0 بينما i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)

نسخة مضغوطة من الكود:

fib1 = fib2 = 1 n = int (الإدخال ( "رقم عنصر سلسلة فيبوناتشي:") ) - 2 بينما n > 0 : fib1، fib2 = fib2، fib1 + fib2 n -= 1 طباعة (fib2)

طباعة أرقام فيبوناتشي باستخدام حلقة for

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

fib1 = fib2 = 1 n = int (الإدخال () إذا كان n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()

مثال التنفيذ:

10 1 1 2 3 5 8 13 21 34 55

حساب العدد النوني من سلسلة فيبوناتشي بشكل متكرر

1. إذا كان n = 1 أو n = 2، قم بإرجاع واحد إلى الفرع المتصل، حيث أن العنصرين الأول والثاني من سلسلة فيبوناتشي يساويان واحدًا.
2. في جميع الحالات الأخرى، قم باستدعاء نفس الوظيفة باستخدام الوسيطات n - 1 و n - 2. قم بإضافة نتيجة الاستدعاءين وإعادتها إلى فرع برنامج الاستدعاء.

Def fibonacci(n) : if n in (1 , 2 ) : إرجاع 1 إرجاع فيبوناتشي(n - 1 ) + فيبوناتشي(n - 2 ) طباعة (فيبوناتشي(10 ) )

لنفترض أن n = 4. ثم سيكون هناك استدعاء متكرر لفيبوناتشي (3) وفيبوناتشي (2). سيُرجع الثاني واحدًا، وسيؤدي الأول إلى استدعاء دالتين إضافيتين: فيبوناتشي (2) وفيبوناتشي (1). ستُرجع كلتا المكالمتين مكالمة واحدة، ليصبح المجموع مكالمتين. لذا فإن استدعاء فيبوناتشي (3) يعيد الرقم 2، الذي يضاف إلى الرقم 1 من استدعاء فيبوناتشي (2). يتم إرجاع النتيجة 3 إلى الفرع الرئيسي للبرنامج. العنصر الرابع من سلسلة فيبوناتشي يساوي ثلاثة: 1 1 2 3.

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

الكود مخصص لـ Python 3، على الرغم من أنه يجب أن يعمل أيضًا مع Python 2.

في البداية دعني أذكرك بالتعريف:

الجبهة الوطنية = الجبهة الوطنية-1 + الجبهة الوطنية-2

و ف1 = ف2 =1.

صيغة مغلقة

سوف نتخطى التفاصيل، ولكن يمكن للمهتمين التعرف على اشتقاق الصيغة. الفكرة هي أن نفترض أن هناك بعض x حيث F n = x n ثم ابحث عن x.

ماذا يعني ذلك

تقليل × ن -2

حل المعادلة التربيعية:

هذا هو المكان الذي تنمو فيه "النسبة الذهبية" ϕ=(1+√5)/2. باستبدال القيم الأصلية وإجراء المزيد من العمليات الحسابية، نحصل على:

وهو ما نستخدمه لحساب Fn.

من __future__ قسم الاستيراد استيراد الرياضيات def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int(PHI ** n / SQRT5 + 0.5)

جيد:
سريع وسهل للصغار
السيئة:
عمليات النقطة العائمة مطلوبة. سيتطلب n الكبير دقة أكبر.
شر:
يعد استخدام الأعداد المركبة لحساب F n أمرًا جميلًا من وجهة نظر رياضية، ولكنه قبيح من وجهة نظر الكمبيوتر.

العودية

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

فيب = لامدا ن: فيب (ن - 1) + فيب (ن - 2) إذا ن > 2 وإلا 1

جيد:
تطبيق بسيط جدًا يتبع التعريف الرياضي
السيئة:
وقت التنفيذ الأسي. بالنسبة للحجم الكبير فهو بطيء جدًا
شر:
تجاوز سعة المكدس

الحفظ

يواجه حل العودية مشكلة كبيرة: الحسابات المتداخلة. عند استدعاء fib(n)، يتم حساب fib(n-1) وfib(n-2). ولكن عندما يتم حساب fib(n-1)، فسيتم حساب fib(n-2) مرة أخرى بشكل مستقل - أي أنه يتم حساب fib(n-2) مرتين. إذا واصلنا الجدال، فسنرى أنه سيتم حساب fib(n-3) ثلاث مرات، وما إلى ذلك. التقاطعات كثيرة جدًا.

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

M = (0: 0، 1: 1) def fib(n): إذا n في M: إرجاع M[n] M[n] = fib(n - 1) + fib(n - 2) إرجاع M[n]

(في بايثون، يمكن القيام بذلك أيضًا باستخدام أداة الديكور، functools.lru_cache.)

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

البرمجة الديناميكية

وبعد الحل مع الحفظ يتبين أننا لسنا بحاجة إلى جميع النتائج السابقة، بل إلى النتيجتين الأخيرتين فقط. أيضًا، بدلاً من البدء من fib(n) والرجوع للخلف، يمكنك البدء من fib(0) والمضي قدمًا. يحتوي التعليمة البرمجية التالية على وقت تنفيذ خطي واستخدام ثابت للذاكرة. من الناحية العملية، ستكون سرعة الحل أعلى، نظرًا لعدم وجود استدعاءات دوال متكررة والعمل المرتبط بها. والكود يبدو أبسط.

غالبًا ما يتم الاستشهاد بهذا الحل كمثال للبرمجة الديناميكية.

Def fib(n): a = 0 b = 1 لـ __ في النطاق (n): a، b = b، a + b يُرجع a

جيد:
يعمل بسرعة مع رمز n صغير وبسيط
السيئة:
لا يزال وقت التنفيذ الخطي
شر:
لا شيء خاص.

جبر المصفوفة

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

وتعميم هذا يقول ذلك

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

فلماذا هذه الصيغة مفيدة؟ لأن الأسي يمكن أن يتم في الزمن اللوغاريتمي. ويتم ذلك من خلال التربيع. النقطة هي أن

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

Def pow(x, n, I, mult): """ إرجاع x إلى قوة n. بافتراض أن I هي مصفوفة الهوية التي يتم ضربها بـ mult وأن n عدد صحيح موجب """ إذا n == 0: إرجاع I elif n == 1: إرجاع x else: y = pow(x, n // 2, I, mult) y = multi(y, y) إذا n % 2: y = multi(x, y) إرجاع y defident_matrix (n): """إرجاع مصفوفة هوية n بواسطة n""" r = list(range(n)) return [ for j in r] def Matrix_multiply(A, B): BT = list(zip(*B) ) إرجاع [ للصف_a في A] def fib(n): F = pow([, ], n,identity_matrix(2),Matrix_multiply) إرجاع F

جيد:
حجم الذاكرة ثابت، والوقت اللوغاريتمي
السيئة:
الرمز أكثر تعقيدًا
شر:
عليك أن تتعامل مع المصفوفات، على الرغم من أنها ليست بهذا السوء

مقارنة الأداء

يجدر مقارنة متغير البرمجة الديناميكية والمصفوفة فقط. إذا قارناها بعدد الأحرف في الرقم n، يتبين لنا أن حل المصفوفة خطي، والحل بالبرمجة الديناميكية هو حل أسي. ومن الأمثلة العملية على ذلك حساب fib(10 ** 6)، وهو رقم سيحتوي على أكثر من مائتي ألف رقم.

ن=10**6
حساب fib_matrix: يحتوي fib(n) على 208988 رقمًا فقط، واستغرق الحساب 0.24993 ثانية.
حساب fib_dynamic: يحتوي fib(n) على 208988 رقمًا فقط، واستغرق الحساب 11.83377 ثانية.

ملاحظات نظرية

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

لنحسب عدد المسارات ذات الطول n من A إلى B. على سبيل المثال، بالنسبة إلى n = 1 لدينا مسار واحد، 1. بالنسبة إلى n = 2 لدينا مسار واحد مرة أخرى، 01. بالنسبة إلى n = 3 لدينا مساران، 001 و 101 يمكن أن نبين بكل بساطة أن عدد المسارات ذات الطول n من A إلى B يساوي تمامًا F n. بعد كتابة مصفوفة المجاورة للرسم البياني، نحصل على نفس المصفوفة التي تم وصفها أعلاه. إنها نتيجة معروفة من نظرية الرسم البياني أنه، في ضوء مصفوفة المجاورة A، فإن التكرارات في A n هي عدد المسارات ذات الطول n في الرسم البياني (إحدى المشاكل المذكورة في فيلم Good Will Hunting).

لماذا توجد مثل هذه العلامات على الأضلاع؟ اتضح أنه عندما تفكر في تسلسل لا نهائي من الرموز على تسلسل لا نهائي من المسارات ذهابًا وإيابًا على الرسم البياني، فإنك تحصل على ما يسمى "التحولات الفرعية من النوع المحدود"، وهو نوع من نظام الديناميكيات الرمزية. يُعرف هذا التحول الفرعي المحدد من النوع المحدود باسم "تحول النسبة الذهبية"، ويتم تحديده بواسطة مجموعة من "الكلمات المحرمة" (11). بمعنى آخر، سوف نحصل على تسلسلات ثنائية لا نهائية في كلا الاتجاهين ولن يكون هناك أي أزواج منها متجاورة. الإنتروبيا الطوبولوجية لهذا النظام الديناميكي تساوي النسبة الذهبية ϕ. ومن المثير للاهتمام كيف يظهر هذا الرقم بشكل دوري في مجالات مختلفة من الرياضيات.

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

int fibo(int n) ( if (n == 1 || n == 2) ( return 1; ) else ( return fibo(n - 1) + fibo(n - 2); ) )

دعونا نفكر في سبب حدوث ذلك. على سبيل المثال، لحساب فيبو (30)، نقوم أولاً بحساب فيبو (29) وفيبو (28). ولكن في الوقت نفسه، "ينسى" برنامجنا أننا فيبو (28). محسوبة بالفعلعند البحث عن فيبو (29).

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

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

ذاكرة التخزين المؤقت كثافة العمليات؛ int fibo(int n) ( if (cache[n] == 0) ( if (n == 1 || n == 2) (ذاكرة التخزين المؤقت[n] = 1;) آخر (ذاكرة التخزين المؤقت[n] = fibo(n - 1) + fibo(n - 2 ) إرجاع ذاكرة التخزين المؤقت[n];

نظرًا لأننا في هذه المشكلة نضمن حاجتنا إلى القيمة (N-1) لحساب القيمة N، فلن يكون من الصعب إعادة كتابة الصيغة في شكل تكراري - سنقوم ببساطة بملء المصفوفة في صف واحد حتى نصل إلى القيمة المطلوبة خلية:

<= n; i++) { cache[i] = cache + cache; } cout << cache;

الآن يمكننا أن نلاحظ أنه عندما نحسب قيمة F(N) فإن قيمة F(N-3) مضمونة لنا بالفعل أبداًلن تكون هناك حاجة. أي أننا نحتاج فقط إلى تخزين قيمتين في الذاكرة - F(N-1) و F(N-2) . علاوة على ذلك، بمجرد قيامنا بحساب F(N)، فإن تخزين F(N-2) يفقد كل معناه. دعونا نحاول كتابة هذه الأفكار في شكل رمز:

// القيمتان السابقتان: int Cache1 = 1; ذاكرة التخزين المؤقتة 2 = 1؛ // قيمة جديدة int Cache3; من أجل (int i = 2؛ i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>بعد التكرار، سوف تفقد ذاكرة التخزين المؤقت 2 أهميتها، أي. يجب أن تصبح ذاكرة التخزين المؤقت 1 // بمعنى آخر، ذاكرة التخزين المؤقت 1 - f(n-2)، ذاكرة التخزين المؤقت 2 - f(n-1)، ذاكرة التخزين المؤقت 3 - f(n).<< cache3;

// Let N=n+1 (الرقم الذي نحسبه في التكرار التالي). ثم n-2=N-3، n-1=N-2، n=N-1.

// وفقًا للحقائق الجديدة، نعيد كتابة قيم متغيراتنا: Cache1 = Cache2;<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;

Cache2 = Cache3; ) كوت

سوف يفهم المبرمج ذو الخبرة أن الكود أعلاه، بشكل عام، هراء، حيث لا يتم استخدام ذاكرة التخزين المؤقت 3 أبدًا (يتم كتابتها على الفور في ذاكرة التخزين المؤقت 2)، ويمكن إعادة كتابة التكرار بأكمله باستخدام تعبير واحد فقط:< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;

ذاكرة التخزين المؤقت = 1؛ ذاكرة التخزين المؤقت = 1؛ من أجل (int i = 2؛ i

بالنسبة لأولئك الذين لا يستطيعون فهم كيفية عمل السحر مع البقايا، أو يريدون فقط رؤية صيغة غير واضحة، هناك حل آخر:

إنت س = 1؛ كثافة العمليات ص = 1؛ من أجل (int i = 2؛ i

حاول مراقبة تنفيذ هذا البرنامج: ستقتنع بصحة الخوارزمية.