فيبوناتشي حتى الأرقام

مستوحاة من تعليق تحت منشور فيبوناتشي للمقابلة . ذكر المستخدم pavellyzhin مهمة المقابلة التالية ( تعليق ):

منذ أكثر من عام ، استجاب "مبرمج php" للوظيفة الشاغرة ، وأرسلوا المعارف التقليدية وكانت هناك مهمة من فيبوناتشي: حدد جميع أرقام فيبوناتشي حتى في النطاق من 1 إلى 10000 . قررت استخدام حلقة (من أجل). هناك ، كان من الضروري أيضًا إجراء استعلام SQL لتحديد أقرب أعياد ميلاد المستخدمين ، لتعويض شيء ما ، لا أتذكر وأكتب نوعًا من الوظيفة. فعلت كل شيء ، أرسلها. أرسلوا إجابة: "وفقًا لنتائج مهمة الاختبار ، فأنت غير مقبول". بالضبط ما لم يعجبهم لم يكتب. الآن أنا جالس وأفكر ، ربما بعد كل شيء بسبب Fibonacci طرت ... :)

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

وضع نظرية في

أفضل طريقة للبدء هي النظر إلى عيون أرقام N Fibonacci الأولى ومحاولة إيجاد نمط في ترتيب الأرقام الزوجية.

$$

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

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

نثبت أن "كل رقم فيبوناتشي ثالث متساو ، والرقمان السابقان لكل رقم من هذا القبيل غريب".

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

هذه هي الطريقة التي يمكننا بها إثبات تخميننا دون حتى اللجوء إلى الحسابات الرياضية. يمكنك إضفاء الطابع الرسمي على هذه الفكرة ، في الوقت نفسه الحصول على صيغة لحساب كل رقم فيبوناتشي ثالث $$$F_ {n + 3}$ من $$$F_n$ و $$$F_ {n + 1}$ . باستخدام العلاقة العودية $$$F_ {n + 2} = F_ {n + 1} + F_ {n}$ حصلنا على:

$$

$$F_ {n + 3} = F_ {n + 2} + F_ {n + 1} = 2 F_ {n + 1} + F_n$$

إذا كان الأمر كذلك $$$F_n$ - حتى ذلك الحين $$$F_ {n + 3}$ أيضا حتى بحكم هذه الصيغة. بالنظر إلى ذلك $$$F_3 = 2 دولا$ ، إذن كل رقم فيبوناتشي ثالث هو حقًا ، وهو ما يؤكد جزءًا من تخميننا. تحتاج هنا إلى التأكد من أننا لا نفتقد الأرقام الزوجية الأخرى ، أي أنهم جميعا لديهم مضاعفات 3. بفضل janatem لفكرته البسيطة ، لأنه من الصيغة أعلاه ل $$$F_ {n + 3}$ كما أنه يتبع ذلك إذا $$$F_n$ - غريب إذن $$$F_ {n + 3}$ غريب أيضًا ، لذلك نحصل على هذه الأرقام بالأرقام $$$3k-2،3k-1، k \ in \ mathbb {N}$ - غريب (عن طريق الاستقراء ، تبدأ بـ $$$F_1 = F_2 = 1 دولا$ - غريب) ، و $$ - حتى ، الذي يغطي جميع أرقام فيبوناتشي ، مما يعني أننا نغطي حقا جميع الأرقام الزوجية.

هناك طريقة أخرى ، حيث سيكون من الممكن إظهار أنه لا توجد أرقام زوجية أخرى. لنفترض أن هناك عددا $$$F_m$ - حتى و $$$0 \ not \ equiv m \ mod 3$ ثم $$$م = 3 آلاف - 1 دولا$ أو $$$m = 3k + 1$ حيث $$$ك$ - نوع من الطبيعي.

دعنا ننتقل إلى تمثيل مصفوفة أرقام فيبوناتشي من المشاركة الأصلية

$$

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

حساب المحدد لكلا الجزأين ، نحصل عليه

$$

$$(-1) ^ n = F_ {n + 1} F_ {n-1} -F_n ^ 2$$

