في الواقع ، تم تحديد أول رقمين فيبوناتشي مسبقًا. رقم فيبوناتشي الأول هو 0 ورقم فيبوناتشي الثاني هو 1. مع الفهرسة على أساس الصفر وافتراض أن أرقام فيبوناتشي موجودة في مصفوفة ، إذن:
في الفهرس 0 ، رقم فيبوناتشي هو 0 و ( محدد مسبقا ) ؛في الفهرس 1 ، رقم فيبوناتشي هو 1 و ( محدد مسبقا ) ؛
في الفهرس اثنين ، رقم فيبوناتشي هو 1 = 1 + 0 و ( حسب التعريف ) ؛
في الفهرس 3 ، رقم فيبوناتشي هو اثنين = 1 + 1 و ( حسب التعريف ) ؛
في الفهرس 4 ، رقم فيبوناتشي هو 3 = اثنين + 1 و ( حسب التعريف ) ؛
في الفهرس 5 ، رقم فيبوناتشي هو 5 = 3 + اثنين و ( حسب التعريف ) ؛
في الفهرس 6 ، رقم فيبوناتشي هو 8 = 5 + 3 و ( حسب التعريف ) ؛
في الفهرس 7 ، رقم فيبوناتشي هو 13 = 8 + 5 و ( حسب التعريف ) ؛
في الفهرس 8 ، رقم فيبوناتشي هو واحد وعشرين = 13 + 8 و ( حسب التعريف ) ؛
في الفهرس 9 ، رقم فيبوناتشي هو 3. 4 = واحد وعشرين + 13 و ( حسب التعريف ) ؛
وهلم جرا.
في البرمجة ، يتم استخدام المتغير n وليس i للفهارس الصفرية لأرقام فيبوناتشي هذه. وبذلك ، فإن أول اثني عشر رقمًا فيبوناتشي هي:
| 0 | 1 | 1 | اثنين | 3 | 5 | 8 | 13 | واحد وعشرين | 3. 4 | 55 | 89 |
| 0 | 1 | اثنين | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | أحد عشر |
يعطي الصف الثاني في الجدول الفهارس الصفرية ، كل منها يحتوي على المتغير n في البرمجة. يعطي الصف الأول أرقام فيبوناتشي المقابلة. لذا ، فإن أرقام فيبوناتشي ليست مجرد أرقام. يبدأ تعريف النواة بـ 0 ، لأول رقم فيبوناتشي و 1 لرقم فيبوناتشي الثاني. يتم إنتاج بقية الأرقام من هناك.
يمكن إنتاج أرقام فيبوناتشي في وقت O (n) وأيضًا في وقت O (1). بالنسبة لوقت O (n) ، إذا كان n هو 12 على سبيل المثال ، فسيتم إنتاج أول اثني عشر رقمًا فيبوناتشي. بالنسبة لوقت O (1) ، يتم إنتاج رقم واحد فيبوناتشي فقط. على سبيل المثال ، إذا كان n هو 6 ، فسيتم إنتاج رقم فيبوناتشي 8.
تشرح هذه المقالة هاتين الطريقتين لإنتاج أرقام فيبوناتشي في جافا.
صيغة لرقم فيبوناتشي
توجد معادلة رياضية لرقم فيبوناتشي. يمكن كتابة هذه الصيغة في ثلاثة أسطر أو سطر واحد. في ثلاثة أسطر ، هو مكتوب على النحو التالي:
حيث F ن هو رقم فيبوناتشي عند الصفر n العاشر فهرس. هذه هي الطريقة التي يتم بها تحديد رقم فيبوناتشي.
إنتاج أرقام فيبوناتشي بتوقيت O (n)
إذا تم إنتاج أرقام فيبوناتشي في O (3) مرات ، فسيتم إنتاج الأرقام ، 0 ، 1 ، 1 ؛ هذه هي أول ثلاثة أرقام فيبوناتشي. آخر ن العاشر الفهرس هنا هو 2. إذا تم إنتاج أرقام فيبوناتشي في O (7) مرات ، فسيتم إنتاج الأرقام 0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ؛ هذه هي أول سبعة أرقام فيبوناتشي. آخر ن العاشر الفهرس هنا ، هو 6. إذا تم إنتاج أرقام فيبوناتشي في O (n) مرات ، فسيتم إنتاج الأرقام 0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 - - - ؛ هذه هي أول أرقام فيبوناتشي n. آخر ن العاشر الفهرس هنا هو n-1.
طريقة Java في فئة لإنتاج أول أرقام فيبوناتشي n هي:
صف دراسي فيبوناتشي {فارغ فيبوناتشي ( int [ ] ص ) {
int ن = ص. الطول ؛
إذا ( ن > 0 )
ص [ 0 ] = 0 ؛
إذا ( ن > 1 )
ص [ 1 ] = 1 ؛
إلى عن على ( int أنا = اثنين ؛ أنا < ن ؛ أنا ++ ) { // n = 0 و n = 2 تم اعتبارهما
int تيار = ص [ أنا - 1 ] + ص [ أنا - اثنين ] ؛
ص [ أنا ] = تيار ؛
}
}
}
الصف ، فيبوناتشي خاص. ال فيبوناتشي () يأخذ الأسلوب الصفيف P ويعيد الفراغ. تبدأ الطريقة بتحديد طول المصفوفة. طول n هذا هو عدد أرقام فيبوناتشي المطلوبة. يتم تحديد أرقام فيبوناتشي الأولى والثانية بشكل صريح ويتم وضعها في الموضعين الأول والثاني في المصفوفة.
يتم تحديد باقي أرقام فيبوناتشي بدءًا من الرقم الثالث (الفهرس ، n = 2) في حلقة for-loop ويتم وضعها في مواقعها في المصفوفة. لذلك ، يجب أن تعيد الوظيفة الفراغ. تضيف العبارة الرئيسية في الحلقة for-loop الرقمين السابقين.
تم استخدام متغير الفهرس i بدلاً من n لغرض التوضيح.
فئة Java الرئيسية المناسبة (باستخدام طريقة Java الرئيسية) هي:
عام صف دراسي رئيسي {عام ثابتة فارغ رئيسي ( سلسلة أرجس [ ] ) {
int م = 12 ؛
int [ ] آر = الجديد int [ م ] ؛
هدف فيبوناتشي = الجديد فيبوناتشي ( ) ؛
الهدف. فيبوناتشي ( آر ) ؛
إلى عن على ( int أنا = 0 ؛ أنا < م ؛ أنا ++ )
نظام . خارج . مطبعة ( آر [ أنا ] + '' ) ؛
نظام . خارج . println ( ) ؛
}
}
بعد أن يتم إنتاج الأرقام باستخدام طريقة فيبوناتشي () ، تقوم طريقة جافا الرئيسية بقراءتها.
إنتاج رقم واحد فيبوناتشي في وقت ثابت
هناك معادلة رياضية يمكن استخدامها لإنتاج رقم فيبوناتشي ، عند إعطاء المؤشر المقابل ذي الأساس الصفري ، n. الصيغة هي:
حيث n هو الفهرس الصفري و Fib ن هو رقم فيبوناتشي المقابل. لاحظ أنه في الجانب الأيمن من المعادلة ، ليس الجذر التربيعي لـ 5 مرفوعًا للقوة n ؛ إنه التعبير الموجود بين الأقواس الذي يتم رفعه للقوة n. هناك نوعان من هذه التعبيرات.
إذا كانت n تساوي 0 ، فيبوناتشي ن سيكون 0. إذا كان n هو 1 ، فيبوناتشي ن سيكون 1. إذا كان n هو 2 ، فيبوناتشي ن سيكون 1. إذا كانت n تساوي 3 ، فيبوناتشي ن سيكون 2. إذا كان n هو 4 ، فيبوناتشي ن سيكون 3 - وهكذا. يمكن للقارئ التحقق من هذه الصيغة رياضيًا ، عن طريق استبدال قيم مختلفة لـ n وتقييمها.
عند ترميزها ، ستنتج هذه الصيغة رقم واحد فيبوناتشي لـ n. إذا كانت هناك حاجة إلى أكثر من رقم واحد فيبوناتشي ، فيجب استدعاء رمز الصيغة مرة واحدة لكل من الفهارس المقابلة المختلفة.
في Java ، طريقة إنتاج رقم واحد فيبوناتشي هي:
يستورد java.lang. * ؛صف دراسي فيب {
مزدوج فيب ( int ن ) {
مزدوج FibN = ( رياضيات . الأسرى ( ( 1 + رياضيات . الجذر التربيعي ( 5 ) ) / اثنين ، ن ) - رياضيات . الأسرى ( ( 1 - رياضيات . الجذر التربيعي ( 5 ) ) / اثنين ، ن ) ) / رياضيات . الجذر التربيعي ( 5 ) ؛
إرجاع FibN ؛
}
}
يجب استيراد الحزمة java.lang. * في بداية البرنامج. هذا لأن الحزمة تحتوي على فئة الرياضيات ، والتي لها طرق power (pow) والجذر التربيعي (sqrt). تقوم طريقة Java المخصصة هنا بتنفيذ الصيغة الرياضية مباشرة.
التعقيد الزمني لهذه الوظيفة هو O (1) ، ترويض ثابت لعملية رئيسية واحدة. فئة Java الرئيسية المناسبة ، مع طريقة Java الرئيسية للطريقة المذكورة أعلاه هي:
عام صف دراسي رئيسي {عام ثابتة فارغ رئيسي ( سلسلة أرجس [ ] ) {
int ن = أحد عشر ؛
هدف فيب = الجديد فيب ( ) ؛
مزدوج حقا = الهدف. فيب ( ن ) ؛
نظام . خارج . println ( حقا ) ؛
}
}
يتم إرسال الفهرس n = 11 ويتم إرجاع رقم فيبوناتشي ، 89. الخرج هو:
89.00000000000003يمكن إزالة الأرقام العشرية غير الضرورية ، لكن هذه مناقشة لبعض الوقت.
استنتاج
أرقام فيبوناتشي هي سلسلة معينة من الأعداد الصحيحة. للحصول على الرقم الحالي ، أضف الرقمين المتوافقين السابقين مباشرة. أول رقمين فيبوناتشي ، 0 متبوعًا بالرقم 1 ، معلنان مسبقًا ، للتسلسل بأكمله. يتم إنتاج باقي أرقام فيبوناتشي من هناك.
لإنتاج أرقام فيبوناتشي من الفهرس 2 ، إلى تلك التي تتوافق مع الفهرس n-1 ، استخدم حلقة for مع العبارة الرئيسية:
int تيار = ص [ أنا - 1 ] + ص [ أنا - اثنين ] ؛حيث CurrNo هو رقم فيبوناتشي الحالي و P هو المصفوفة لتخزين الأرقام n.
لإنتاج رقم فيبوناتشي واحد فقط من أي مؤشر ن صفري ، استخدم الصيغة الرياضية:
