أرقام فيبوناتشي هي الأرقام الموجودة في تسلسل الأعداد الصحيحة التالية. 0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89 ، 144 ، …… .. من الناحية الرياضية ، يتم تحديد تسلسل Fn لأرقام فيبوناتشي من خلال علاقة التكرار

Fn = Fn-1 + Fn-2 
F0 = 0 and F1 = 1.

الطريقة الأسهل هي استعمال العودية ولكن تستغرق وقت حتى يتم ينفيذها 

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)
 

درجة التعقيد هي 2 قوى n ، وهي كبيرة جدا 

لأن هذه هي العميات التي تتم 

                        fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

لحساب fib(5) يتم تنفيذ 15 عملية وهذا غير جيد . 

الطريقة الثانية باستعمال البرمجة الديناميكية 

def fibonacci(n):
     
# أخذ أول رقمين فيبوناتشي على هيئة 0 و 1
    f = [0, 1]
    for i in range(2, n+1): # نملأ الجدول 
        f.append(f[i-1] + f[i-2])
    return f[n]
     
print(fibonacci(9))

درجة التعقيد هنا هي فقط O(n)

الطريقة الثالثة باستعمال المصفوفات 

طريقة صعبة ولكن ذو سرعة عالية وتعقيد اقل 

MAX = 1000

# إنشاء مجموعة للحفظ
f = [0] * MAX

# إرجاع رقم فيبوناتشي n باستخدام الجدول f []
def fib(n) :
# الحالات الأساسية
	if (n == 0) :
		return 0
	if (n == 1 or n == 2) :
		f[n] = 1
		return (f[n])

# إذا تم حساب Fib (n) بالفعل
	if (f[n]) :
		return f[n]

	if( n & 1) :
		k = (n + 1) // 2
	else :
		k = n // 2

# تطبيق الصيغة أعلاه [قيمة الملاحظة n & 1 هي 1
# إذا كان n فرديا ، وإلا 0.
	if((n & 1) ) :
		f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
	else :
		f[n] = (2*fib(k-1) + fib(k))*fib(k)

	return f[n]

درجة التعقيد هنا هي فقط O(logn) فقط !

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

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

نهيأ المصفوفة عند الدليل 0 بأول عدد فيبوناتشي و هو ال 0، و نهيأ المصفوفة عند الدليل 1 بثاني عدد فيبوناتشي و هو ال 1، ثم نقوم بالمرور بحلقة و في كل مرة يكون العنصر i هو مجموع العنصرين i-1, i-2 و الذين موجودان حتماً.

مثال عن طريق البايثون:

def f():
	a = [0, 1]
	for i in range(2, 1000000):
		a.append(a[i-1] + a[i-2])
	return a

fib = f()
# الآن يمكننا الوصول إلى أي عدد كما يلي
print(fib[1000])

هناك صيغة صريحة explicit formula لإيجاد أعداد فيبوناتشي هي كالتالي:

from math import *
def getF(x):
      x-=1
      if x <= 0:
            return 0
      Phi = (1+sqrt(5))/2
      phi = -1/Phi
      return floor((pow(Phi,x)-pow(phi,x))/sqrt(5))
for x in range(1,1000):
      print(getF(x))

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

الطريقة السابقة مع الطرق التي ذكرها المدربون جميعها مذكورة في كتاب تصميم وتحليل الخوارزميات للبروفيسور Anany Levitin مع برهان كل طريقة إذا أحببت الإطلاع عليه.