ويترتب على ذلك قسمة الأرقام $$$F_ {n + 1} ، F_n$ و $$$F_ {n-1} ، F_n$ فواصل المباراة $$$(- 1) ^ n$ ، أي أرقام فيبوناتشي المجاورة بسيطة بشكل متبادل. وهذا يعني أيضا أن البساطة والأرقام المتبادلة $$$F_ {3k} ، F_ {3k-1}$ و $$$F_ {3k} ، F_ {3k + 1}$ ، أي $$$F_ {3k}$ و $$$F_m$ . ولكن عن طريق الافتراض $$$F_m$ - حتى و $$$F_ {3k}$ - حتى كما ثبت سابقا. حتى الأرقام الأخرى من $$$F_ {3k}$ حيث $$$k \ in \ mathbb {N}$ في تسلسل فيبوناتشي غير موجود. وأقمنا أيضًا حقيقة مثيرة للاهتمام وهي أن أرقام فيبوناتشي المجاورة بسيطة ومتبادلة.

أخيرًا ، نعرض طريقة واحدة على الأقل لإثبات تخميننا: استخدم نظرية Luke.

نظرية لوقا . عدد صحيح يقسم $$$F_m$ و $$$F_n$ ، إذا وفقط إذا كان المقسوم عليه $$$F_d$ حيث $$$d = \ gcd (م ، ن)$ على وجه الخصوص

$$

$$\ gcd (F_m، F_n) = F _ {\ gcd (m، n)}$$

هنا $$$\ gcd$ هو أكبر عامل مشترك. إذا وضعت $$$م = 3 دولارا$ ثم $$$\ gcd (2، F_n) = F _ {\ gcd (3، n)}$ . إذا $$$F_n$ - حتى ، إذا كان الجانب الأيسر هو 2 ، بحيث يساوي الجانب الأيمن أيضًا 2 ، فمن الضروري ذلك $$$ن$ مقسوما على 3 وفي الوقت نفسه العكس هو الصحيح. وبالتالي ، نحصل على ما نريد إثباته بالضبط.

لذلك ، كل رقم فيبوناتشي ثالث متساوٍ ، وكل واحد لديه مضاعفات ثلاثة. لقد أثبتنا ذلك بعناية ولا يجرؤ أحد على الشك في الأمر الآن.

خوارزمية

والآن يبقى التوصل إلى خوارزمية. يمكنك بالطبع القيام بما فعله pavellyzhin في الأصل ، ولكن بدلاً من التحقق $$$0 \ equiv F_n \ mod 2$ يمكننا التحقق $$$0 \ equiv n \ mod 3$ ، هذا تطور! صحيح ، هذا لا يؤثر على عدد التكرارات للخوارزمية ، لأننا قمنا بتغيير مرشح التسلسل. من الأفضل إنشاء مجموعة من أرقام فيبوناتشي على الفور مع الخاصية التي نحتاجها (التكافؤ) ، لذلك هناك طريقة أخرى واضحة تتمثل في استخدام صيغة Binet

$$

$$F_n = \ left \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ right \ rceil ، \ qquad n \ in \ {3،6 ، \ ldots ، 3k \ ldots \}$$

هناك صعوبات في كفاءة الحسابات ، المزيد حول هذا الموضوع في المشاركة الأصلية. لذلك ، أقترح الطريقة الأفضل - في رأيي - الحساب التكراري $$$F_ {n + 3}$ ، يمكن القيام بذلك ، كما أوضحنا سابقًا ، بواسطة الصيغة $$$F_ {n + 3} = 2F_ {n + 1} + F_n$ . لإنشاء انتقال تكراري في الخوارزمية ، نحتاج إلى حساب $$$F_ {n + 4}$ كل شيء بسيط

$$

$$F_ {n + 4} = F_ {n + 3} + F_ {n + 2} = 2F_ {n + 1} + F_n + F_ {n + 1} + F_n = 3F_ {n + 1} + 2F_n$$

بالمناسبة ، بشكل عام ، من السهل إثبات ذلك

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n$$

ثم يتم كتابة الخوارزمية رسميًا على النحو التالي (رقم فيبوناتشي الحالي حتى $$$F_n$ تليها رقم فيبوناتشي $$$F_ {n + 1}$ . $$$M$ هو الحد الأعلى للأرقام الواردة في حالة المشكلة):

1. $$$F_n \ leftarrow F_3 = 2 ، \ quad F_ {n + 1} \ leftarrow F_4 = 3$
2. إذا $$$F_n> M$ ، ثم الانتهاء ، وإلا إضافة إلى النتيجة $$$F_n$
3. $$$(F_n ، F_ {n + 1}) \ leftarrow (2F_ {n + 1} + F_n ، 3F_ {n + 1} + 2F_n)$ انتقل إلى الخطوة 2.

