لئوناردو فیبوناچی از ریاضی دانان مشهور قرن سیزدهم میلادی به رابطه ی جالبی میان اعداد دست یافت که دنباله ی این اعداد را سری فیبوناچی نام نهاد. همسان سازی میان الگوی موجود در این دنباله از اعداد و الگوهای موجود در طبیعت نشان دهنده ی اعتبار و اهمیت درک این موضوع است. در مقاله ی برنامه دنباله فیبوناچی در پایتون به معرفی اعداد و دنباله ی فیبوناچی می‌پردازیم و با روش‌های مختلف حل آن به کمک زبان پایتون آشنا می‌شویم.

سری فیبوناچی چیست؟

دنباله ی فیبوناچی یا سری فیبوناجی دنباله ای از اعداد به شکل زیر است:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

در این دنباله عدد بعدی با جمع دو عدد ماقبل خود به دست می‌آید:

2=1+1
3=1+2
5=2+3

و بقیه اعدد نیز به همین ترتیب محاسبه می‌شوند و مفهوم بسیار ساده ای است. لیست طولانی‌تر این دنباله به شکل زیر است:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
 144, 233, 377, 610, 987, 1597, 2584, 4181,
 6765, 10946, 17711, 28657, 46368, 75025,
 121393, 196418, 317811, ...

تولید مارپیچ (Spiral)

وقتی مربع هایی با این عرض‌ها درست می‌کنیم، یک مارپیچ خوب بدست می‌آوریم:

آیا می‌بینید که مربع‌ها چگونه در کنار هم قرار می‌گیرند؟ با نظم خاصی که در دنباله ی فیبوناچی ظاهر شده اند: 1 کنار 2، 3 کنار 2، 5 کنار 3، 8 کنار 5 و ... .

گیاهان می‌توانند سلول‌های جدید را در الگوی مارپیچی تولید کنند. مانند الگوی دانه‌ها در گل زیبای شکل زیر:

مارپیچ به طور طبیعی اتفاق می‌افتد و هر سلول جدید پس از چرخش طبق الگوی مارپیچ تشکیل می‌شود.

کد سری فیبوناچی در پایتون

به کمک عبارات ریاضی می‌توان سری فیبوناچی را به شکل زیر نوشت:

Fn = Fn-1 + Fn-2

یعنی مقدار هر عنصر جدید را می‌توان به کمک مجموع دو عنصر قبلی و طبق یک رابطه ی بازگشتی نوشت که مقادیر اولیه ی آن به شکل زیر است:

F0 = 0 & F1 = 1

در کد زیر دنباله ی فیبوناچی را به کمک رابطه ی بازگشتی تعریف می‌کنیم. ابتدا شرایط بازگشت را با عبارت شرطی if و با بررسی مقادیر اولیه تعریف کرده و سپس طبق روال توابع بازگشتی، مقدار تابع بازگشتی را بر اساس مقادیر قبلی به شکل جمله ی nام سری فیبوناچی، تعریف می‌کنیم:

# Function for nth Fibonacci number 
def Fibonacci(n): 
    if n<0: 
        print("Incorrect input") 
    # First Fibonacci number is 0 
    elif n==0: 
        return 0
    # Second Fibonacci number is 1 
    elif n==1: 
        return 1
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2) 
# Driver Program 
print(Fibonacci(9))

خروجی را به ازای مقدار 9 بررسی می‌کنیم. یعنی مقدار جمله ی نهم سری فیبوناچی را محاسبه می‌کنیم :

34

پیچیدگی زمانی این کد به صورت (T(n) = T(n-1) + T(n-2 است که نمایی است. حل مسأله و کدنویسی به روش بازگشتی موجب بروز کارهای تکراری و در نهایت باعث افزایش زمان اجرای برنامه می‌شود. برای مثال در شکل زیر مراحل محاسبه ی جمله ی پنجم را می‌بینید که چه تعداد گره تکراری دارد.

                           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)

اندازه ی پشته در این حالت از (O(n است.

می توان برای جلوگیری از تکرار محاسباتی، از روش برنامه ریزی دینامیک یا پویا استفاده کرد. طوری که نتیجه ی عملیاتی محاسباتی را در هر مرحله در داخل یک لیست ذخیره کنیم و در صورت نیاز مجدد، آن را از لیست به دست آوریم. در این صورت زمان اجرای برنامه از مرتبه ی خطی خواهد بود. در کد زیر چگونگی محاسبه ی اعداد فیبوناچی به روش برنامه نویسی پویا را می‌بینید:

# Fibonacci Series using Dynamic Programming  
def fibonacci(n):  
    # Taking 1st two fibonacci nubers as 0 and 1  
    FibArray = [0, 1]  
    while len(FibArray) < n + 1:  
        FibArray.append(0)  
    if n <= 1:  
        return n  
    else:  
        if FibArray[n - 1] == 0:  
            FibArray[n - 1] = fibonacci(n - 1)  
        if FibArray[n - 2] == 0:  
            FibArray[n - 2] = fibonacci(n - 2)  
    FibArray[n] = FibArray[n - 2] + FibArray[n - 1]  
    return FibArray[n]  
print(fibonacci(9)) 

خروجی برنامه برابر است با:

34

قطعه کد بالا از نظر مرتبه ی زمانی بهینه است. می‌توان از نظر مرتبه مصرف حافظه نیز آن را بهینه سازی نمود. به روش به کار گرفته در برنامه ی زیر توجه کنید:

# Function for nth fibonacci number - Space Optimisataion 
# Taking 1st two fibonacci numbers as 0 and 1 
def fibonacci(n): 
    a = 0
    b = 1
    if n < 0: 
        print("Incorrect input") 
    elif n == 0: 
        return a 
    elif n == 1: 
        return b 
    else: 
        for i in range(2,n+1): 
            c = a + b 
            a = b 
            b = c 
        return b 
# Driver Program 
print(fibonacci(9)) 

در کد بالا تنها دو عدد ماقبل هر یک از اعداد در سری فیبوناچی را ذخیره می‌کنیم. پس از نظر زمانی مرتبه ی (O(n و از نظر حافظه (O(1 است. خروجی کد بالا نیز برابر است با:

34

روش دیگری برای محاسبه ی اعداد فیبوناچی است که بر پایه ی محاسبه ی توان nاٌم ماتریس {{M= {{1,1},{1,0 می‌باشد. این روش متکی بر این واقعیت است که اگر ماتریس M را n مرتبه به خودش ضرب کنیم (به عبارتی توان nاٌم ماتریس M را محاسبه کنیم)، می‌توانیم عدد n+1اٌم فیبوناجی را به دست بیاوریم که برابر عنصر (0,0) در ماتریس حاصل است. به توان رساندن ماتریس می‌تواند اعداد فیبوناچی زیر را تولید کند.

در کد زیر که یک تابع کمکی است، نحوه ی محاسبه ی روش بیان شده برای به دست آوردن اعداد فیبوناچی توسط به توان رساندن ماتریس M را می‌بینیم. تابع multiply دو ماتریس M و F را که 2*2 است، در هم ضرب می‌کند.

# Helper function that multiplies  
# 2 matrices F and M of size 2*2,  
# and puts the multiplication 
# result back to F[][]  
# Helper function that calculates  
# F[][] raise to the power n and  
# puts the result in F[][] 
# Note that this function is  
# designed only for fib() and  
# won't work as general 
# power function  
def fib(n): 
    F = [[1, 1], 
         [1, 0]] 
    if (n == 0): 
        return 0
    power(F, n - 1) 
    return F[0][0] 
def multiply(F, M): 
    x = (F[0][0] * M[0][0] + 
         F[0][1] * M[1][0]) 
    y = (F[0][0] * M[0][1] +
         F[0][1] * M[1][1]) 
    z = (F[1][0] * M[0][0] + 
         F[1][1] * M[1][0]) 
    w = (F[1][0] * M[0][1] + 
         F[1][1] * M[1][1]) 
    F[0][0] = x 
    F[0][1] = y 
    F[1][0] = z 
    F[1][1] = w 
def power(F, n): 
    M = [[1, 1], 
         [1, 0]] 
    # n - 1 times multiply the 
    # matrix to {{1,0},{0,1}} 
    for i in range(2, n + 1): 
        multiply(F, M) 
# Driver Code 
if __name__ == "__main__": 
    n = 9
    print(fib(n)) 

خروجی تابع به شکل زیر است:

34

این تابع نیز زمان محاسباتی از (O(n دارد و مصرف حافظه ی مازاد آن از (O(1 است. می‌توان روش ارائه شده ی مبتنی بر توان رساندن ماتریس را بهینه کرد؛ به طوری که پیچیدگی زمانی آن (O(logn گردد. برای محاسبه ی به توان n رساندن ماتریس M از روش ضرب به شیوه ی بازگشتی استفاده می‌شود. به کد زیر توجه کنید:

# Fibonacci Series using  
# Optimized Method 
# function that returns nth  
# Fibonacci number  
def fib(n): 
    F = [[1, 1], 
         [1, 0]] 
    if (n == 0): 
        return 0
    power(F, n - 1) 
    return F[0][0] 
def multiply(F, M): 
    x = (F[0][0] * M[0][0] + 
         F[0][1] * M[1][0]) 
    y = (F[0][0] * M[0][1] + 
         F[0][1] * M[1][1]) 
    z = (F[1][0] * M[0][0] + 
         F[1][1] * M[1][0]) 
    w = (F[1][0] * M[0][1] + 
         F[1][1] * M[1][1]) 
    F[0][0] = x 
    F[0][1] = y 
    F[1][0] = z 
    F[1][1] = w 
# Optimized version of 
# power() in method 4  
def power(F, n): 
    if( n == 0 or n == 1): 
        return; 
    M = [[1, 1], 
         [1, 0]]; 
    power(F, n // 2) 
    multiply(F, F) 
    if (n % 2 != 0): 
        multiply(F, M) 
# Driver Code 
if __name__ == "__main__": 
    n = 9
    print(fib(n)) 
  

خروجی تابع به شکل زیر است:

34

پیچیدگی زمانی برنامه ی بالا (O(logn است و از نظر مصرف حافظه ی اضافی اگر از پشته استفاده کنیم، (O(logn و در غیر این صورت از (O(1 می‌باشد.

جمع بندی

در مقاله برنامه دنباله فیبوناچی در پایتون به معرفی اعداد فیبوناچی و نحوه ی کدنویسی آن در زبان پایتون پرداختیم. این مفهوم ساده و پایه ای کاربرد گسترده ای در علوم طبیعی و حتی اقتصاد دارد. الگوریتم‌های مختلفی برای حل آن موجود است که از نظر هزینه ی زمانی و مصرف حافظه بهینه سازی شده اند که در این مقاله دو مورد بازگشتی و روش برنامه نویسی پویا ارائه شد. خوشحال می‌شویم نظرات و پیشنهادات خود را با ما در میان بگذارید.

اگر به یادگیری بیشتر در زمینه ی برنامه نویسی پایتون علاقه داری، یادگیری زبان پایتون بسیار ساده است. و با شرکت در دوره ی متخصص آموزش پایتون توسعه وب در آینده می‌تونی اپلیکیشن موبایل و دسکتاپ بسازی و وارد حوزه ی هوش مصنوعی هم شوی.