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

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

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

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 می‌باشد.

جمع‌بندی

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

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