الخوارزمية تافهة للغاية - فنحن ببساطة نقفز على كل رقم فيبوناتشي ثالث وطبعه (إذا لم يكن أكثر $$$M$ ). لا يزال تعقيد الخوارزمية خطيًا ، لكن عدد مرات تكرار الخطوة 2 يساوي تمامًا عدد أرقام فيبوناتشي حتى في النطاق $$$1 \ ldots M$ ، للمقارنة ، تتطلب خوارزمية بسيطة مع التكرار 3 مرات أكثر تكرار (لكل وجدت ، سيكون هناك 2 المهملة).

الخوارزمية موجودة على الورق ، ماذا كانت المقابلة ، PHP؟ حسنا ، كشف أخيرا يعني PHP

function evenfibs($ubound) { $result = []; [$evenf, $nextf] = [2, 3]; while($evenf <= $ubound) { array_push($result, $evenf); [$nextf, $evenf] = [ 3 * $nextf + 2 * $evenf, 2 * $nextf + $evenf]; } return $result; } 

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

$$

$$F_ {n + 3} = 2F_ {n + 1} + F_ {n} = 3F_n + 2F_ {n-1} = 3F_n + F_ {n-1} + F_ {n-1} = \\ 3F_n + ( F_ {n-1} + F_ {n-2}) + F_ {n-3} = 4F_n + F_ {n-3}$$

 function evenfibs($ubound) { if($ubound < 2) return []; $evens = [2]; $next = 8; for($i = 1; $next <= $ubound; $i++) { $evens[$i] = $next; $next = $evens[$i]*4 + $evens[$i-1]; } return $evens; } 

تعميم

ذكرنا هنا نظرية لوقا ، التي تنص على ذلك $$$\ gcd (F_m، F_n) = F _ {\ gcd (m، n)}$ . نتيجة لذلك ، يمكننا الحصول على رقم فيبوناتشي $$$F_n$ مضاعفات $$$F_m$ ، إذا وفقط إذا كان عددها $$$ن$ مضاعفة للرقم $$$م دولا$ . أي يتم تقسيم كل رقم رابع فيبوناتشي على 3 ، كل 5 في 5 ، كل 6 في 8 ، إلخ.

ثم ، بطريقة بسيطة ، نحصل على خوارزمية لحساب فيبوناتشي لاحقة ، والتي تكون فيها العناصر مضاعفات لعدد معين $$$F_m$ . باستخدام حقيقة ذلك

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n \\ F_ {n + m + 1} = F_ {m + 1} F_ {n + 1} + F_mF_n$$

الخوارزمية السابقة يتحول إلى

1. $$$F_n \ leftarrow F_m ، \ quad F_ {n + 1} \ leftarrow F_ {m + 1}$
2. إذا $$$F_n> M$ ، ثم الانتهاء ، وإلا إضافة إلى النتيجة $$$F_n$
3. $$$(F_n ، F_ {n + 1}) \ leftarrow (F_mF_ {n + 1} + F_ {m-1} F_n ، F_ {m + 1} F_ {n + 1} + F_mF_n)$ انتقل إلى الخطوة 2.

حيث $$$F_ {m-1} ، F_m ، F_ {m + 1}$ يمكن تعيين الثوابت.

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

$$

$$F_ {n + 1} = F_n + F_ {n-1} \\ F_ {n + 2} = 3F_ {n} - F_ {n-2} \\ F_ {n + 3} = 4F_ {n} + F_ {n-3} \\ F_ {n + 4} = 7F_ {n} - F_ {n-4} \\ F_ {n + 5} = 11F_ {n} + F_ {n-5} \\ \ cdots \\ F_ {n + t} = (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt}$$

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

$$

$$F_ {n + t + 1} = F_ {n + t} + F_ {n + t-1} = \\ (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt} + \\ (F_ {t-1} + 2F_ {t-2}) F_n + (-1) ^ {t-2} F_ {n-t + 1} = \\ (F_t + F_ { t-1} + 2 (F_ {t-1} + F_ {t-2})) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {n-t + 1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {nt} -F_ {nt-1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ tF_ {nt-1}$$

شيء مثل المجموع

المهمة بالطبع اصطناعية تمامًا ، وعدد التكرارات صغير جدًا (من أجل $$$M = 10000 دولا$ يحتوي الجواب على 6 أرقام فقط ، أي كان من الممكن إتمام 6 تكرارات ، وستحتاج الخوارزمية الأصلية "المباشرة" إلى 18) ، ولكن بهذه الطريقة يمكن للمستخدم الذي اكتشف شيئًا جديدًا هنا أن يُظهر الآن معرفة رياضية أعمق قليلاً بأرقام فيبوناتشي في المقابلة.

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